Project Euler #18 in Haskell

3
votes

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

  2. 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?

3
haskelltree
It looks pretty readable already (especially for a Haskell program). – Robert Harvey
Depends if you find map (map read . words) (lines a) :: [[Int]] more readable (I do) – bennofs
I am not sure what you want when you say converting a tree from the list. – Satvik
@Satvik If you look on the actual project euler page you will see it is formatted more like an equilateral triangle which is essentially just a tree where each node has two children. I'm trying to determine if the problem would be easier to solve with the data in tree form or [[Int]] form. – picklebobdogflog
@bennofs Ah I see I was confused about how read works with the whole :: part. So you can just put what you want the final form to be at the end of the whole line? – picklebobdogflog

3 Answers

4
votes

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

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

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)