0

剧透：这是Project Euler问题 #18。阅读风险自负

问题是找到从帕斯卡三角形顶部严格向下到底部的所有非确定性路径的“最大和”。我试图通过对三角形的行进行折叠来计算总和。

这是输入字符串，以及一些基本的准备工作：

inputLines = ["75",
              "95 64",
              "17 47 82",
              "18 35 87 10",
              "20 04 82 47 65",
              "19 01 23 75 03 34",
              "88 02 77 73 07 63 67",
              "99 65 04 28 06 16 70 92",
              "41 41 26 56 83 40 80 70 33",
              "41 48 72 33 47 32 37 16 94 29",
              "53 71 44 65 25 43 91 52 97 51 14",
              "70 11 33 28 77 73 17 78 39 68 17 57",
              "91 71 52 38 17 14 91 43 58 50 27 29 48",
              "63 66 04 68 89 53 67 30 73 16 69 87 40 31",
              "04 62 98 27 23 09 70 98 73 93 38 53 60 04 23"]

input = map (map (read ::String ->Integer) . words) inputLines

prepareElems :: [[Integer]] -> [[Elem Integer]]
prepareElems = map mkElemsFromTri

这里有两个想法——有一排树，一排三角形。我没有做太多类型级别的抽象，但这并不重要。这个想法是三角形中的每一行都是在其长度上的二项式的“平行枚举”（即：）[(4,0), (3,1), (2,2), ... (0,4)]，并且在将标记的三角形行应用于树的行之前，树的每一行都得到“复制分叉”，使得确保每次分叉的机会都保持非确定性的完整性。这是我的技术的样子：

data BiLabel = BiLabel Integer Integer
  deriving (Show, Eq)

leftLabel (BiLabel x _) = x
rightLabel (BiLabel _ y) = y

parEnumBiLabel :: Integer -> [BiLabel]
parEnumBiLabel n = map ( \x ->BiLabel x $ (n-1)-x ) [0..(n-1)]


forkBiLabel :: BiLabel -> (BiLabel, BiLabel)
forkBiLabel (BiLabel x y) = (BiLabel (x+1) y,BiLabel x (y+1))

data Elem a = Elem {label :: BiLabel, element :: a}
  deriving (Show, Eq)

forkElem :: Elem a -> [Elem a]
forkElem (Elem l a) = [Elem left a,Elem right a]
  where
    (left,right) = forkBiLabel l

-- Does a binomial expansion, but cloning the elements and making new labels
cloneNextLevel :: [Elem Integer] -> [Elem Integer]
cloneNextLevel = concatMap forkElem

我的问题是代码适用于一行输入，但在折叠多行时失败。我的直觉告诉我，我的“复制叉”技术正在创建新标签，然后我的overElems函数可以通过它期望访问的标签应用。这是我的主要功能：

-- this applys a 1-ary function to all Elems of a list that match the label
onLabel :: (a -> a) -> BiLabel -> [Elem a] -> [Elem a]
onLabel f (BiLabel la lb) (x:xs) | label x == BiLabel la lb = processHead : processTail
                                 | otherwise = x : processTail
   where
    processHead = Elem (BiLabel la lb) $ f (element x)
    processTail = onLabel f (BiLabel la lb) xs 
onLabel _ _ [] = []


-- this _tries_ to do the equivalent of `onLabel`, but over lists and 2-ary functions
overElems :: (a -> a -> a) -> [Elem a] -> [Elem a] -> [Elem a]
overElems f (x:xs) ys = overElems f xs ( onLabel (f $ element x) (label x) ys )
overElems _ [] ys = ys


-- This starts with the first element of `input` as an accumulator, just because
-- then I won't have to copy it over as part of the fold, and can simply 
-- `cloneNextLevel` before I process it with `overElems`.
calculate :: [[Elem Integer]] -> [Elem Integer]
calculate = foldr (\z acc -> overElems (+) z (cloneNextLevel acc)) [Elem (BiLabel 0 0) (head $ head input)]

奇怪的是，折叠一行有效，但折叠多行无法应用高阶函数，但仍将结果扩展为正确的大小。以下是几个示例输入：

\> calculate $ prepareElems [[2,3]]

[Elem {label = BiLabel 1 0, element = 78},Elem {label = BiLabel 0 1, element = 77}]
-- that's correct, because the first element of the tree is 75

\> calculate $ prepareElems [[2,3],[10,20,30]]

[Elem {label = BiLabel 2 0, element = 75},Elem {label = BiLabel 1 1, element = 75},
Elem {label = BiLabel 1 1, element = 75},Elem {label = BiLabel 0 2, element = 75}]
-- this is the correct size and labeling, but not the right contents.

我的列表处理中的懒惰会导致这种情况吗？我的感觉是标签枚举发生在overWith有机会通过标签应用功能之前。这也是我的代码的完整页面。

4

0 回答 0