Euler Problems
January 29th, 2010
A collegue showed me the Project Euler website, a site with interesting and challenging problems to solve using a programming language of your choice. The fun part in most of these problems is to find a smart way to solve it rather than brute-force your way to a solution.
Take this challenge: how many months in the 20th century began on a Sunday? Remember that the 20th century began on January 1st 1901, and ended on December 31st 2000.
There are a few ways of solving this. Given VB.Net you’d be tempted to iterate through all years and months of the 20th century and use the built-in methods to get the day-of-the-week for each month. Then simply keep track of how many Sundays you find. But that’s not very satisfactory smart-wise.
Let’s say you have a language that does not have this built-in support. All you have is the number of days in each month, a way to determine if a year is a leap-year, and a reference point: January 1st 1900 was a Monday.
The solution I developed is simply stated:
- let Monday be day 0
- add the number of days in the month ahead to this day
- divide by 7
- the remainder is the new day of the week
- if the remainder is 6, we have a Sunday as 1st day of the month
- repeat until we reach January 2001
The tricky things about this particular puzzle as it appears on the Project Euler, is that the reference point is given as January 1st 1900, which is a year outside of the 20th century. You must also take leap-years into account.
To deal with these things you must keep track of which month you are currently investigating, and which year you are in. You need these to determine if you are in a leap-year and to be able to adjust for 29 days in February. You also need the year to both begin and end counting Sundays.
If you feel so inclined, you can register at Project Euler and submit your own solution. There are lots more problems to solve, some of them easier but most of them slightly harder than this one.
Here is the main method I used (VB.Net), without the setup (defining days for each month, etc.) and supporting methods for figuring out if a given year is a leap-year.
Dim NumberOfSundays As Integer = 0
Do
If (thisDay = 6 And thisYear > 1900) Then NumberOfSundays += 1
If IsLeapYear(thisYear) And thisMonth = 1 Then
thisDay += 29
Else
thisDay += (DaysInMonth(thisMonth))
End If
thisDay = thisDay Mod 7
thisMonth += 1
If thisMonth > 11 Then
thisMonth = 0
thisYear += 1
If (thisYear = 2001) Then Exit Do
End If
Loop
Return NumberOfSundays
End Function
My name is Marco Hokke. My blog is about the things that interest me and things I might forget if I would not blog them.
Leave a Reply