Arantium Maestum

プログラミング、囲碁、読書の話題

IT速報

簡単な硬貨問題 from IT速報4

前回からの続き 「随分とダサいコードを書いてるのね」と某IQ145の女子高生*1に言われた気がしたので考え直してみたら、こうなった。 (def coins [500 100 50 10 5 1]) (defn coin-divide [n] (map quot (reductions rem n coins) coins)) 一つの直線で全部…

簡単な硬貨問題 from IT速報3

前回 まあこれもありかも。 (def coins [500 100 50 10 5 1]) (defn f [[remainder & count-list] coin] (concat ((juxt rem quot) remainder coin) count-list)) (defn coin-count2 [n] (->> coins (reduce f (list n)) next reverse)) reduceの戻り値を、…

簡単な硬貨問題 from IT速報2

前回 ふと気づいたのだが、この問題ってreduceじゃなくてreductionsで書けば、「fの中でvectorを作成してそれを戻り値のvectorに入れて・・・」というvector入れ子状態を避けられる。 (def coins [500 100 50 10 5 1]) (defn f [[last-count remain] coin] (…

簡単な硬貨問題 from IT速報

Project Eulerをブログ用に解いていると、 答えを出す 2.高速化 3.コードの美化 の順番でかなり書き直しが必要なので、ただ単に解き散らかすのに比べてべらぼうに時間がかかる。 息抜きにIT速報を見ていたら、タイムリーなことに硬貨関連の問題が出ていた。 …

Python 覆面式ソルバー 終

前回からの続き。 そうこうしているうちに、ついにルール追加である。 以下の二つのルールを追加する。 二つの数の和の一番上の桁に関するルール 二つの数とその和の同じ桁に関するルール その前に、足し算と引き算でルールをケース分けするのはめんどうなの…

Python 覆面式ソルバー 続続続

前回からの続き。 てなもんで、再帰的に書いたソルバーに、各段階で次のステップに使える数字を絞るルールを組み入れる仕組みを作っていく。 方式としては、入力された文字列を引数にして評価関数を返す高次関数create_rule(input_string)を作成する。その返…

Python 覆面式ソルバー 続続

前回からの続き。 というわけで総当たり形式をやめて、なるべく制約を加えることで評価する文字:数字マッピングの総量を絞ってみる。 具体的には for numbers in permutations(range(10), len(characters)): この部分をやめるわけである。じつはこの部分も…

Python 覆面式ソルバー 続

前回からの続き。 ということで高速化に取り組んでみる。 が、その前に、とりあえず短く書いたコードが実際どれくらいかかっているのか、数値化しておく。 import time def time_solver(input_string): start = time.time() solve(input_string) end = time.…

Python、再帰とダイナミック・プログラミング 微調整

以前書いたこのエントリーの最後のコードだが zehnpaard.hatenablog.com H = {0:0} for n in xrange(1, 2016): H[n] = n - H[H[H[n-1]]] print H[2015] 書いた直後から、そもそも数字がkeyならdictionaryじゃなくてlistでよくないか?と気になっていた。(が…

Python 覆面式ソルバー

気がついたら前回の更新から四半期が過ぎようとしている。恐ろしいことだ。 IT速報でまた面白そうな問題があった。 blog.livedoor.jp 複数の文字が同じ数字にマップしないと仮定するなら、そもそも問題の大きさが最大で10!(~360万通り)なので、ちょっと時…

Python、再帰とダイナミック・プログラミング

IT速報で以下の記事があった。Pythonでの解き方を少し考えてみた。 blog.livedoor.jp 数列Hが以下のように定義されているとき、H(2015)を求める。 H(0) = 0 H(n) = n - H(H(H(n - 1))) (n > 0) 再帰で書くならかなり簡単である。 def H(n, memo={0:0}): if n…