最近、CodeIQというサイトの「今週のアルゴリズム」を解くのが楽しい。元々私はこういうアルゴリズム問題を解くのが非常に苦手なんですが、まあこの「今週のアルゴリズム」の問題は簡単だし。20分とはいえないかもしれないけど1時間もかかんない感じだし。
で、この問題
第2回「今週のアルゴリズム：日付の2進数変換」解説 #ruby｜CodeIQ MAGAZINE
日付を例えば2013年12月7日なら20131207という整数値にして、それを2進数に変換して、そのビット列が左右対称になるような日付を、1964年10月10日から2020年7月24日までの間で全て列挙しろ、と。
解き方はおおまかに2種類あって、
(案1) 1964/10/10から日付を加算しながら、数値や2進数に変換して対称の判定をする。
(案2) 左右対称なビット列を列挙して、それぞれが日付として解釈できるかを判定する。
案1の方はまあ簡単です。ああでもHaskellで書いたんで、10進2進変換を自前で書かなきゃいけないのが面倒だった。「日付+1日」というのも無くて、これは+1すればいいだけなので簡単だったんだけど、Rubyにすりゃよかったとちょっと思った。
探索空間は60年分くらいあるのでちょっとアレだが、1年400日としても2万4千個くらいになると見積もった。
案2の方は、左右対称なビット列を作るのが若干面倒だし、Haskellだと文字列を日付として正しいかどうかを判断するのが結構面倒（Data.Time.parseTimeが19656617を平然と1965年12月31日と読んだり。Rubyにすりゃよかった）なので採用しなかったんですが、解説によるとこっちの方が圧倒的に速いらしい。
私の感覚的には10進8桁は30ビット弱くらいだから、左右対称なので半分の15ビット弱くらいになって、まあ3万もいかないだろうけどもどっこいどっこいかなぁと思ったんですが。
本当に簡単だったので案1で5分くらいで書いたと思う。
フィードバックのメールを見ると、アルゴリズム問題なのでできるだけ速い案2で解いて欲しかったと書いてあって、そこまではまあそりゃそうだなんですが、模範解答で「19641010から20200724までは2進数にすると25桁で、12桁と真ん中1桁、12桁も全て1001から始まるので8桁+真ん中1桁の合計9桁、512個の数字を調べればいい」というようなことが書いてあった。
いや、そういうの考えるのが面倒だからコンピュータを使っているんじゃないのか。それにそんなこと言ってたらどこをとっても再利用できないプログラムができてしまうんじゃないか。一般化されてないコードを書くのは苦痛じゃないのか。
と思ったけどもよく考えたら問題文にプログラミングで解決しろとは書いてなかったのでどっちでもよかった。実際過去問見たら手計算で解いてる人もいるみたいだし。
ということでこれはただの自己主張なんですが、私は頭を使うのが面倒なのでコンピュータを使っています。あと、性能より一般化だ。遊びならなおさら。
私はアルゴリズムの高速化問題には向いてないかもしれない。
それはそうと、試しに案2の方も実装してみました。パーサを改造してちゃんとした日付しか読まないようにするのは簡単だったというかパース後の文字列比較で簡単にやった。左右対称なビット列を作るのは意外に面倒でした。小さい順に並べようとすると偶数桁の時と奇数桁の時で分けないといけないし、桁上りのタイミングを見ないといけないし。どうなんだろう。
でもそれらができれば簡単だし、速かった。いやちゃんと測ってないですけど、4倍くらい？ 0から20200724までの対称なビット列の数は9027個しかなかった。これだけでも案1の日付数え上げの半分弱くらいで、19641010以上だと137個だから8890個は日付の判定までもいかないから、そりゃ速いわ。
誰か私の代わりにこういうの考える役をやってください。
これコードのネタバレいつまでダメなんでしょうね。
