Project Euler #19: Counting Sundays

This article is part of a series where I'll be diving head first into the Project Euler puzzles. I want to document the challenge of solving such a puzzle and how I got to the answer. I want to prefix this by stating that I can't cheat for any of these challenges; with that I mean I can't look up any other implementations online. After the implementation, I will validate the answer by using this document or a similar sheet.

In this article I'll be solving: Project Euler #19.

Introduction The puzzle asks: “how many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?”

Initially I start out with this:

fn problem_19() -> u32 {
    for year in 1901..=2000 {
        for month in 0..=11 {
            // How many days?
            // Incl. leap years.
        }
    }

    0
}

#[test]
fn test_sundays() {
    assert_eq!(problem_19(), 1);
}

The next step is to determine the amount of days per month. It’s a pretty steady number except on a leap year.

for year in 1901..=2000 {
    // There are 4 months which are 30 days long:
    // September, April, June and November.
    // The rest of the 7 months are 31 days long,
    // except February which has 28 days except on leap years.
    let mut month_lengths = vec![
        31, // January,
        0,  // February,
        31, // March
        30, // April
        31, // May
        30, // June
        31, // July
        31, // August
        30, // September
        31, // October
        30, // November
        31 // December
    ];
    // Since 2000 is divisble by 400, it's therefor also divisible
    // by 4, so there's no need to apply that rule here.
    month_lengths[1] = if year % 4 == 0 {
        29
    } else {
        28
    };

    for month in 0..=11 {
        for day in 0..month_lengths[month] {
            println!("{}", day + 1);
        }
    }
}

The next part of this puzzle is to find out on which day the first of January 1901 landed. Google has the answer here: “Tuesday”, which is the 2nd day of the week. Including in the weekdays I guess I can start counting.

let mut weekday = 1;
for month in 0..=11 {
    for day in 0..month_lengths[month] {
        if day == 0 && weekday % 7 == 6 {
            total_sundays += 1
        }

        weekday += 1;
    }
}

The answer I receive from the code is: 175 Sundays landed on the first day of a month. Upon checking the correct answer, I find out the actual answer should be 171 Sundays, meaning I’m 4 off. I also found out why, it was because I was resetting the weekdays to Tuesday every year which is not really what happens in real life. After fixing that little mistake I got the correct answer of 171 Sundays.

Improvements In the code month_lengths only has to be initiated once, instead of every loop cycle. Also I feel I can do something smart with the way we determine if it’s a Sunday on the first of the month. Considering we’re only interested in one day of the month, it feels a little bit useless to loop over each day of the month regardless. The code therefor can be shortened to:

fn problem_19() -> u32 {
    let mut total_sundays = 0;
    let mut weekday = 1;
    // There are 4 months which are 30 days long:
    // September, April, June and November.
    // The rest of the 7 months are 31 days long,
    // except February which has 28 days except on leap years.
    let mut month_lengths = vec![
        31, // January
        0,  // February
        31, // March
        30, // April
        31, // May
        30, // June
        31, // July
        31, // August
        30, // September
        31, // October
        30, // November
        31 // December
    ];

    for year in 1901..=2000 {
        // Since 2000 is divisible by 400, it's therefor also divisible
        // by 4, so there's no need to apply that rule here.
        month_lengths[1] = if year % 4 == 0 {
            29
        } else {
            28
        };

        for month in 0..=11 {
            if weekday % 7 == 6 {
                total_sundays += 1
            }
            weekday += month_lengths[month];
        }
    }

    total_sundays
}

The full solution is available on GitHub.

55545352515049484746454443424140393837363534333231302928272625242322212019181716151413121110987654321