Skip to content

Problem 18

March 13, 2010

In order to solve the 18th Euler problem, I used a lookahead function that tries to find out which position to choose in the current level of the triangle based on the next level. It also uses the last position used in order to pick the right values in the next levels of the triangle.

First, I defined both triangles using a list of lists, as one can see below.

import List

type Triag = [[Int]]

triangle :: Triag
triangle =
 [
  [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]
 ]

triangleExample :: Triag
triangleExample =
  [
   [3],
   [7,4],
   [2,4,6],
   [8,5,9,3]
  ]

Then, I created a few utility functions that I thought I could use, such as maxValue, which returns the position of the best number among 2; the indexOf, which btw I am not very proud of, that returns the position of a given number in a list (note: although one should never define such a function like that, I am sure I will find an element in that list, so the result will always be correct); and finally maxOf, which tells the lookahead function which position it should return based on the next level of the triangle.

Here are the definitions:

maxValue ::
  Int   -> --position
  [Int] -> --list
  Int

maxValue p l =
 let a = (!!) l p
     b = (!!) l (p+1)
 in case a >= b of
     True  -> p
     False -> p+1

indexOf ::
  Int   -> --element
  [Int] -> --list
  Int      --position in the list
indexOf n l =
   case (elemIndex n l) of
   Nothing -> 0
   Just x -> x

maxOf l = let k = unzip l
              m = (maximum . fst) k
              n = indexOf m (fst k)
          in (!!) (snd k) n

The lookahead calculates the sum of the relevant values in the current and next level of the triangle, and returns the best position to choose:

lookahead ::
  [Int] ->  -- Line 1
  [Int] ->  -- Line 2
  Int   ->  -- Column value
  Int       -- Column position where to go next

lookahead l1 l2 c =
  let x1_l1 = (!!) l1 c
      x2_l1 = (!!) l1 (c+1)
      v1    = (x1_l1 + (!!) l2 c,c)
      v2    = (x1_l1 + (!!) l2 (c+1),c)
      v3    = (x2_l1 + (!!) l2 (c+1),c+1)
      v4    = (x2_l1 + (!!) l2 (c+2),c+1)
      l     = [v1,v2,v3,v4]
  in maxOf l

Finally, it was a matter of assembling everything:

total_max ::
  Triag -> -- Triangle
  Int   -> -- Next column
  Int      -- maximum total

total_max (l1:l2:l3:ls) n =
  let next = lookahead l2 l3 n
      val  = (!!) l1 n
  in val + total_max (l2:l3:ls) next
total_max (l1:l2:[]) n =
  let val = (!!) l1 n
      nextval = maxValue n l2
  in val + (!!) l2 nextval

total = total_max triangle 0

The interpreter returned the following output, when I executed the total function:

(0.03 secs, 4125124 bytes)

Although it is not a pretty solution, it solved the problem relatively fast. Now I will try it in problem 67, where there are 299 possible routes!

Advertisements

From → Project Euler

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: