popular this month

recent comments

recent articles

Almer S. Tigelaar » Puzzles

Puzzle #4: Working Days

Almer S. Tigelaar 06 / 10 / 2011, 09:00

Calculating the number of days between two arbitrary dates is doable for humans and trivial on modern computers. However, calculating the number of working days: Mondays through Fridays, is more complicated. In this puzzle you are asked to devise an algorithm for doing this. It is something you can do on the back of a napkin, so you don’t need anything besides pen, paper and the rational part of your brain.

Problem:
Given two dates d_{1}, d_{2} where d_{2}>d_{1}, what is the number of workdays w between these two dates? Assume that only Saturdays and Sundays are not workdays: holidays can be ignored.

You may use the following definitions augmented with any standard mathematical functions, like div and min.

  • d is a date
  • Subscripts are used to indicate different dates: d_{1},d_{2}\cdots d_{n}
  • d_{x}-d_{y} yields the number of days between two dates. This is negative if d_{x}<d_{y} and zero if the dates are identical
  • weekday\left(d\right) gives the day of the week for the given date as a number (1 = Monday, 2 = Tuesday, …, 7 = Sunday)
  • weeknumber\left(d\right) gives the number of the week for the specified date (in the range 1 up to including 53)
  • workdays=\left\{ 1,2,3,4,5\right\} is the set of numbers that represent working days (a subset of the domain of the weekday function)

Try to work out a solution first, then expand mine below.

More »


Solution:
There are really two cases to consider.

If both days are in the same week:
weeknumber\left(d_{1}\right)=weeknumber\left(d_{2}\right)\Rightarrow d_{2}-d_{1}\leq7,
the solution might seem simple: w=d_{2}-d_{1}. This will work provided that both dates have a weekday less than or equal to five. If this is not the case, we need a more complex function: w=min\left(weekday\left(d_{2}\right),5\right)-min\left(weekday\left(d_{1}\right),5\right)+1. The min function returns the lesser of its two arguments (or either one in case they are equal). The +1 is to count the end date as a whole day. Note that we exploit here the fact that the workdays form a continuous range (1–5).

If both days are not in the same week:
weeknumber\left(d_{1}\right)\neq weeknumber\left(d_{2}\right),
then we must devise a way to find the number of weekends in between the two dates (each weekend subtracts two days from the interval \left[d_{2},d_{1}\right]). We can do this in three steps:

  1. Determine if the starting day is in a workweek: 5-weekday\left(d_{1}\right)\geq0. If so, then set this as the initial count: c=\left(5-weekday\left(d_{1}\right)\right), otherwise set c=0.
  2. c now covers the number of working days in the first week of the range. To find the number of remaining days we first subtract 7-weekday\left(d_{1}\right) days from the days between the dates d_{2}-d_{1}. We wil define this as: r=\left(d_{2}-d_{1}+1\right)-\left(7-weekday\left(d_{1}\right)\right).
  3. The number of weekends must be div\left(r,7\right), since each weekend consists of two days, we must subtract this twice, giving: w=c+r-\left(2\cdot div\left(r,7\right)\right). The div function is an integer division yielding a whole number. It is equivalent to \left\lfloor x/y\right\rfloor (the floor of a division, in this case between r and 7).

These steps are the full solution for the case where the weeks are not equal. Below are some examples of the method presented. However, perhaps you’ve come up with a simpler or more elegant solution? Let me know in the comments below.

Examples:
For the number of working days between d_{1}=16-02-2009 (weekday 1) and d_{2}=18-02-2009 (weekday 3): since these are within the same week (week 8), the number of working days is:

w=min\left(3,5\right)-min\left(1,5\right)+1=3-1+1=3

For the number of working days between d_{1}=16-02-2009 (weekday 1) and d_{2}=22-02-2009 (weekday 7): these are also within the same week (week 8), but the end date is in the weekend. Still this should work:

w=min\left(7,5\right)-min\left(1,5\right)+1=5-1+1=5

For the number of working days between d_{1}=16-02-2009 (weekday 1) and d_{2}=25-02-2009 (weekday 3): these are not within the same week, thus we must use the three step approach:

c=\left(5-1\right)=4
r=\left(25-16+1\right)-\left(7-1\right)=10-6=4
w=4+4-\left(2\cdot0\right)=8

Here we see that the last part of the formula has no effect. This is always true for adjacent weeks, since div\left(r,7\right)\geq1 only if r\geq7.

So, now for non-adjacent weeks:
For the number of working days between d_{1}=09-02-2009 (weekday 1) and d_{2}=25-02-2009 (weekday 3):

c=\left(5-1\right)=4
r=\left(25-9+1\right)-\left(7-1\right)=17-6=11
w=4+11-\left(2\cdot1\right)=13

tags: algorithm, li, linkedin, mathematics, workdays,

More in Puzzles:

2 comments

add your comment
  • ^ reply

    Things become much easier if you're also allowed to subtract an integer from a date, resulting in a new date. Then you can just look at the number of days between the dates, div it by 7 to obtain whole weeks — for which you can count 5 working days –, and subtract these weeks from d2. You're left with a new d2 within a week of d1, and count the remaining working days by enumeration. See line 7-14 of http://pastebin.com/YNeCtDtz

    Sander E
    on 16 / 10 / 2011 wrote:
    • ^ reply

      @Sander E I played around with your code, it's a nice solution that seems to work well for all the cases presented, and indeed simplifies the problem a lot as you pointed out. Thanks for sharing :)

      almer.tigelaar
      on 19 / 10 / 2011 wrote: