[Project Euler] Problem 19 「日曜日の数え上げ」

次の情報が与えられている.

• 1900年1月1日は月曜日である.
• 9月, 4月, 6月, 11月は30日まであり, 2月を除く他の月は31日まである.
• 2月は28日まであるが, うるう年のときは29日である.
• うるう年は西暦が4で割り切れる年に起こる. しかし, 西暦が400で割り切れず100で割り切れる年はうるう年でない.

20世紀（1901年1月1日から2000年12月31日）中に月の初めが日曜日になるのは何回あるか?

ポイントは, うるう年を求めることと毎月の1日が1900年１月１日から経過した日数を求めることです.

1. うるう年を求める手続きを定義する.
2. 年と月からその月の日数を求める手続きを定義する.
3. 1900年から2000年までの期間で月ごとの日数を求める.
4. 月ごとの日数を足して, 1900年１月１日からの経過した日数を求める.
5. 毎月の１日の日数を７で割り, 余りが０なら日曜日.

手続きは次のようになります.

(require srfi/1)

;; うるう年か判定する
(define (leap? n)
  (or (= 0 (remainder n 400))
      (and (not (= 0 (remainder n 100)))
           (= 0 (remainder n 4)))))

;; 月の日数を求める
(define (days y m)
  (cond ((= m 1) 31)
        ((= m 2) (if (leap? y) 29 28))
        ((= m 3) 31)
        ((= m 4) 30)
        ((= m 5) 31)
        ((= m 6) 30)
        ((= m 7) 31)
        ((= m 8) 31)
        ((= m 9) 30)
        ((= m 10) 31)
        ((= m 11) 30)
        ((= m 12) 31)))

;; 月ごとの日数のリストを求める
(define y-m 
  (apply append
         (map (lambda (y) 
                (map (lambda (m) (list (days y m) y m))
                     (iota 12 1)))
              (iota 101 1900))))

;; 月ごとの日数を足しこんで, 経過した日数を求める.
(define (acc count items)
  (if (null? items) 
      ()
      (let ((head (car items))
            (tail (cdr items)))
        (cons (cons (+ count (car head)) head)
              (acc (+ count (car head)) tail)))))

(define c-y-m (acc 0 y-m))
 
;; 7で割った余りが0なら日曜日
(define ans (filter (lambda (c) (= (remainder (+ (car c) 1) 7) 0))
                    c-y-m))

計算してみます.

ようこそ DrRacket, バージョン 5.3.3 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> y-m
((31 1900 1)
 (28 1900 2)
 (31 1900 3)
 (30 1900 4)
 (31 1900 5)
 (30 1900 6)

 ... 省略 ...

 (31 2000 7)
 (31 2000 8)
 (30 2000 9)
 (31 2000 10)
 (30 2000 11)
 (31 2000 12))
> c-y-m
((31 31 1900 1)
 (59 28 1900 2)
 (90 31 1900 3)
 (120 30 1900 4)
 (151 31 1900 5)
 (181 30 1900 6)

 ... 省略 ...

 (36737 31 2000 7)
 (36768 31 2000 8)
 (36798 30 2000 9)
 (36829 31 2000 10)
 (36859 30 2000 11)
 (36890 31 2000 12))
> ans
((90 31 1900 3)
 (181 30 1900 6)
 (608 31 1901 8)
 (699 30 1901 11)
 (881 31 1902 5)
 (1126 31 1903 1)

 ... 省略 ...

 (35580 31 1997 5)
 (35825 31 1998 1)
 (35853 28 1998 2)
 (36098 31 1998 10)
 (36371 31 1999 7)
 (36798 30 2000 9))
> (length ans)
173
> 

計算は1900年からしていますが, 問題は期間の始まりを1901年１月１日からにしていることに注意が必要です.