問題
https://codeiq.jp/q/2597
https://codeiq.jp/q/2598
概要
特殊な暦(キュラ歴・ラゲ歴)で、与えられた日の曜日を答える問題。
ABDFHIK月は31日、CEGJ月は32日。ただしラゲ歴の閏年(4000で割りきれるか、20で割り切れかつ80で割り切れない)はE月が31日になる。
問題文通りに実装すれば正解できるが、問題は、 バッジを獲得するには短いコードを書く必要がある (71/117バイト以下)ことにある。
戦略
数学的に曜日を求める式が得られれば繰り返しなしに解くことができる。つまり、コード量を大幅に削減できる。
普通の暦であれば、ツェラーの公式を使えばよいが、今回は暦が違う。よって、キュラ歴・ラゲ歴でのツェラーの公式に相当するものを求める必要がある。
方法
ツェラーの公式
いきなり問題を解くのではVerifyが大変なので、まず普通の暦でツェラーの公式を求めてみることにする。
まず、配列bに当該月までの累計日数を代入する。ただし2月は閏年か否かで日付けが異なるので、最初の要素を3月とする。
b=[];x=0;11.times{|i|b<<(x+=30+0b011010110101[i])} # 最上位=2月
# => [31, 61, 92, 122, 153, 184, 214, 245, 275, 306, 337]
3月までの日数は31、4月までは61、5月までは92…といった具合である。
次に、公式を見ると、その年までの日数以外は、n*(MONTH+start)/d-diffという形になっていることがわかる(MONTHは0から始まるとする)。d、start、nを決定するとdiffはn*start/d-b[0]により得られるので、先述の式が0〜11のすべての場合においてbと一致するようなd、start、nを適当な閾値を設定して全探索すればよい。
コードを示します(変数mはnのことです)
(1..1/0.0).each{|d|
STDERR.puts '[*] %d'%d
(1..6).each{|st|
m=1
m+=1 while m*st/d<firstday
while m*st/d<firstday+200
diff=m*st/d-firstday
a=b.size.times.map{|i|(m*(st+i)/d-diff)} # (i-1)月までの日数
if a==b
p [m,st,d,diff] # [153, 5, 5, 122]
exit
end
m+=1
end
}
}
ここで、本来1年は2月始まり(0-indexed)であるが、プログラムは0月始まりとしている。月を2〜13ではなく0〜11に読み替えて処理する。
x,y,z=2016,3-1,24
(x-=1;y+=12)if y<2
p (31+28+365*(x-1)+x/4-x/100+x/400+z+153*((y-2-1)+5)/5-122)%7
# => 4
木曜日と求めることができた。
キュラ歴
b=[];x=0;10.times{|i|b<<(x+=31+0b01001010100[i])}について探索すると、[220, 1, 7, 0]が導かれる。
よって、(345*(x-500)+z+220*((y-1)+1)/7+6)%7が答えとなる(+6は、u曜日開始からt曜日開始への変換)。
式を整理して入力部分を付けると以下のようになる。
x,y,z=gets.split(?.);putc (x.to_i*2+z.to_i+220*(y.ord-65)/7)%7+116
66バイトとなり、バッジ要件を満たすことができた。
ラゲ歴
b=[];x=0;10.times{|i|b<<(x+=31+0b00100010010[i])} # 最上位=E月について探索すると、[219, 3, 7, 62]が導かれる。月を5〜15ではなく0〜10に読み替えて処理する。
(31+31+32+31+31 + 345*(x-1600)-x/20+x/80-x/4000+z+219*((y-5-1)+3)/7-62+6)%7 (0<=y<=10)を整理すると以下のようになる(普通の暦と閏年に関する符号が逆なことに注意)。
x,y,z=gets.split(?.)
x=x.to_i
y=y.ord-68
(x-=1;y+=11)if y<2
putc (6+2*x-x/20+x/80-x/4000+z.to_i+219*y/7)%7+116
110バイトとなり、バッジ要件を満たすことができた。
まとめ
ツェラーの公式について深く学ぶことができた問題だったと思います。しかし、昔はコンピュータがなかったので、試行錯誤が辛かっただろうなぁと思いました。