miauのブログ

はてなダイアリー「miauの避難所」をはてなブログに移行しました

Google Code Jam 2010 の思い出

Algorithm

ということで、一年遅れで Google Code Jam 2010 の思い出です。予選で終わったのであっさりと書きたいところなんですが、APL とか J言語 とか触ってたことを書いたら無駄にボリューム増えちゃいました。

方針

前回 Perl で苦労したので実行速度に不安がない言語を一つ身につけておきたかったんですけど、本気で学びたいような言語がなかなかない＆新しい言語を勉強する余裕もなくて。今回一つくらいは自分にとって刺激になる言語を触っておこうかな、という感じ。

あと GCJ 2009 の

これが格好良かったので、自分も見習って 6 言語で解くのにチャレンジしようかなという程度。

準備

2010 年の 5/9 8:00〜5/10 8:00 というスケジュールなんですが、大幅に寝坊したりで、準備を始めたのが 5/9 21:00 とか。

準備といっても、まずは新しい言語として何を使うかの選定から。

APL を触ってみる→挫折

いい機会なので、以前から気になっている APL を触ってみました。

APL に興味を持ったきっかけは Developers Summit 2009 のこの講演で。

まず気に入ったのはこの処理の密度。プログラミングしてると「もっと簡単に書ける方法がありそう」なんて思いをすることはたまにあるんですが、そういう方向で新しい視点が得られそうです。

あと使い方を調べたことがあったんですが、

を見ると、Ctrl キー＋ふつうのキーで特殊な記号を入力していく方針みたいです。これってキーストロークだけ見ると IDE や ビジュアルプログラミング言語（VPL）でショートカットキーを駆使してコーディングするときに近い感覚になるんじゃないかなと。絵をアスキーアートで表現するように、ふつうの言語と VPL の中間くらいの感覚で使えるんじゃないかと妄想していたのでした。

上記入門ページの手順でもインストールできますが、INSTALL.BAT は大した処理は行っていないので以下のようにしてインストールすることもできます。

  1. Freeapl.zip を解凍
    • 更新日時が 1997年なんだけど大丈夫なのかな・・・
  2. FREEAPL\RUN をインストール先（デフォルトだと C:\freeapl ）にコピー
  3. FREEAPL\RUN\FREEAPL.INI を C:\WINDOWS にコピー
    • もしインストール先を変更したなら FREEAPL>INI 内のパスを書き換え
    • ついでに以下の設定を追記してもいいかも（一度フォント設定ダイアログを開いてキャンセルしたときのでかい文字設定です）
screenfont=APL2741
screenfontsize=36

で、動作させると・・・あれ。ふつうに動いちゃいました。

去年いじったときは、

  • 「パスが不正」系のエラーがでてバイナリ書き換え
  • フォントサイズが 35 以上じゃないと表示されないからそのあたりの調整

してもちゃんと動かすことができずに、2 時間ほど試行錯誤した挙句 APL 使うのを諦めたのでした。

そもそも動かなかったので評価対象外でしたが、ちゃんと動いても可読性低いので他人に見せるコードには使えそうにないです。インタラクティブ環境やらワンライナーやらで書き捨てするならいいかもしれません。

J言語 を触ってみる→なんとかいけそう？

ということで、APL の後継である J言語 も触ってみました。とりあえず情報源を羅列します。

ということで、なんとかいけそうな雰囲気ではあったんですが、問題を解き始めてから何点かハマりました。

  • ファイルからの読みこみはどうすればいい？
  • 条件分岐がうまくいかない
    • Control structure に載っているから使えそうなのにエラーになって。「explicit...」でしか使えないのかな？というのが当時の結論だったのですが、正直よくわかりません。
  • ビット演算のやり方がわからない
  • ファイルをスクリプトとして実行するにはどうすればいい？ 
j -jijx hello.ijs

言語の感想としては・・・テーブルの操作が強力で新鮮でした。他の言語では確実にループが必要になる処理が演算子の組み合わせで実現できたりして。あと GCD や LCM が標準関数なのが面白いです。今回は不慣れすぎたのであれですけど、使いこなせばずいぶん面白い言語のような気がします。

欠点は・・・APL よりははるかに読みやすいけど、上に書いたような「4 (32 b.) 1」みたいな書き方がちょっとマジックナンバーっぽくて嫌かなと。

本戦

そんな感じで J の使い方をだいたい理解して、日付が変わって 5/10 1:30 くらいのスタート。残り 6:30 と。

の問題をざっと読んで、

  • A. Snapper Chain
    • 簡単そうだから不慣れな言語やネタ系の言語で解く。
  • B. Fair Warning
    • 最大公約数の問題。BigNum 対応の言語で解くと楽そう。
  • C. Theme Park
    • 計算量が多いから高速な言語を使いたい。何段階か高速化できそうだけどどこまでやったもんだか。

くらいの目星をつけて、作業開始。

ちなみに予選通過ラインは 33pt なので

  • Small 1 つと Large 1 つ解ければ予選が通過できる
  • Small 3 つ解いても 30pt なので通過できない

という感じです。

A. Snapper Chain

ひとつは J で解くとして、もうひとつは .bat でいいかなと。sh で解いてる人がいるくらいだし。

.bat

仕事でも使ってるバッチファイルなんですが、あまり計算はやったことなかったので何点かハマりました

  • if で括弧を使っているから、その中の set /a で括弧を使おうとすると構文エラーになる
    • 文字列にすれば OK
  • set /a で剰余するときに %% する必要あり
  • 遅延展開を使っているから単項演算子の ! も使えない
    • とりあえずロジックを変えて回避

みたいな感じで・・・気がつくと 3:00 くらい。

J言語

上で書いた「条件分岐できない」「ビット演算のやり方がわからない」あたりでハマって、書き上げたのが 5:30 とか。

どっちが速い？

実行時間は J だと 0.375 秒、.bat だと 1.750 秒とかだったので、Small を .bat、Large を J で実行すればいいかなと。そんなわけで .bat 版を post してみると・・・Incorrect。あれ？

・・・というところで一時間くらい処理を見直してみたけど解決せず、A の問題は捨てることに。この時点で 6:30 とか。

B. Fair Warning

もう時間がないので Ruby で解くことにする。比較的あっさり書けたけど、Small を実行すると

fair_warning.rb:5:in `%': divided by 0 (ZeroDivisionError)

とかなんとか。問題文に「ti ≠ tj for some i, j.」とか書いてあるのに

3 81592424 30724059 30724059

なんてケースがあるんですけど・・・。とりあえず 0 除算にも対応して、Small は通過。

Large を動かすと・・・

fair_warning.rb:2:in `p': stack level too deep (SystemStackError)

とか。ひぃぃ。

最大公約数を再帰で求めるところでエラーになっているので、ふつうのループに書き換えて、再度実行・・・したけど間に合わず。もう 1〜2 分あれば間に合ってたんだけど、まあいいや、次。

C. Theme Park

この時点で 7:10 なので残り 50 分。A の問題を読み直すか悩んだけど、C のほうを急いで解くことに。

「速い言語がいいから」とD言語で書きかけたけど、細かいところで書き方を思い出せず。去年のひな形 を使って Perl で解くことに。ここで残り 40 分。

残念ながらここでもハマって。何か変な動作すると思ったら、計算で使ってる $data って変数がひな形の中でも使われてた。そしてサンプルの答えが合わないと思ったら、別グループの人同士も隣に座れる、というのを逆に読んでしまっていた。

そうして書き上げたスクリプトはいちおう Small は通ったけど、Large は時間内に終わらず時間切れ。

反省とか

結局

こんな感じで Small を 2 問解いただけで終わってしまいました。

A の反省

答えが合わなかった原因ですが、解いている最中にいつの間にか問題を勘違いしてしまっていて、思い込みで変なゴールを目指していたみたいです。手元のメモは合っていたし、.bat 版と J 版の答えが食い違っていて考え直したりもしたんですが、そのとき間違った解のほうに突き進んでしまったようで。慣れない言語で書いているうちに混乱した部分もありそうなので、ちゃんと慣れた言語で解くのが重要そうです。（当たり前ですね・・・。）

そんな間違った解答ですが、いちおう gist に置いておきます。

B の反省

Ruby の動作が遅い＆スタックの深さを明示できないのが原因なので

  • 2009 年の反省どおり、高速に動作する言語を使えるようになる
  • 「StackOverflow しないためにループ処理に書きなおし」みたいなことはやりたくないので、末尾最適化を勝手にやってくれる言語を一つ身につける

というのを GCJ 2011 への目標にしてました。

ただこれは勘違いで、前項で書いたように除算で最大公約数を求めればスタックオーバーフローにはなりませんし、Windows の Ruby が極端に遅いというのもありましたので、Ruby は GCJ に向かない、とは一概には言えないのでした。

C の反省

敗因は問題をざっと眺めて理解した気になっていたこと。いつの間にか記憶が改ざんされて誤った問題を解いていた（そのための計算速度向上処理を入れていたけど、後で消すことになったり）のでもったいなかったです。

      • -

ということでようやく去年＆一昨年の内容を吐き出したので、検証が終わったら今年のことを書こうかと。Round2 が始まる前くらいまでには書きたいなぁ。