19問目

以下のような情報があります. また, 各自で調査しても良いでしょう.

• 1900年1月1日は月曜日.
• 小の月は9月, 4月, 6月, 11月. 残りは2月を除いて大の月. 2月は通常は28日だが, 閏年では29日.
• 閏年は, 4年に1度あり, 100年に1度は閏年でなくなり, さらに400年に1度は閏年になる.

20世紀(1901年1月1日から2000年12月31日)にはいくつの1日が日曜日になるか?

http://projecteuler.net/index.php?section=problems&id=19

問題とは関係無いが, ソースを書いていて気付いたのは, 「朔日」(ついたち)に当たる英単語が無いこと. ユリウス暦もグレゴリオ暦も太陽暦に分類されるからなのかなぁ?

さてこの問題では, 例外を含む周期的な数列の数え上げをどうコーディングするか?というのがテーマでした. 20世紀をある単位の繰り返しに分割し, その1周期の「最初の曜日」とその1周期の間での「1日の日曜日の数」の関係を配列に持っておいて, 次の周期との曜日のずれを計算しつつ1日の日曜日の合計を求めるという方針で行きました.
周期の候補としては1年, 4年, 100年, 400年という4種類の周期が考えられますが, 人間に分かりやすいということから1年を採用しました. 4年ごとにしても良かったのですが, 上記の配列の意味が分かりづらくなるので止めました.

#include <stdio.h>
#include <stdlib.h>

enum day {sun, mon, tue, wed, thu, fri, sat};
const enum day JAN_1st_1901 = tue;
const int N_DAYS_IN_YEAR = 365;
const int N_DAYS_IN_LEAP_YEAR = 366;
#define N_DAYS_IN_WEEK 7
/*
 * differences January 1st and the first day in each month.
 */
const int firstDays[N_DAYS_IN_WEEK] = {2, 1, 1, 3, 1, 2, 2};
const int firstDaysInLeapYear[N_DAYS_IN_WEEK] = {3, 1, 1, 2, 2, 1, 2};

const int FIRST_YEAR_IN_19TH_CENTURY = 1901;
const int FIRST_YEAR_IN_20TH_CENTURY = 2001;

int solveVer00();
int isLeapYear(int);
enum day nextNewYearsDay(int, enum day);
int numOfFirstDaysOfSunday(int year, enum day newYearsDay);

int main() {
	fprintf(stdout, "Solution: %d.\n", solveVer00());
	return EXIT_SUCCESS;
}

int solveVer00() {
	int result;
	int year;
	enum day newYearsDay;

	for (year = FIRST_YEAR_IN_19TH_CENTURY, newYearsDay = JAN_1st_1901, result = 0;
		 year < FIRST_YEAR_IN_20TH_CENTURY;
		 newYearsDay = nextNewYearsDay(year, newYearsDay), year++) {
		result += numOfFirstDaysOfSunday(year, newYearsDay);
	}

	return result;
}

int numOfFirstDaysOfSunday(int year, enum day newYearsDay) {
		if (isLeapYear(year)) {
			return firstDaysInLeapYear[(N_DAYS_IN_WEEK - newYearsDay) % N_DAYS_IN_WEEK];
		} else {
			return firstDays[(N_DAYS_IN_WEEK - newYearsDay) % N_DAYS_IN_WEEK];
		}	
}

int isLeapYear(int year) {
	return year % 4 == 0 && (year % 100 != 0 || year % 400 == 0);
}

enum day nextNewYearsDay(int year, enum day thisYears) {
	if (isLeapYear(year)) {
		return (thisYears + N_DAYS_IN_LEAP_YEAR) % N_DAYS_IN_WEEK;
	} else {
		return (thisYears + N_DAYS_IN_YEAR) % N_DAYS_IN_WEEK;
	}
}