読者です 読者をやめる 読者になる 読者になる

「遠い昔、はるか彼方の銀河系の カレンダー」問題解答 ( CodeIQ )

CodeIQ コードゴルフ

はじめに

CodeIQというところでプログラミング問題に挑戦しましたので、ネタバレです。今回は類似問題を2つまとめてます。

codeiq.jp codeiq.jp

問題

問題は一種の日暦算であり、与えられた日付から曜日を求めます。ただ、現実の暦ではなく、仮想のキュラ暦/ラゲ暦を扱います。簡単な方はキュラ暦、難しい方がラゲ暦に関する問題であり、ある時点を境に暦が切り替わっているという設定です。

詳細は次の通り。

項目 グレゴリオ暦 キュラ/ラゲ暦
整数 整数 ( キュラ暦は500以上1600未満、ラゲ暦は1600以上 )
1~12の整数 A~Jの英字(11ヶ月)

(平年)
1~31の整数、ただし4,6,9,11月は30まで、2月は28まで 1~32の整数、ただしA,B,D,F,H,I,K月は31まで
曜日 日~土 ( 7種類 ) t~zの英字 ( 7種類 )
うるう年 大体4年に1度 ( 投げやり )
2月の日数が29に増える
キュラ暦はなし。
ラゲ暦の年数が20の倍数 ( ただし80の倍数でない )、もしくは4000の倍数の場合。
E月の日数が31に減る
  • 基準となるポイントとしては、500年A月1日、1600年A月1日がともにt曜日というところ。( キュラ暦の終わりは1599年J月26日 )
  • “年.月.日”の形式 ( 可変桁、ドット区切り ) の1行の入力に対し、キュラ暦/ラゲ暦の曜日を出力する。キュラ暦/ラゲ暦どちらかは問題によって決まっており日付から判断する必要はない。
    ( 例えばキュラ暦の方で“500.A.1”という入力に対しては“t”と出力する。改行は任意 )

余談: キュラ暦が1599年J月26日までという記述を見た時の感想

解説

方針

まあ、現実の暦と同じく曜日が7種類なので、暦を日数換算して$mod\,\,7$の値を考えれば済む…というか、多分それしかないとは思うのですが。

まあざっくり、月のA~Jを0~10と、曜日のt~zを0~6として扱うならば、年・月・日 $y,m,d$ に対して

  • キュラ暦の曜日は $2y+\left[0,3,6,3,6,3,6,3,6,2,6\right]\left[m\right]+d\,\,mod\,\,7$
  • ラゲ暦の曜日は $2y+\left[4,0,3,0,3,5,1,5,1,4,1\right]\left[m\right]+d-\lfloor\frac{y}{20}\rfloor+\lfloor\frac{y}{80}\rfloor-\lfloor\frac{y}{4000}\rfloor\,\,mod\,\,7$ ( ただし、A~E月の場合は年数$y$を1小さくする )

という計算が成立します。( 式中の[] は配列の値選択と見てください )

今回は ( も? ) コードゴルフにチャレンジ的な目標 ( それぞれ 71バイト、117バイト ) があったため、さてこの計算をどう短く実装するか…ということになります。

コード

というわけで、提出したコードです。

まずはキュラ暦版Perl(51)

$/='.';print chr 116+(<>*2+8400135306%(ord<>)+<>)%7

続いてラゲ暦版Perl(89)

$/='.';print chr 116+(($y=<>-(($m=ord<>)<70))*2+1762490546%$m+<>-$y/20%$y*3/4-$y/4e3%7)%7

Perlの場合、特殊変数$/を変更すれば、そこで行の区切りとみてくれますから、<> だけで年・月・日の値を取り出すことができます。

さて。文字数を短くする上でのポイントは、月によって変わる値をどう捻出するか、ですが以下を利用しています。

http://d.hatena.ne.jp/haruya12/20150629 より、

任意の非負整数の有限列 x_0, x_1, \cdots, x_m に対して、正整数 n, a, b を適当に取って、 \Large x_k = n\,\bmod\,(ak+b)\hspace{50pt}(k=0,1,\cdots,m)
とできる(mod は剰余の2項演算子)。

まあ要するに、適当な値を見つけて月数 ( ここでは文字コードを直に利用 ) での余りを取れば、ちょうど配列の値を作り出すことができるわけですね。なお $mod\,\,7$ 上で等しければよいので、余りの範囲として0~6に収める必要はありません。

終わりに

解いたのは昨年末のことだったので結構忘れてました。締め切りが長いとなかなか悩ましいところですね。月の所の値の作り方、もっと短くできそうな気もするのですが…。どうなんでしょうか。

(2016/3/26追記)

出題者の@Nabetaniさんの記事が公開されました。

nabetani.hatenablog.com

その中にある@stephen_doleさんの解答をアレンジすると、Perl(48)まで縮まるようです。

小数をかけて+2か。うーん思いつかなかった。( これ実は+0で済まそうとすると、途端に見つからなくなるんですよね )

(追記終わり)