Search for the day of the thirteenth of each month for several years

Question

I'm currently trying to solve some problems on the USACO training website in preparation for unrelated competition in C ++.

However, I am stuck in this problem:

Is the 13th of a month on Friday Friday less common than on any other day of the week? To answer this question, write a program that will calculate the frequency that the 13th of every month lands on Sunday, Monday, Tuesday, Wednesday, Thursday, Friday and Saturday for a certain period of N years. The time period for testing will be from January 1, 1900 to December 31, 1900 + N-1 for a certain number of years, N. N is non-negative and will not exceed 400.

The number N is provided in the input file, and the output should be a file with seven numbers in it, each of which represents the number of the 13th fall on a specific day of the week.

I was wondering how you guys approach this issue. I'm not looking for code or anything else, as this will simply defeat the goal of my execution, instead, only the starting point or algorithm will be useful.

So far, the only thing I could think of was to use the Doomsday Algorithm, however, I'm not sure how to implement it in the code.

Any help would be greatly appreciated.

Answer 1

As Denny says, N is so small that you can easily iterate over months using a days-per-month table, and a simple “a-leap-year” predicate to handle February. Just find out what day January 13 was in 1900, and then add the days past until February 13, then March 13, etc. Use the % operator to wrap the number of elapsed days back to the day of the week value.

Answer 2

N is less than 400? you just need to go 365.25 * 400 = 146100 days at max. it sounds easy to list everything, convert dates to year / month / date (with your favorite date conversion program), testing for a day of the week is trivial.

I would pre-compute the table.

Answer 3

Just use brute force. Pseudo- code example:

 from datetime import date day_names = ['Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday', 'Saturday', 'Sunday'] counts = [0] * 7 for year in range(1900, 2300): for month in range(1, 13): counts[date(year, month, 13).weekday()] += 1 for day, count in zip(day_names, counts): print('%s: %d' % (day, count)) 

The hard part calculates the day of the week on which the date falls . In C (++), you can use mktime and localtime if you know that your platform handles a fairly wide range of dates.