数を構成する数字を階乗したものの和で作る数列の長さを求める問題です。
3 -(3!)> 6 -(6!)> 720 -(7!+2!+0!)> 50402 -...
これをそのままやっては終らないので、別の方法を考えたのですけど、思いつかないし、改善方法は思いついたので、それで実装。
2分ちょいかかります。
この数列、どこかで必ずループするらしいのです。
a -> b -> c -> x -> y -> z -> x ...x,y,zのところがループになってます。このときaの数列の長さは6です。
この構造を前提に計算結果をキャッシュすることで、無駄な計算を省きます。
以降、aの数列の長さをF(a)とします。
その1 ある数を計算したら、そこにつながる数の結果に利用できる。
たとえば、nの数列にaが出てきたとします。
n -> m -> o -> aこの先はb,cと続くことになり、この先は5つ数の列があることになります。
結局、F(n)は6+3で9ということになります。
その2 ある数を計算したら、その数列に含まれる数の結果も得られる。
aを計算すればb,c,x,y,zの結果も出たことになります。
F(b)は5、F(c)は4になります。
xとyとzはループの中なので、どれも同じF(x)=F(y)=F(z)=3になります。
また、この結果は、その1の情報にも使えます。
g -> h -> yになれば、F(g)は2+3で5です。
その3 数字の階乗の和の性質1
F(123)とF(321)は、構成する数字が同じなので同じです。3桁であれば6通りですが、6桁だと720通りあります。
これを使って、
- 階乗の和の計算は、ソートした数のリストの関数と定義して、メモ化で効率を上げます。
- (もう一工夫 後述)
その4 数字の階乗の和の性質2
0!と1!はどちらも1なので、1を含む数は、それを0と置き変えたものと同じ値になります。たとえば、F(321)とF(320)は同じ値になります。これを使って効率化できます。
が、面倒だったので実装しませんでした。
初めの実装は、ツイッターで「メモ化を使えばDPが簡単に実装できる」ってのを見て「これこれ」と思って始めたのですが、その2以降を実装するために結局こっちに持って来てしまいました。ので、トップレベルの(let の部分はメモ化の構造から取っています。
おまけ もう一工夫について
これも実装はしませんでしたけど、数字の並びが同じものは基本的に数列の数も同じになります。
a -> b -> c -> x -> y -> z -> x ...このときF(a)は6ですが、同じ数字でできているある数をa'とすると、こうなる
a' -> b -> c -> x -> y -> z -> x ...ので、F(a')も6です。
でも、たとえば、xと同じ数字でできている数x'の場合は、こうなります。
x' -> y -> z -> x -> y ->...x'はループに入っていないのです。
なので、F(x')=F(x)+1=4になります。
たとえば、F(123)が求まれば、この方法でF(132)、F(123)... の値も求めてキャッシュに入れてしまえばいいのですが、上記の判断のところが面倒なのでやめました。
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| ;; Problem 74 : 2011/12/14 | |
| ;; "Elapsed time: 135291.687352 msecs" | |
| (defn factorial [n] | |
| (reduce * (range 1 (inc n)))) | |
| (defn-memo sum-of-factorial [num-list] | |
| (reduce + (map factorial num-list))) | |
| (defn exists [tgt col] | |
| (some #(= tgt %) col)) | |
| (defn get-loop [key col] | |
| (let [loops (drop-while #(not= key %) col)] | |
| (if (empty? loops) | |
| false | |
| [loops | |
| (take-while #(not= key %) col)]))) | |
| (let [mem (atom {})] | |
| (defn mem-set-count-loop! [loop-list] | |
| (let [loop-cnt (count loop-list)] | |
| (dorun (map #(swap! mem assoc % loop-cnt) loop-list)))) | |
| (defn mem-set-count-stem! [stem-list base] | |
| (dorun (map #(swap! mem assoc %1 (+ base %2)) | |
| (reverse stem-list) (iterate inc 1)))) | |
| (defn count-74-link [num prec-vec] | |
| (if-let [cnt (get @mem num)] | |
| (do (mem-set-count-stem! prec-vec cnt) | |
| (+ cnt (count prec-vec))) | |
| (let [next-num (sum-of-factorial (sort (num-to-list num))) | |
| new-vec (conj prec-vec num)] | |
| (if-let [[looping stem] (get-loop next-num new-vec)] | |
| (do (mem-set-count-loop! looping) | |
| (mem-set-count-stem! stem (count looping)) | |
| (count new-vec)) | |
| (recur next-num new-vec))))) | |
| ) | |
| (defn pe-74 [lmt] | |
| (count | |
| (filter #(= 60 %) | |
| (map #(do (count-74-link % [])) (range 1 (inc lmt)))))) |
- factorial
累乗の計算。 固定値を返すようなものでも試してみましたけど、あまり効果なし。
1～9までしか使わないからあたりまえですね。
- sum-of-factorial
リストにはいっている数の累乗の和を求める。
- exists
リストにtgtが存在するかどうか。someを使っているので、無いときはfalseでなくてnilが返ります。
- get-loop
リストがループしていれば、ループとへた(ループに入る前の部分)に分けます。
[a b c x y z] なら [[x y z] [a b c]] が返ります。
ループしていなければ、falseが返ります。
- (let [mem (atom {})]
memがキャッシュの保存場所です。
([32768 42] [65536 39] [98304 15] [131072 36] [163840 39] ...
こんな風に、[数字 列の長さ]のハッシュになっています。
- mem-set-count-loop!
その2のループ内の数のキャッシュを保存します。
- mem-set-count-stem!
その2のへたにある数のキャッシュを保存してます。
- count-74-link
メイン関数です。再帰処理をしますので、注目中の数(num)とそれより前の数列(prec-vec)を引数に取ります。
最初に呼ぶときは、前の数列は空です。
- numがキャッシュにあるかどうか調べます。
キャッシュにあれば、numとそれより前の数列について、その2に沿ってキャッシュにデータを入れ、キャッシュの値と前の数列の数を足したものを返します。
- キャッシュに無ければ、次の数(next-num)を計算し、numをリストに入れます(new-vec)
- リストがループしていれば数列が求まったので、その2に沿ってキャッシュにデータを入れ、数列の要素数を返します。
- ループしていなければ、next-numとnew-vecで再帰します。
- pe-74
1からlmtまでの数について、count-74-linkを呼んで、答が60のものをすべて数えます。
0 コメント:
コメントを投稿