Skip to content

Problem 67 – Using an efficient algorithm find the maximal sum in a triangle

March 14, 2010

In order to solve this problem, I tried to use the solution of problem 18, however that didn’t work… Therefore, I started by looking into some Haskell libraries and I came across the zipWith function. I used it before, however I didn’t remember it when I solved problem 18. The truth is that by using it together with the foldr1 function, it simplified the solution drastically. Here is my solution:

import Examples

total67 = head . foldr1 f
  where f x1 x2 = let l = zipWith max (init x2) (tail x2)
                  in zipWith (+) x1 l

The triangles were saved inside another module (Examples). In order to save the triangle used in this problem, I used a small python script to insert a list syntax into the text file:

o = open("triangle.hs","a")
i = open("triangle.txt")
for line in open("triangle.txt"):
   line = line.replace(" ",",")
   line = line.strip()
   line = " [" + line + "],\n"
   o.write(line)
o.close()

GHCi executes this function in (0.08 secs, 34504884 bytes).

Advertisements
Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: