Y箱

GCJJ運営からメールが来て、予選の問題の解説が掲載されたらしい。

でも、くやしいから自分で納得できる解答ができるまで見ないよ。
見ないみない。

Code Jam Japan予選のA問題。当日終ってから考えたロジックを実装してみた。
結果は上でき。 ということで、解説です。




その方法は、逆順でのトレース。
知りたい場所のカードが初めにどこにあったのかを考えるわけ。
図を書いたので、貼りつけ。


ソースはこれ



なんと、1秒以下で答がでた。

今日は環境を調えて、6時間みっちり Code Jam やりました。

結局 AとBのSmallだけしか時間内にできなかった。
Cの問題はそれほど時間がかからなそうだったけど、順番に解くのにこだわりたくて、でも、結局だめだったけど。
時間切れ後に、いちおう、CのSmallも解いてみた。

次回は、1つぐらいLargeが解けるようになっていたい。


問題が公開されているんで、一応僕の書いたコードを。



あら。 Gistって修正すると、貼ったやつも変っちゃうんだね。便利なような不便なような。
Gistベースで修正してるので、随時更新されます。
前のを見たい人は、下の方のリンクからGistに直接アクセスしてくださいです(10/7)


問題Aです。
最初は書いてあるとおりに解いた。Smallだと数秒で解ける。
修正版は、Largeでも250ms程度で解けた。 完了。




問題Bです。
最初からいちおうしらみつぶしでないやりかたを模索した。
現在修正中。


問題 C。
時間切れ後に解いた。 問題のとおり。でも、Small解くのに1分半くらいかかってしまう。
そのうち修正。

明日は Google Code Jam Japan に挑戦です。

この週末にProject Eulerのサイトのデザインが変更になりました。

Googleの変更に似た感じになっています。
最近のトレンドなんでしょうか。

僕はまだレベル2なんですけど、レベルを表わすマークも変更されてます。
僕は前の立体の方が好きでしたね、だんだん角が増えていくので、ぱっと見てどんなだかわかるようになってました。 新しいやつは、上下が良くわからなくなってます。 それが狙いなんでしょうね。

最近別件で忙しくて手をつけてませんけど、そろそろ涼しくなってきたことだし、再開しましょうかね。

前にclojureのmemoize関数の動きがだめだっていう話を書きました。
このポストも関心のある方がいらっしゃるようなので、ちょっと追加の情報を。
べつに目新しいものではありませんけど、日本語の情報が無いみたいなので。

さて、 何がだめなのかをくりかえすと、再帰で定義されている関数をmemoizeを使ってメモ化しても、内部での 再帰呼び出しにメモ化が効かないという現象です。
実はこれ、clojureの1.2からのことで、1.1では問題なく動きます。 

これは、以下に出てくる解決策から考えると、1.2で、関数の名前の解決方法に変更があったためだと思われます。

以下ちょっと長くなります。




例によってフィボナッチ数を求める関数を再帰を使ってで定義して、1.1環境で実行してみます。

user> (clojure-version)
"1.1.0"

(defn fib [n]
  (do
     (println "Called with : " n)
     (if (<= n 1)
        n
        (+ (fib (dec n)) (fib (- n 2))))))


user> (fib 5)
Called with :  5
Called with :  4
Called with :  3
Called with :  2
Called with :  1
Called with :  0
Called with :  1
Called with :  2
Called with :  1
Called with :  0
Called with :  3
Called with :  2
Called with :  1
Called with :  0
Called with :  1
5

再帰的に呼ばれているのが分ります。 これを、memoize関数でメモ化しして、同様に呼んでみます。

(def fib (memoize fib))

user> (fib 5)
Called with :  5
Called with :  4
Called with :  3
Called with :  2
Called with :  1
Called with :  0
5

1.2で実行したときに出て来ていた(fib 1),(fib 2),(fib 3) が出てきません。メモにヒットして関数が呼ばれなくなったためです。memoizeちゃんと動いています。

同じことを1.2でやると、このようにはなりません。 (前のポスト参照)

この問題について、前回僕はマクロを作って解決したわけですが、他にこんな方法もあります。 

まず、メモ化する関数の定義を変更します。

(defn fib2 [n]
  (do
     (println "Called with | " n)
     (if (<= n 1)
        n
        (+ (#'fib2 (dec n)) (#'fib2 (- n 2))))))

このように再帰で呼ばれる関数名に「#'」をつけます。(なんでこうするのかについての考察は後で) そして1.1の時と同様にメモ化すればOKです。

やってみます。

user> (clojure-version)
"1.2.1"

(defn fib2 [n]
  (do
     (println "Called with : " n)
     (if (<= n 1)
        n
        (+ (#'fib2 (dec n)) (#'fib2 (- n 2))))))

user> (fib2 5)
Called with :  5
Called with :  4
Called with :  3
Called with :  2
Called with :  1
Called with :  0
Called with :  1
Called with :  2
Called with :  1
Called with :  0
Called with :  3
Called with :  2
Called with :  1
Called with :  0
Called with :  1
5

(def fib2 (memoize fib2))

user> (fib2 5)
Called with :  5
Called with :  4
Called with :  3
Called with :  2
Called with :  1
Called with :  0
5

この通り 

さて、じゃあ、これはなんでうまく行くんでしょう
 以下の説明は僕の推測です。1.2の変分を見てもよくわからなくて、 なんとなくしか理解できてなくて、今一つ現象を性格に捉えられていない。 
 間違っていたら指摘ください 


 関数が再帰的に呼ばれるとき、1.1では、「関数が評価される時点でこの名前を持っている関数を呼ぶ」という仕組みだったものが、1.2では「定義時点この名前が差している関数を呼ぶ」という方式に変更になった。
そのため、1.2では、初めの関数そのものが再帰で呼ばれてしまい、memoizeがうまく動かなくなってしまった。 

この解決策でつかった「#'」はリーダーマクロで(var xxx)の略。「この名前のvarを取得する」ということを意味している。 なので、1.1の時と同じ定義をさせることができるのです。

推測ここまで


 さて、この方式はちょっと気に入らない。
だって、メモ化するつもりの関数はあらかじめ定義をそれ用に書いておけってことになってしまうわけで、 たとえば、あとから、「あ、これメモ化してほうがいいな」と思った場合、関数定義に手を入れることになってしまう。
だったら、僕の作ったマクロで再定義しちゃったほうが手間は少ない。 

ということで、僕はこの方法は却下。
勉強にはなったけどね。

clojure関連のサイトを見ていたら、ソースコードの表示にgist使っているような感じのものがあった。
調べてみたら、gistでそんな機能を提供してるらしい。 しらなかった。

んで、使ってみた。



どうだろ？ あれ？ シンタックスハイライトは無いのかな？

と思ったら、ファイル名に拡張子、この場合cljを指定してやったら、出た。

これ、いいじゃない。
ProjectEulerはこっちでやろうかな。