Thank God It’s Friday!

June 24, 2011

We have previously given two algorithms to calculate the day of the week, one in the Standard Prelude and one in the exercise on Zeller’s Congruence. In today’s exercise we give three more algorithms to calculate the day of the week.

Our first method is due to Carl Gauss, and is based on moving January and February to the end of the preceding year, then fitting a straight line through the number of days in each month. Gauss gives the formula w = \left( d + \lfloor 2.6 m - 0.2 \rfloor + y + \lfloor \frac{y}{4} \rfloor + \lfloor \frac{c}{4} \rfloor - 2c \right) \pmod{7} where Y is the input year, except that it is reduced by 1 in January and February, d is the day of the month, m is the number of the month, with 1 for March through 12 for February, y is the last two digits of Y, c is the first two digits of Y, and w is the day of the week, with 0 for Sunday through 6 for Saturday. For instance, June 24, 2011 is calculated as 24 + floor(2.6×4−0.2) + 11 + floor(11÷4) + floor(20÷4) – 2×20, modulo 7, which is 5 for Friday.

Our second method is due to Tomohiko Sakamoto, who gives a table of offsets for the days of each month from the day at the start of the year: t = {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4}. Then Sakamoto subtracts 1 from the input year in January and February and calculates the day of the week with the formula \left( y + \lfloor \frac{y}{4} \rfloor - \lfloor \frac{y}{100} \rfloor + \lfloor \frac{y}{400} \rfloor + t[m-1] + d \right) \pmod{7}. For instance, June 24, 2011 is calculated as 2011 + floor(2011÷4) − floor(2011÷100) + floor(2011÷400) + t[6−1] + 24 = 2011 + 502 – 20 + 5 + 3 + 24 = 2525, modulo 7, which is 5 for Friday.

Our third method is due to John Horton Conway, and is intended for mental calculation. Conway’s method is based on calculating the anchor day for the requested century, the doomsday for the requested year, and interpolating from various repetitions of the doomsday through the year.

The anchor day is calculated as \left( 5c + \lfloor \frac{c-1}{4} \rfloor \right) \pmod{7} + Thursday, where c is the century; note that century years, such as 2000, are part of the succeeding century, so c=21 for the year 2000. For example, the anchor day for the 21st century is Tuesday, calculated as 5×21 + floor(20÷4), modulo 7, plus Thursday. Anchor days repeat every four centuries, in the cycle Friday, Wednesday, Tuesday, Sunday starting from the year 1800.

The doomsday is calculated by dividing the last two digits of the year by 12 to calculate the quotient and remainder. Then the doomsday is the quotient, plus the remainder, plus the quotient of the remainder divided by 4, plus the anchor day for the century. For example, the doomsday for 2011 is Monday, calculated as 0 + 11 + floor(11÷4) = 13, which is 6 modulo 7, plus the anchor day Tuesday.

Once the doomsday is known, the day of the week is calculated by locating the nearest doomsday in each month, which can be memorized in the following manner: For April, June, August, October, and December, the doomsday is the month number: 4/4, 6/6, 8/8, 10/10, and 12/12. For May, July, September, and November, the doomsday can be calculated by the ditty “I worked 9 to 5 at 7-11″ which gives 5/9, 7/11, 9/5, and 11/7. The last day of February is a doomsday, whether a common year or a leap year, and this gives an easy way to calculate the day of the week for March, where doomsday is 3/0 (the “zeroth” day of March). All that’s left is January, for which the doomsday is 1/10 in common years and 1/11 in leap years.

Thus, the day of the week for June 24, 2011 is calculated as 24−6=18 ≡ 4 (mod 7) days past the doomsday, which gives an answer of Friday. Conway claims to be able to calculate any day of the week in two seconds, though I confess I have not been able to make the required calculations reliably except by using pencil and paper to assist.

Your task is to write programs to calculate the day of the week using the three functions described above; for Conway’s algorithm, you should calculated the doomsday for the year rather than the day of the week for the date. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

5 Responses to “Thank God It’s Friday!”

  1. [...] today’s Programming Praxis exercise, our goal is to implement three functions related to dates: two ways to [...]

  2. My Haskell solution (see http://bonsaicode.wordpress.com/2011/06/24/programming-praxis-thank-god-it%E2%80%99s-friday/ for a version with comments):

    data Weekday = Sun | Mon | Tue | Wed | Thu | Fri | Sat deriving (Enum, Eq, Show)
    
    gauss :: Int -> Int -> Int -> Weekday
    gauss y m d = toEnum $ mod (d + floor (2.6 * fromIntegral
      (mod (m - 2) 12) - 0.2) + y' + div y' 4 + div c 4 - 2*c) 7 where
        (c,y') = divMod (if m < 3 then y - 1 else y) 100
    
    sakamoto :: Int -> Int -> Int -> Weekday
    sakamoto y m d = toEnum $ mod (y + div y 4 - div y 100 +
        div y 400 + [0,3,2,5,0,3,5,1,4,6,2,4] !! (m - 1) + d) 7
    
    conway :: Int -> Weekday
    conway y = toEnum $ mod (q + r + div r 4 + 5*(c+1) + div c 4 + 4) 7
        where (c, (q,r)) = (div y 100, divMod (mod y 100) 12)
    
  3. Graham said

    My Python submission (basically just a translation of the Scheme solution):

    #!/usr/bin/env python
    
    from fractions import Fraction
    
    DAYS = {0: "Sunday", 1: "Monday", 2: "Tuesday", 3: "Wednesday", 4: "Thursday",
            5: "Friday", 6: "Saturday"}
    
    def gauss(year, month, day):
        yr = (year - 1) if (month < 3) else year
        m = (month + 10) if (month < 3) else (month - 2)
        c, y = divmod(yr, 100)
        return DAYS[sum((day, int((Fraction('13/5') * m) - Fraction('1/5')), y,
                     (y / 4), (c / 4), - 2 * c)) % 7]
    
    def sakamoto(year, month, day):
        t = [0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4]
        y = (year - 1) if (month < 3) else year
        return DAYS[sum((day, y, (y / 4), - (y / 100), (y / 400), t[month - 1]))
                    % 7]
    
    def doomsday(year):
        return DAYS[sum((2, year, year / 4, - (year / 100), year / 400)) % 7]
    
    if __name__ == "__main__":
        print gauss(2011, 6, 24)
        print sakamoto(2011, 6, 24)
        print doomsday(2011)
    
  4. Mike said

    Python version

    Tried all the formulas from Wikipedia for conway’s method. And went all the way to calculate the day of the week.

    dow = "Sun Mon Tue Wed Thu Fri Sat".split()
    
    def leap(year):
        return bool(not year % 400 or not year % 4 and year % 100)
    
    def gauss(year, month, day):
        c, y = divmod(year if month > 2 else (year - 1), 100)
        m = (month - 3)%12 + 1
        return dow[(day + int(2.6*m - 0.2) + y + y//4 + c//4 - 2*c) % 7]
    
    def sakamoto(year, month, day):
        t = [0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4]
        y = year if month > 2 else (year - 1)
        return dow[(day + y + y//4 - y//100 + y//400 + t[month - 1]) % 7]
    
    def conway(year, month, day):
        c, y = divmod(year, 100)
    
        # original formula
        #c += 1
        #anchor = (5*c + (c-1)//4 + 4)%7
        # modified formula-don't add 1 to first 2 digits of year.
        anchor = (5*c + c//4 + 2)%7
    
        # original conway formula
        #doomsday = (anchor + y//12 + y%12 + y%12//4)%7
    
        # alternative from wikipedia.  I think this is easiest to do in head.
        doomsday = (anchor + y + y//4)%7
    
        # odd+11 rule from wikipedia
        #y = (y+11) if y&1 else y
        #y = y//2
        #y = (y+11) if y&1 else y
        #y = 7 - y%7
        #doomsday = (anchor + y)%7
    
        #computer formula from wikipedia
        #doomsday =  (2 + y + y//4 - y//100 + y//400)%7
    
        nearest = (10, 28, 0, 4, 9, 6, 11, 8, 5, 10, 7, 12)[month - 1]
        if month < 3 and leap(year):
            nearest += 1
        
        return dow[(doomsday + day - nearest) % 7]
    
  5. razvan said

    Here’s my solution in Java:

    package dayofweek;
    
    public class DayOfWeek {
    
        private static final int[] SAKAMOTO_TABLE = { 0, 3, 2, 5, 0, 3, 5, 1, 4, 6,
                2, 4 };
    
        private static void checkDate(int d, int m, int y) {
            if (m < 1 || m > 12)
                throw new NumberFormatException("Bad month");
            if (d < 0 || d > 31)
                throw new NumberFormatException("Bad day");
            if (m == 2
                    && (d > 29 || d > 28
                            && ((y % 4 == 0 && y % 100 != 0) || y % 400 == 0)))
                throw new NumberFormatException("Bad day");
            if (y < 0)
                throw new NumberFormatException("Bad year");
        }
    
        public static int gauss(int d, int m, int y) {
            checkDate(d, m, y);
            if (m >= 3 && m <= 12)
                m -= 2;
            else if (m < 3 && m > 0) {
                m += 10;
                y--;
            }
            int c = y / 100;
            y %= 100;
            return (d + (int) Math.floor(2.6 * (double) m - 0.2) + y + y / 4 + c
                    / 4 - 2 * c) % 7;
        }
    
        public static int sakamoto(int d, int m, int y) {
            checkDate(d, m, y);
            if (m < 3 && m > 0)
                y--;
            return (y + y / 4 - y / 100 + y / 400 + SAKAMOTO_TABLE[m - 1] + d) % 7;
        }
    
        public static int conway(int d, int m, int y) {
            checkDate(d, m, y);
            int c = y / 100 + 1;
            int anchor = ((5 * c + (c - 1) / 4) % 7 + 4) % 7;
            int yy = y % 100;
            int quo = yy / 12, rem = yy % 12;
            int doomsday = ((quo + rem + rem / 4) % 7 + anchor) % 7;
            int doom = 0;
            if (m == 4 || m == 6 || m == 8 || m == 10 || m == 12)
                doom = m;
            else if (m == 2) {
                if ((y % 4 == 0 && y % 100 != 0) || y % 400 == 0)
                    doom = 29;
                else
                    doom = 28;
            } else if (m == 3)
                doom = 0;
            else if (m == 3) {
                if ((y % 4 == 0 && y % 100 != 0) || y % 400 == 0)
                    doom = 11;
                else
                    doom = 10;
            } else
                switch (m) {
                case 5:
                    doom = 9;
                    break;
                case 7:
                    doom = 11;
                    break;
                case 9:
                    doom = 5;
                    break;
                case 11:
                    doom = 7;
                    break;
                }
    
            if (d > doom)
                return ((d - doom) % 7 + doomsday) % 7;
            else
                return ((doomsday - (doom - d) % 7) + 7) % 7;
        }
    
        public static String intToDate(int d) {
            switch (d) {
            case 0:
                return "Sunday";
            case 1:
                return "Monday";
            case 2:
                return "Tuesday";
            case 3:
                return "Wednesday";
            case 4:
                return "Thursday";
            case 5:
                return "Friday";
            case 6:
                return "Saturday";
            }
            throw new NumberFormatException("Bad day of week");
        }
    
        public static void main(String[] args) {
            System.out.println(intToDate(gauss(24, 6, 2011)));
            System.out.println(intToDate(sakamoto(24, 6, 2011)));
            System.out.println(intToDate(conway(11, 5, 2010)));
        }
    
    }
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 617 other followers

%d bloggers like this: