首页 文章

项目Euler#18在Haskell

提问于
浏览
3

我目前正在学习函数式编程和来自python背景的Haskell . 为了帮助我学习,我决定做一些项目的euler问题(http://projecteuler.net/problem=18) . 目前我在#18 . 从这个字符串开始,

"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"

我设法使用此函数将其转换为嵌套数组:

map (\x -> map (\y -> read y :: Int) (words x)) (lines a)

该功能输出:

[[75],[95,64],[17,47,82],[18,35,87,10],[20,4,82,47,65],[19,1,23,75,3,34],[88,2,77,73,7,63,67],[99,65,4,28,6,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,4,68,89,53,67,30,73,16,69,87,40,31],[4,62,98,27,23,9,70,98,73,93,38,53,60,4,23]]
  • 有没有办法在没有lambdas的情况下编写转换函数并使其更具可读性?

  • 如何将此嵌套数组转换为如此定义的树结构:

数据树a = EmptyTree |节点a(树a)(树a)派生(显示,读取,Eq)

或者将它作为一个数组并从那里解决它会更容易吗?

3 回答

  • 1

    您可以使用 foldr 将列表列表转换为 Tree

    -- given the elements for the current generation of trees, 
    -- and a list of trees in the next generation, generate
    -- the current generation of trees
    -- assumes |as| == |ts| - 1
    generation :: [a] -> [Tree a] -> [Tree a]
    generation as ts = zipWith3 Node as (init ts) (tail ts)
    
    -- forest gs ~ generates |head gs| trees
    forest :: [[a]] -> [Tree a]
    forest = foldr generation $ repeat EmptyTree
    
    fromList :: [[a]] -> Maybe (Tree a)
    fromList gs = case forest gs of
      [t] -> Just t
      _   -> Nothing
    

    请注意同一棵树如何重用为上一代中两棵不同树的子节点 .

    向后思考它可能会有所帮助

    • 最后一行中的每个元素都将 EmptyTree 作为左右子项 .
    generation as ts = zipWith3 Node as (init ts) (tail ts)
      as = [4,62,98,27,23,9,70,98,73,93,38,53,60,4,23]
      ts = [EmptyTree, EmptyTree, ..]
      init ts = [EmptyTree, EmptyTree, ..]
      tail ts = [EmptyTree, EmptyTree, ..]
      zipWith3 Node as (init ts) (tail ts) = [Node 4 EmptyTree EmptyTree,Node 62 EmptyTree EmptyTree,Node 98 EmptyTree EmptyTree,Node 27 EmptyTree EmptyTree,Node 23 EmptyTree EmptyTree,Node 9 EmptyTree EmptyTree,Node 70 EmptyTree EmptyTree,Node 98 EmptyTree EmptyTree,Node 73 EmptyTree EmptyTree,Node 93 EmptyTree EmptyTree,Node 38 EmptyTree EmptyTree,Node 53 EmptyTree EmptyTree,Node 60 EmptyTree EmptyTree,Node 4 EmptyTree EmptyTree,Node 23 EmptyTree EmptyTree]
    
    • 倒数第二行中的每个元素都使用最后一行中的树
    generation as ts = zipWith3 Node as (init ts) (tail ts)
      as = [63,66,4,68,89,53,67,30,73,16,69,87,40,31]
      ts = [Node 4 EmptyTree EmptyTree,Node 62 EmptyTree EmptyTree,Node 98 EmptyTree EmptyTree,Node 27 EmptyTree EmptyTree,Node 23 EmptyTree EmptyTree,Node 9 EmptyTree EmptyTree,Node 70 EmptyTree EmptyTree,Node 98 EmptyTree EmptyTree,Node 73 EmptyTree EmptyTree,Node 93 EmptyTree EmptyTree,Node 38 EmptyTree EmptyTree,Node 53 EmptyTree EmptyTree,Node 60 EmptyTree EmptyTree,Node 4 EmptyTree EmptyTree,Node 23 EmptyTree EmptyTree]
      init ts = [Node 4 EmptyTree EmptyTree,Node 62 EmptyTree EmptyTree,Node 98 EmptyTree EmptyTree,Node 27 EmptyTree EmptyTree,Node 23 EmptyTree EmptyTree,Node 9 EmptyTree EmptyTree,Node 70 EmptyTree EmptyTree,Node 98 EmptyTree EmptyTree,Node 73 EmptyTree EmptyTree,Node 93 EmptyTree EmptyTree,Node 38 EmptyTree EmptyTree,Node 53 EmptyTree EmptyTree,Node 60 EmptyTree EmptyTree,Node 4 EmptyTree EmptyTree]
      tail ts = [Node 62 EmptyTree EmptyTree,Node 98 EmptyTree EmptyTree,Node 27 EmptyTree EmptyTree,Node 23 EmptyTree EmptyTree,Node 9 EmptyTree EmptyTree,Node 70 EmptyTree EmptyTree,Node 98 EmptyTree EmptyTree,Node 73 EmptyTree EmptyTree,Node 93 EmptyTree EmptyTree,Node 38 EmptyTree EmptyTree,Node 53 EmptyTree EmptyTree,Node 60 EmptyTree EmptyTree,Node 4 EmptyTree EmptyTree,Node 23 EmptyTree EmptyTree]
      zipWith3 Node as (init ts) (tail ts) = [Node 63 (Node 4 EmptyTree EmptyTree) (Node 62 EmptyTree EmptyTree),Node 66 (Node 62 EmptyTree EmptyTree) (Node 98 EmptyTree EmptyTree),Node 4 (Node 98 EmptyTree EmptyTree) (Node 27 EmptyTree EmptyTree),Node 68 (Node 27 EmptyTree EmptyTree) (Node 23 EmptyTree EmptyTree),Node 89 (Node 23 EmptyTree EmptyTree) (Node 9 EmptyTree EmptyTree),Node 53 (Node 9 EmptyTree EmptyTree) (Node 70 EmptyTree EmptyTree),Node 67 (Node 70 EmptyTree EmptyTree) (Node 98 EmptyTree EmptyTree),Node 30 (Node 98 EmptyTree EmptyTree) (Node 73 EmptyTree EmptyTree),Node 73 (Node 73 EmptyTree EmptyTree) (Node 93 EmptyTree EmptyTree),Node 16 (Node 93 EmptyTree EmptyTree) (Node 38 EmptyTree EmptyTree),Node 69 (Node 38 EmptyTree EmptyTree) (Node 53 EmptyTree EmptyTree),Node 87 (Node 53 EmptyTree EmptyTree) (Node 60 EmptyTree EmptyTree),Node 40 (Node 60 EmptyTree EmptyTree) (Node 4 EmptyTree EmptyTree),Node 31 (Node 4 EmptyTree EmptyTree) (Node 23 EmptyTree EmptyTree)]
    

    zipWith3 f as bs cs 只是从步骤中的每个列表中获取元素,并将给定的函数应用于具有相同索引的元素,给出 [ f a0 b0 c0, f a1 b1 c1, ... ]

    您也可以使用 forest [[63,66,4,68,89,53,67,30,73,16,69,87,40,31],[4,62,98,27,23,9,70,98,73,93,38,53,60,4,23]] 直接计算

    您需要生成此中间数据结构才能解决问题,但您可以使用相同的结构直接计算答案 .

    generation :: Num a => [a] -> [(a, [a])] -> [(a, [a])]
    generation as ts = zipWith3 ????  as (init ts) (tail ts)
    
    forest :: Num a => [[a]] -> [(a, [a])]
    forest = foldr generation $ repeat ????
    
    fromList :: [[a]] -> Maybe (a, [a])
    fromList gs = case forest gs of
      [t] -> Just t
      _   -> Nothing
    
    -- what's the maximum total sum of any path
    maxTotal :: [[a]] -> Maybe a
    maxTotal = fmap fst . fromList
    
    -- what's the path with maximum total sum
    maxPath :: [[a]] -> Maybe [a]
    maxPath = fmap snd . fromList
    
  • 4

    这就是我想出的

    foo :: String -> [[Int]]
    foo = map (map read) . map words . lines
    

    可以使用递归定义从此构造树 .

    fromList :: [[a]] -> Tree a
    fromList [[]] = EmptyTree
    fromList [[x]] = Node x EmptyTree EmptyTree
    fromList ([x]:rs) = Node x ltree rtree
      where ltree = fromList . snd $ mapAccumL (\n l -> (n+1,take n l)) 1 rs
            rtree = fromList $ map (drop 1) rs
    
  • 2

    我喜欢嵌套列表,也许是因为我对树木知之甚少......这里有一个提示:

    如果从具有 n 数字的最长行开始(即 n 选项),您是否可以将其转换为具有 n-1 数字/选项的行,每行对应一行中的数字/选项?

    (使用嵌套列表作为参数,您可以使用Haskell将解决方案编码为一行)

相关问题