Project Euler problem 19 - How many Sundays fell on the first

Question

Here's the problem:

How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

And here's my code:

#include <stdio.h>

int main(void){
    int months[12] = { 31 , 28 , 31 , 30 , 31 , 30 , 31 , 31 , 30 , 31 , 30 , 31 };
    int year=1901;
    int dayoftheweek=2;  //put a 2 because the 1 jan 1901 is tuesday. 0-sunday 6-Saturday
    int sunday=0;
    int firstsundays=0;

    while(year<=2000){
        if(year%4==0)    //checking if it's a leap year
            months[1]=29;

        for (int i = 0; i < 12; ++i) {
            for (int d = 1; d <= months[i]; d++){
                if(dayoftheweek==7)  //reset the week
                    dayoftheweek=0;

                if(dayoftheweek==sunday && d==1)
                    firstsundays++;

                dayoftheweek++;
            }
        }

        months[1]=28;
        year++;
    }

    printf("There are %d Sundays that fell on the first of the month\n", firstsundays);

    return 0;
}

What could I improve?

Answer 1

The loops could be clearer:

• The outermost loop is actually spread across three lines: int year=1901, while(year<=2000), and year++. It should be written as a for loop.
• i should be renamed to month or m.
• The exceptional case for leap years is awkward: you sometimes clobber the February entry at the top of the loop, then reset it at the end. I'd consider such mutations to be a hack that makes the code harder to understand. It also makes the code harder to maintain, since you have hard-coded 29 and 28 in scattered places.

As for the algorithm itself… you should be able to do better than advancing a day at a time through an entire century. Why not advance a month at a time?

#include <stdio.h>

static const int *month_lengths(int year) {
    static const int NON_LEAP_YEAR[] = {
        31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31
    };
    static const int LEAP_YEAR[] = {
        31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31
    };
    return (year % 4 == 0 && (year % 100 != 0 || year % 400 == 0)) ?
        LEAP_YEAR : NON_LEAP_YEAR;
}

int main(void) {
    int first_sundays = 0;
    int day_of_the_week = 2;    // 0 = Sun, 6 = Sat.  1 Jan 1901 was a Tuesday.
    for (int year = 1901; year <= 2000; ++year) {
        const int *lengths = month_lengths(year);
        for (int month = 0; month < 12; month++) {
            if (day_of_the_week == 0) {
                first_sundays++;
            }
            day_of_the_week = (day_of_the_week + lengths[month]) % 7;
        }
    }
    printf("There are %d Sundays that fell on the first of the month\n",
           first_sundays);
}