ザネリは列車を見送った ブログという名の備忘録

今日も今日とてせっせとオイラー。

Problem 13. Large sum

Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.
Problem 13. Large sum

---

以下の50桁の数字100個の和の上位10桁を求めよ.
Problem 13 「大数の和」 (問題文に掲載されている50桁の数字100個は省略)

sum でリストの要素の数値を足して、show で文字列にして take で上位10桁を取る。
(最後に read で再び Num にしているが、これは別に不要のはず。)
…あれっ、これだけ？
うーむ、これはあれだろうか。使用言語によっては大きい数値を扱う型を工夫しないといけないとか、そういうことだろうか。

Problem 14. Longest Collatz sequence

The following iterative sequence is defined for the set of positive integers:
     n → n/2 (n is even)
     n → 3n + 1 (n is odd)
Using the rule above and starting with 13, we generate the following sequence:

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms.
Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.
Which starting number, under one million, produces the longest chain?
NOTE: Once the chain starts the terms are allowed to go above one million.
Problem 14. Longest Collatz sequence

---

正の整数に以下の式で繰り返し生成する数列を定義する.
     n → n/2 (n が偶数)
     n → 3n + 1 (n が奇数)
13からはじめるとこの数列は以下のようになる.

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

13から1まで10個の項になる.
この数列はどのような数字からはじめても最終的には 1 になると考えられているが,
まだそのことは証明されていない(コラッツ問題)
さて, 100万未満の数字の中でどの数字からはじめれば最長の数列を生成するか.
注意: 数列の途中で100万以上になってもよい
Problem 14 「最長のコラッツ数列」

まず、愚直に書いてみるとこうなった。
コラッツ数列を求める関数自体はシンプルに書ける。
maximumBy (comparing length)で要素数が最大のものを取得し、その開始の数値である last を取る。
しかし、999999～1まで全てのコラッツ数列を求めていて、見るからに無駄で遅そうだ…。
実際最適化オプションつきでコンパイルしても10秒近くかかる。
高速化を試みたい。
考えるに、例えば100から始まるコラッツ数列 [～34,11,22,44,88,29,58,19,38,76,25,50,100]を求めていたとすると、
その後50から始まるコラッツ数列は同じ数値からなる[～34,11,22,44,88,29,58,19,38,76,25,50]となり、
100より要素数が大きくなることはないことが分かる。
つまり、数値の大きい方から順にコラッツ数列を求めていき、
その求めたコラッツ数列の中の数値から始まるコラッツ数列は求めなくてもよいので
以下のようにすれば処理の節約になるのではないだろうか？

import Data.Ord (comparing)
import Data.List (maximumBy, (\\))

main = print $ maxCollatz 999999

maxCollatz :: Integral a => a -> a
maxCollatz n = last $ maxCollatz' [] [n, n-1..1]
  where
    maxCollatz' m []       = m
    maxCollatz' m (n:rest) = let c = collatz n in maxCollatz' (maximumBy (comparing length) [m, c]) (rest \\ (filter (< n) c))

-- nからはじまるコラッツ数列(逆順)
collatz :: Integral a => a -> [a]
collatz n = collatz' n [n]
  where
    collatz' 1 ns = ns
    collatz' n ns = collatz' next $ next:ns
      where next | even n    = n `div` 2
                 | otherwise = 3 * n + 1

rest が 999999～1の検査対象の数値だが、一度求めたコラッツ数列の中に含まれる数値はもう求める必要がないので
差集合を取ろうとしている。
速くなるかな…と思いきや、その逆で全く処理が終わらず、最終的に以下のエラーで停止してしまう…。

Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.

要素数の大きいリスト同士の差集合を作ろうとしてスタックオーバーフローになってしまったのだろうか…。

発想を変えてみよう。
ある数値から始まるコラッツ数列を求める前に、その数値が含まれるコラッツ数列をすでに算出済みであれば省く、
ということができないだろうか。
先ほどの例でいうと、50から始まるコラッツ数列を求める前に、
すでに50を含むものは100から始まるコラッツ数列の算出によって算出済みと判断する。
何だか今ひとつ足りていない気がするが、こうなった。
実行してみると、約5秒程度…。速くはなったが、果たしてこの判定で妥当なんだろうか、と違和感が残る…。

Problem 15. Lattice paths

Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down,
there are exactly 6 routes to the bottom right corner.
How many such routes are there through a 20×20 grid?
Problem 15. Lattice paths

---

2×2 のマス目の左上からスタートした場合, 引き返しなしで右下にいくルートは 6 つある.
では, 20×20 のマス目ではいくつのルートがあるか.
Problem 15 「格子経路」

多分経路を求めるのに適した公式なりアルゴリズムなりがあるんだろうな…と思いつつ、
情けないことにそんなものは知らなかったので自力で考えてみた。
愚直にやるとこんな感じか。

route :: (Num a, Ord a) => a -> a -> [[(a, a)]]
route row line = route' [[(0, 0)]]
  where
    route' ls
      | all (\x -> (head x) == (row, line)) ls = ls
      | otherwise =
          let ls' = filter (not . null) $ concat $ map (\x -> let (r, l) = head x in [(proceed x (r+1) l), (proceed x r (l+1))]) ls
          in route' ls'
    proceed x r l | (r <= row) && (l <= line) = (r, l):x
                  | otherwise                 = []

このroute関数は目標地点(row, line)まで右に1マス、下に1マス進む全ての経路を作る。
例題の2×2 のマス目の場合、以下のようになる。

route 2 2
{-
[[(2,2),(2,1),(2,0),(1,0),(0,0)],
 [(2,2),(2,1),(1,1),(1,0),(0,0)],
 [(2,2),(1,2),(1,1),(1,0),(0,0)],
 [(2,2),(2,1),(1,1),(0,1),(0,0)],
 [(2,2),(1,2),(1,1),(0,1),(0,0)],
 [(2,2),(1,2),(0,2),(0,1),(0,0)]]
-}
length $ route 2 2
-- 6

これで20×20 のマス目でもいけるか、と思ったが、route 20 20はとてもじゃないが処理が終わらない…。

発想を変えよう。
全ての経路を保持し続けると膨大な要素数になるので、ある地点までの経路がどれだけあるのかの数も持つようにしてみる。
こちらのroute関数は、右に1マス、下に1マス進み、同じ地点までの経路の個数を summarize 関数で足しあわせていく。
route 2 2の場合、
第1ステップで[(1,(1,0))(1,(0,1))]、(右に1マス進む経路と下に1マス進む経路が1つずつ)
第2ステップで[(1,(2,0))(2,(1,1))(1,(0,2))]、(真ん中の(1,1)に進む経路は、右→下と進んだ経路と下→右と進んだ経路の2つ)
第3ステップで[(3,(2,1))(3,(1,2))]、
第4ステップで[(6,(2,2))]となり、経路の6を求められる。
これと同様に、20×20 のマス目でも高速に算出することができた！