Google Code Jam Japan 2011 - 練習問題A.数珠繋ぎ

アルゴリズム Google code jam jsdo.it JavaScript

Google Code Jam Japan 2011 - 練習問題A.数珠繋ぎ を
JavaScript と HTML でやってみた

ではさっそく恒例（？）の言い訳タイムです。

その前にお願い

IEではlargeで実行しないでください！
処理重すぎて本当にやばいですから！（そんなもんつくるなよ




Google Code Jam Japan 2011 - 練習問題A.数珠繋ぎ - jsdo.it - share JavaScript, HTML5 and CSS

はい。
そんな危なっかしい代物です。

問題自体のアルゴリズムのほうは結構前にできてました。紙の上では。
それを今日やっとJavaScriptで動くようにしたわけですが、そこでいろいろとトラブル発生。


問題自体の方は
紙の上に書いている中で snapper のスイッチが切り替わる法則見つけました。
4つ繋げた絵を書いてスイッチが切り替わる順番をひたすら書いているうちに

「これ2進数じゃん！」と

そして電球がつくと次には最初のすべてOFFの状態に戻る。
これで一周。あとは同じ変化パターンの繰り返し。
snapper を N個繋いだ時は 2のN乗で一周するってわけです。
実際一周するとまた全OFFに戻るから、その1回前だと電球がついてるんですけど。

あとはこれを式にするだけ。
本体の方は結構自信あったんです。
それなりに早いと思ったんです。

だがしかし！
JavaScript で上手く書けないorz

まずべき乗で躓きましたｗ

2 ** n

…ってJavaScriptじゃこの書き方使えないのかよorz
COBOLの癖がｗ

普通の演算子が使えないのでどうしたものかと思ったら
数学関数とかいう便利なものがあるんですね。

Math.pow(2, n)

数学関数愛してる！

乏しい知識を総動員して、こんな感じに書きました。 

//何回指を鳴らすとsnapperのON,OFFパターンが一回りするのか
//最初に電球がつく（厳密に言うとついて消える）のは何回目か
    cycle = Math.pow(2, n);
    //それをもとに点灯するかチェック
    if (k % cycle === cycle - 1) {
      result = 'ON';
    }

指を鳴らす回数 K が snapper の変化サイクルの 倍数マイナス1か
って感じのことをチェックしています。
もしそうなら電球が点灯するので、結果にONを代入。

ここまではそれなりによかった。
最後の予想外の難所

結果の出力

    // 結果を出力します
    document.getElementById(<SPAN class=str>'output'</SPAN>).value += ('Case #'+ i + ': ' + result + ret);

これがいけなかったorz
一行ずつどんどん書き足していこうって発想が間違いだった
JavaScript的にはものすごく効率が悪いことらしく
IEでlargeテストケースで実行するとしばらく応答しなくなるとかいう恐ろしい事態に…

指摘されていい方法を教えてもらいましたよ


forked: Google Code Jam Japan 2011 - 練習問題A.数珠繋ぎ - jsdo.it - share JavaScript, HTML5 and CSS

まず配列に入れてそれを最後に結合するといいらしい
この違いで処理速度が全然ちがうんだもんなぁ…

1400msec が
11msec になった！！
IEでも普通に45msec くらいで実行できた！

書く人によってこれだけ違うんだねぇ
いや…ボクの知識がアレすぎなんだろうけど

ちゃんと言語の勉強も真面目にしなきゃなーと思う出来事でしたよ