欧拉计划 No. 14 Haskell

我正在尝试解决 Project Euler 的问题 14 (http://projecteuler.net/problem=14 http://projecteuler.net/problem=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

Ex:

  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并更新地图，但我也想更新 20、40，以防它们仍然存在（False，_）

My code:

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)              ^
     |                         |
     ---------------------------

问题是我不知道是否可以在函数中做两件事，例如更新数字并继续重复。在一个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 不应该

最简单的优化（正如您所确定的）是记忆。您尝试自己创建一个记忆系统，但是遇到了如何存储记忆值的问题。有一些解决方案可以以可维护的方式做到这一点，例如使用 State monad 或STArray http://www.haskell.org/ghc/docs/latest/html/libraries/array/Data-Array-ST.html。然而，有一个更简单的解决方案可以解决您的问题 - 使用 haskell 现有的记忆功能。 Haskell 默认情况下会记住常量值，因此如果您创建一个存储 collat​​z 值的值，它将自动记忆！

下面的斐波那契定义就是一个简单的例子：

fib :: Int -> Integer
fib n = fibValues !! n where
  fibValues = 1 : 1 : zipWith (+) fibValues (tail fibValues)

The fibValues is a [Integer]，并且由于它只是一个常数值，因此它被记忆。然而，这并不意味着它会被一次性记住，因为它是一个无限列表，所以它永远不会完成。相反，这些值仅在需要时才计算，因为 haskell 很懒。

因此，如果你对你的问题做了类似的事情，你不需要做很多工作就可以记住。但是，使用上面这样的列表在您的解决方案中效果不佳。这是因为 collat​​z 算法使用许多不同的值来获取给定数字的结果，因此所使用的容器需要随机访问才能有效。显而易见的选择是数组。

collatzMemoized :: Array Integer Int

接下来，我们需要用正确的值填充数组。我会写这个函数假装collatz存在计算任意 n 的 collat​​z 值的函数。另请注意，数组的大小是固定的，因此需要使用一个值来确定要记忆的最大数量。我将使用一百万，但可以使用任何值（这是内存/速度的权衡）。

collatzMemoized = listArray (1, maxNumberToMemoize) $ map collatz [1..maxNumberToMemoize] where
  maxNumberToMemroize = 1000000

这非常简单，listArray给定边界，并给出该范围内所有 collat​​z 值的列表。请记住，这不会立即计算所有 collat​​z 值，因为这些值是惰性的。

现在，可以编写 collat​​z 函数了。最重要的部分是只检查collatzMemoized如果被检查的数字在其范围内，则为数组：

collatz :: Integer -> Int
collatz 1 = 1
collatz n
  | inRange (bounds collatzMemoized) nextValue = 1 + collatzMemoized ! nextValue
  | otherwise = 1 + collatz nextValue
  where
    nextValue = case n of
      1 -> 1
      n | even n -> n `div` 2
        | otherwise -> 3 * n + 1

在 ghci 中，您现在可以看到记忆化的有效性。尝试collatz 200000。大约需要 2 秒才能完成。但是，如果您再次运行它，它将立即完成。

最后可以找到解决方案：

maxCollatzUpTo :: Integer -> (Integer, Int)
maxCollatzUpTo n = maximumBy (compare `on` snd) $ zip [1..n] (map collatz [1..n]) where

然后打印：

main = print $ maxCollatzUpTo 1000000

如果运行main，大约10秒后就会打印结果。

现在，这种方法的一个小问题是它使用了大量的堆栈空间。它在 ghci 中工作得很好（它似乎在堆栈空间方面使用更灵活）。但是，如果您编译它并尝试运行可执行文件，它将崩溃（堆栈空间溢出）。因此，要运行该程序，您必须在编译时指定更多内容。这可以通过添加来完成-with-rtsopts='K64m'到编译选项。这会将堆栈增加到 64mb。

现在程序可以编译并运行：

> ghc -O3 --make -with-rtsopts='-K6m' problem.hs

Running ./problem将在不到一秒的时间内给出结果。