Counting Sundays

You are given the following information, but you may prefer to do some research for yourself.

• 1 Jan 1900 was a Monday.
• Thirty days has September,
  April, June and November.
  All the rest have thirty-one,
  Saving February alone,
  Which has twenty-eight, rain or shine.
  And on leap years, twenty-nine.
• A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400. How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

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

Solution

I’m afraid there’s no clever way to solve this without writing plenty of code. On the other hand, this problem is pretty straightforward; all we need is some domain modelling. Let’s do it then.

We can start by encoding some simple facts about the calendar. We need to know how many days are in a given month, as well as if the year is leap or not. Let’s also add two helper functions to let us quickly check the century:

private type Year = Int

private def daysPerMonth(year: Year): Array[Int] = Array(
  31, // January
  if (isLeapYear(year)) 29 else 28, // February
  31, // March
  30, // April
  31, // May
  30, // June
  31, // July
  31, // August
  30, // September
  31, // October
  30, // November
  31 // December
)

private def isLeapYear(year: Year): Boolean =
  (year % 4 == 0) && (year % 100 != 0 || year % 400 == 0)

def isInTwentiethCentury: Boolean = year >= 1901 && year <= 2000

def isInTwentyFirstCentury: Boolean = year >= 2001

Having those facts laid out, we can try constructing a crude model of a calendar:

case class Calendar(
     dayNumber: Int,
     dayOfWeekNumber: Int,
     monthNumber: Int,
     year: Year
 ) 

In this case:

• dayNumber represents a number of a day in a month, as in June 10
• dayOfWeekNumber is an internal counter for a day of the week, 0 being Monday and 6 Sunday
• monthNumber is a number of the month, 0 being January
• year is a year type that we’ve defined before

Our calendar needs a way to progress the day while keeping the state of other variables consistent. It’s not difficult since we have some data to use. Once the dayOfWeekNumber reaches 7 we go back to 0. Every time we reach a day that’s higher than the daysPerMonth(year)(monthNumber), we either progress the month or a whole year if we’re at the last month (11 on our case, since we count from 0).

If neither of these checks is met, we simply progress the day.

def nextDay(): Calendar = {
  val newDay = dayNumber + 1
  val newDayOfWeek = if (dayOfWeekNumber + 1 == 7) 0 else dayOfWeekNumber + 1

  if (newDay > daysPerMonth(year)(monthNumber)) {
    if (monthNumber == 11) Calendar(1, newDayOfWeek, 0, year + 1)
    else Calendar(1, newDayOfWeek, monthNumber + 1, year)
  } else Calendar(newDay, newDayOfWeek, monthNumber, year)
}

val dayOfWeek: DayOfWeek = daysOfWeek(dayOfWeekNumber)

val isSunday: Boolean = dayOfWeekNumber == 6

And that’s all we need to calculate it. The condition that we’ll be checking is pretty simple: if (calendar.isSunday && calendar.dayNumber == 1) If it’s met, then we’ve found the Sunday we’re looking for. If not, we progress the calendar further, until (calendar.isInTwentyFirstCentury) – that’s the termination condition.

Here’s the whole code:

import scala.annotation.tailrec

object Euler019 extends EulerApp {

  private type DayOfWeek = String
  private type Year = Int

  override def execute(): Any = {
    @tailrec
    def sundaysInTwentyCentury(calendar: Calendar, sundays: Int): Int = {
      if (calendar.isInTwentyFirstCentury) sundays
      else if (calendar.isInTwentiethCentury) {
        val newSundays =
          if (calendar.isSunday && calendar.dayNumber == 1) sundays + 1 else sundays
        sundaysInTwentyCentury(calendar.nextDay(), newSundays)
      } else sundaysInTwentyCentury(calendar.nextDay(), sundays)
    }

    sundaysInTwentyCentury(Calendar.StartDate, 0)
  }

  case class Calendar(
      dayNumber: Int,
      dayOfWeekNumber: Int,
      monthNumber: Int,
      year: Year
  ) {
    private def daysPerMonth(year: Year): Array[Int] = Array(
      31, // January
      if (isLeapYear(year)) 29 else 28, // February
      31, // March
      30, // April
      31, // May
      30, // June
      31, // July
      31, // August
      30, // September
      31, // October
      30, // November
      31 // December
    )

    private def isLeapYear(year: Year): Boolean =
      (year % 4 == 0) && (year % 100 != 0 || year % 400 == 0)

    def nextDay(): Calendar = {
      val newDay = dayNumber + 1
      val newDayOfWeek = if (dayOfWeekNumber + 1 == 7) 0 else dayOfWeekNumber + 1

      if (newDay > daysPerMonth(year)(monthNumber)) {
        if (monthNumber == 11) Calendar(1, newDayOfWeek, 0, year + 1)
        else Calendar(1, newDayOfWeek, monthNumber + 1, year)
      } else Calendar(newDay, newDayOfWeek, monthNumber, year)
    }

    val isSunday: Boolean = dayOfWeekNumber == 6

    def isInTwentiethCentury: Boolean = year >= 1901 && year <= 2000

    def isInTwentyFirstCentury: Boolean = year >= 2001
  }

  object Calendar {
    val StartDate: Calendar = Calendar(dayNumber = 1, dayOfWeekNumber = 0, monthNumber = 0, year = 1900)
  }
}

Mutable solution

While reading the previous solution you might be thinking… why don’t we just use the standard library? Indeed, we can! In fact, this problem is completely trivialized once we do so. We can simply encode the start date and the end date, the condition is easily expressed with API for java.time.LocalDate.

import java.time.{DayOfWeek, LocalDate}

object Euler019M extends EulerApp {
  override def execute(): Int = {
    val endDate = LocalDate.of(2000, 12, 31)
    var currentDate = LocalDate.of(1901, 1, 1)
    var sundays = 0

    while (currentDate.isBefore(endDate)) {
      if (currentDate.getDayOfMonth == 1 && currentDate.getDayOfWeek == DayOfWeek.SUNDAY) sundays += 1
      currentDate = currentDate.plusDays(1)
    }

    sundays
  }
}

Easier, cleaner, better. But in this case, most of the information present in the problem description is not used. We don’t need to check if the year is leap or how many days are in a month. In any project using the standard library would be obviously the way to go, but since we’re just practicing, it makes sense to try to attempt doing it ourselves.