Prob 0019 ‐ Counting Sundays - maccergit/Euler GitHub Wiki

Note that the problem needs to be carefully read - we are not looking for the number of Sundays in each year (typically 52), but instead we want the number times a month starts on a Sunday for each year (typically only couple times each year).

Not a heavy math problem, unless we try to get sophisticated. Direct approach will involve modulo math for leap years (remember the 4-year/100-year/400-year rules) and will benefit from standard software engineering approach (divide and conquer, test driven development, etc...).

Investigate to see if Python includes useful libraries for date processing.

01

A direct approach uses the fact that we can compute the day of the week for the start of the next "partition" given the day of the week of the current partition and the number of days in the next partition, using $nextStart = (currentStart + partitionSize) \mod 7$, assuming the start of the week is day 0. Conventional partitions sizes are : 1 for "days" and 7 for "week". For "month", the size varies by the month, and whether or not it is a leap year. Setting "Sunday" to be day 0 is convenient. We can then start knowing that 1 Jan 1900 is a Monday, and iterate through the months until we get to the current year. We keep iterating through the months, keeping track of those that start on day 0. Note that as the year moves farther away from 1900, the more months we need to walk to get to the current year :

02

One optimization we can make is to realize that we can use the partition of a "year" to get from 1900 to the current year. The partitions size will be 365, or 366 on leap years. Once we are at the current year, we can then iterate through the months as before :

03

The approaches taken so far have all been using the imperative programming paradigm. While we have been using structured programming techniques to break a large program into more manageable pieces, this still leads to large blocks of code that can be difficult to maintain over time. Another approach is Object Oriented Programming (OOP), where data and the code that works on the data are pulled together into distinct entities that have well defined behavior, and then entities are put together like building blocks to create a full program. Python supports OOP, and this solution is a refactored version of the previous one with only minimal optimization. The goal of this refactoring was to create classes that "know" how to work on the data they contain - so a Month knows its starting day and how many days it has - and thus also knows how to compute the starting date of the next month. The month does not know anything about the year, and must be told if the year holding the month is a leap year (only used for February). Some of the data (such as the next month's starting day and the number of days in the month) are computed as the Month is built, and not later when the Month is accessed. Since we typically use each object only once in this example, we don't save any time by pre-computing these values - but in other situations, this could be considered a form of caching that would help performance. However, the big reason to use OOP is to make the code easier to read and maintain. For example, each class provides its own namespace, so names can be reused across different classes allowing for better naming.

A big change is the simple test cases embedded in the solution - the objects know how to perform the work, rather than making direct calls to the raw code. In this case, the tests are trivial, but more complex tests that confirm the data in the object is consistent and contains expected values could be implemented - and the test cases would still be easy to read. As a result, users of the objects describe what they want to do, and not how to do it. As programs get larger, this higher level of abstraction becomes more important, allowing the developer to avoid getting bogged down in the implementation details. OOP is a huge topic, and these small solutions don't require the full OOP treatment - we still access data members directly, instead of using setters and getters to hide the internals; we don't provide pretty printing; we don't use inheritance or polymorphism to provide code reuse; and so on... However, this provides a taste of the OOP features available in Python. Since this pretty much a direct port from imperative programming to OOP, there is some extra overhead that makes it run quite a bit slower, as there is code that is run repeatedly that is avoided in the imperative approach. Given some work (and maybe some redesign), this can be avoided :

04

A little research into computing the day of the week turns up a nice Wikipedia article on determination of the day of the week. By implementing Gauss's Algorithm, we no longer need to iterate each year from 1900 to find the starting date of the current year. This turns the quadratic complexity to linear complexity :

05

While Python includes date/time data types, they are not aware of calendar details (like day of week or number of days in each month). Instead, Python also includes the standard "calendar" library to address these needs. This library even has a function to return the details for a given month and year, which is exactly what we need for this problem - the return value is a tuple composed of the day of the week for the first day of the month, along with the number of days in the month. The resulting code is much simpler - although it appears to have some extra overhead (probably error checking or handling of special cases to make it more robust) :