Project Euler ( http://projecteuler.net/problem=14 )の問題 14 を解決しようとしていますが、Haskell を使用して行き詰まりました。
数値が十分に小さい可能性があり、ブルートフォースを実行できることはわかっていますが、それは私の演習の目的ではありません. 次の意味を持つ Mapタイプの中間結果を記憶しようとしています。Map Integer (Bool, Integer)
- the first Integer (the key) holds the number
- the Tuple (Bool, Interger) holds either (True, Length) or (False, Number)
where Length = length of the chain
Number = the number before him
元：
for 13: the chain is 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
My map should contain :
13 - (True, 10)
40 - (False, 13)
20 - (False, 40)
10 - (False, 20)
5 - (False, 10)
16 - (False, 5)
8 - (False, 16)
4 - (False, 8)
2 - (False, 4)
1 - (False, 2)
今、別の番号を検索する40と、チェーンが持っていることがわかってい(10 - 1) lengthます。10 を検索すると、長さが 10 であることを教えて(10 - 3) lengthマップを更新するだけでなく、まだ (False, _) の場合に備えて 20、40 も更新したい
私のコード:
import Data.Map as Map
solve :: [Integer] -> Map Integer (Bool, Integer)
solve xs = solve' xs Map.empty
where
solve' :: [Integer] -> Map Integer (Bool, Integer) -> Map Integer (Bool, Integer)
solve' [] table = table
solve' (x:xs) table =
case Map.lookup x table of
Nothing -> countF x 1 (x:xs) table
Just (b, _) ->
case b of
True -> solve' xs table
False -> {-WRONG-} solve' xs table
f :: Integer -> Integer
f x
| x `mod` 2 == 0 = x `quot` 2
| otherwise = 3 * x + 1
countF :: Integer -> Integer -> [Integer] -> Map Integer (Bool, Integer) -> Map Integer (Bool, Integer)
countF n cnt (x:xs) table
| n == 1 = solve' xs (Map.insert x (True, cnt) table)
| otherwise = countF (f n) (cnt + 1) (x:xs) $ checkMap (f n) n table
checkMap :: Integer -> Integer -> Map Integer (Bool, Integer) -> Map Integer (Bool, Integer)
checkMap n rez table =
case Map.lookup n table of
Nothing -> Map.insert n (False, rez) table
Just _ -> table
{-WRONG-} の部分で、次の例のようにすべての値を更新する必要があります。
--We are looking for 10:
10 - (False, 20)
|
V {-finally-} update 10 => (True, 10 - 1 - 1 - 1)
20 - (False, 40) ^
| |
V update 20 => 20 - (True, 10 - 1 - 1)
40 - (False, 13) ^
| |
V update 40 => 40 - (True, 10 - 1)
13 - (True, 10) ^
| |
---------------------------
問題は、数値を更新して繰り返しを続けるなど、関数で2つのことを実行できるかどうかわからないことです。C同様の言語では、（疑似コード）のようなことをするかもしれません：
void f(int n, tuple(b,nr), int &length, table)
{
if(b == False) f (nr, (table lookup nr), 0, table);
// the bool is true so we got a length
else
{
length = nr;
return;
}
// Since this is a recurence it would work as a stack, producing the right output
table update(n, --cnt);
}
参照によって cnt を送信しているため、最後の命令は機能します。また、ある時点で終了し、cnt が 1 未満であってはならないことが常にわかっています。