Project Euler #18 in Haskell

 

I am currently learning functional programming and Haskell coming from a python background. To help me learn, I decided to do some project euler problems (http://projecteuler.net/problem=18). Currently I am on #18. Starting with this string, 

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

I managed to convert it into a nested array using this function: 

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

That function outputs this: 

[[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]]
  • Is there a way to write that conversion function without the lambdas and make it more readable?

  • How would I convert this nested array to a tree structure defined like so:

    data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show, Read, Eq)

    Or would it just be easier to leave it as an array and solve it from there?

    • You can convert the list of lists into a Tree by using foldr : 

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

    Note how the same tree is reused to be the child of two different trees in the previous generation.

    It might help to think through it backwards

  • each element in the last row gets an EmptyTree as a left and right child. 

    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]

  • each element in the next-to-last row uses the trees from the last row 

    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 just takes elements from each list in step and applies the given function to elements with the same index, giving [ f a0 b0 c0, f a1 b1 c1, ... ]

    You can also compute this directly by using 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]]

    • You're right that you don't need to generate this intermediate data structure in order to solve the problem, but you can use this same structure to compute your answer directly. 

    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

    Here is what I came up with 

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

    Tree can be constructed from this using the recursive definition. 

    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

    I like the nested list, maybe because I don't know too much about trees... here's a hint:

    If you start at the longest line with n numbers (that is, n choices), could you convert it to a line with n-1 numbers/choices, each one corresponding with a number/choice on the line before?

    (with the nested list as a parameter, you can code the solution in one line with Haskell)

    链接地址: http://www.djcxy.com/p/80426.html

    上一篇: 欧拉项目4

    下一篇: 在Haskell项目欧拉＃18