Ruby - Project Euler # 18 - Maximum Path Sum

Question

I've been working on some Project Euler problems, and for the most part, I've been doing pretty well. Problem 18, though has really stumped me.

Starting at the top of a tree, I'm supposed to find the path that leads to the maximum sum

      3
    7   4
  2   4   6
8   5   9   3

In this case, there are 24 possible paths, or 4! The best possible path is 3 -> 7 -> 4 -> 9 which sums up to 23.

I tried to solve the problem by replicating the example.

array = [[3],[7,4],[2,4,6],[8,5,9,3]]
array.each_slice(1){|s|p s}                          => This prints the tree

I got an answer which will on rare cases be correct, but it's not really legitimate.

sum = []
array.each{|a|sum.push(a.sample)}
return sum

This method is basically just selecting a random path and even with this easy example, there is still only a 1 in 24 chance of getting it right.

I've tried things like

level_two = []
level_three = []
for i in 0..array.length-1
  for j in 0..array[1].length-1
    level_two.push([array[0], array[1][i])        => Now level 2 has 2 paths - [3,7] & [3,4]
    for k in 0..array[2].length-1
      level_three.push([level_two[0],array[2][k], [level_two[1], array[2][k])
    end
  end
end

But at this point I can't even track which variables I'm using.

I've tried each_cons, combination and zip, none of which have worked.

Does anyone know of a strategy to solve this problem?

Edit: This won't give the answer to the problem, but simply the answer to the example. I will then apply that design pattern on the main problem.

Answer 1

This is how I would do it.

Code

def longest_path(arr)
  return nil if arr.empty?

  h = { len: arr.first.first, path: [] }
  return h if arr.size == 1

  arr[1..-1].reduce([h]) do |l,row|
    h = l.first
    left = { len: h[:len]+row.first, path: h[:path]+[:l] }
    mid = l.each_cons(2).to_a.zip(row[1..-2]).map do |(h1,h2),v|
            if h1[:len] >= h2[:len]
              { len: h1[:len]+v, path: h1[:path]+[:r] }
            else
              { len: h2[:len]+v, path: h2[:path]+[:l] }
            end
          end
    h = l.last
    right = { len: h[:len]+row.last, path: h[:path]+[:r] }
    [left, *mid, right]
  end.max_by { |h| h[:len] }
end

Example

a = [   [3],
       [7,4],
      [2,4,6],
     [8,5,9,3]]

longest_path a
  #=> {:len=>23, :path=>[:l, :r, :r]}

Thus, the longest path has length 23. From 3 in the first row, down and left (:l) to 7 in the second row, down and right (:r) to 4 in the third row and down and right to 9 in the last row: 3+7+4+9 => 23.

Explanation

This question is as much about the implementation of an algorithm as the choice of algorithm. It seems to me that the latter is fairly obvious: solve for one row, use that to solve for two rows, and so on.

Consider the example array a above.

arr = a
arr.empty? #=> false, so continue

h = { len: arr.first.first, path: [] }
  #=> {:len=>3, :path=>[]}
return h if arr.size == 1 # arr.size => 4, so continue

As

arr[1..-1] => [[7, 4], [2, 4, 6], [8, 5, 9, 3]]

reduce passes [h] and [7, 4] into the block and assigns the block variables:

l   = [{ len: arr.first.first, path: [] }]
row = [7, 4]

It then computes:

h     = l.first
  #=> {:len=>3, :path=>[]}
left  = { len: h[:len]+row.first, path: h[:path]+[:l] }
  #=> {:len=>10, :path=>[:l]}
mid   = []
h     = l.last
  #=> {:len=>3, :path=>[]}
right = { len: h[:len]+row.last, path: h[:path]+[:r] }
  #=> {:len=>7, :path=>[:r]}
[left, *mid, right]
  #=> [{:len=>10, :path=>[:l]}, {:len=>7, :path=>[:r]}]

mid => [] because each_cons(2) is executed on an array of size 1.

This last line above provides information for the longest paths to each of the two elements in the second row. For the first element (7), the path is of length 10 and goes from the only element in the first row (3) and then down and "left" (:l) to the given element.

As [left, *mid, right] is computed in the last row of the reduce block, the block variable l is given that value for the processing of the next row of arr:

l   = [{:len=>10, :path=>[:l]}, {:len=>7, :path=>[:r]}]
row = [2, 4, 6]

Next we compute the following:

left = { len: h[:len]+row.first, path: h[:path]+[:l] }
  #=> {:len=>5, :path=>[:l]}
l.each_cons(2).to_a.zip(row[1..-2]).map do |(h1,h2),v|
   if h1[:len] >= h2[:len]
     { len: h1[:len]+v, path: h1[:path]+[:r] }
   else
     { len: h2[:len]+v, path: h2[:path]+[:l] }
   end
end
  #=> [{:len=>14, :path=>[:l, :r]}]
h = l.last
  #=> {:len=>7, :path=>[:r]}
right = { len: h[:len]+row.last, path: h[:path]+[:r] }
  #=> {:len=>13, :path=>[:r, :r]}
[left, *mid, right]
  #=> [{:len=>5, :path=>[:l]}, {:len=>14, :path=>[:l, :r]},
  #    {:len=>13, :path=>[:r, :r]}]

The calculations of left and right are similar to those done for the previous element of arr. Let's look at the calculation of mid:

pairs = l.each_cons(2).to_a
  #=>   [[{:len=>10, :path=>[:l]}, {:len=>7, :path=>[:r]}]]
vals  = pairs.zip(row[1..-2])
  #=>   pairs.zip([4])
  #=>   [[[{:len=>10, :path=>[:l]}, {:len=>7, :path=>[:r]}], 4]]

vals is an array containing one element. That element is passed into the map, decomposed and assigned to the block variables:

h1       = {:len=>10, :path=>[:l]}
h2       = {:len=> 7, :path=>[:r]}
v        = 4
h1[:len] #=> 10
h2[:len] #=> 7

As 10 > 7, we execute:

{ len: h1[:len]+v, path: h1[:path]+[:r] }

which is the value of mid. The block value l for reduce is now assigned the result of [left, *mid, right]:

l = [{:len=> 5, :path=>[:l]}, {:len=>14, :path=>[:l, :r]},
     {:len=>13, :path=>[:r, :r]}]

and processing of the third row commences. reduce returns:

d = [{:len=>20, :path=>[:l, :l, :l]}, {:len=>19, :path=>[:l, :r, :l]},
     {:len=>23, :path=>[:l, :r, :r]}, {:len=>16, :path=>[:r, :r, :r]}]

which provides information describing the longest path to each element of the last row. The last step is:

d.max_by { |h| h[:len] }
  #=> {:len=>23, :path=>[:l, :r, :r]}

Answer 2

Start at the last row. Replace it by a row consisting of the maximums of each consecutive pair, so 8 5 9 3-> 8 9 9. Add these values to the row above it ( 2 4 6 -> 10 13 15). Repeat until the first row.(10 13 15 -> 13 15, 7 4-> 20 19 -> 20; 3 -> 23.

Answer 3

This problem is a perfect use case for recursion. For terminology, let's say that T[3][0] is 0th element in the 3rd row counting from 0 (which is 8 in your example).

Starting at the top of the tree, what is the path that leads to the maximum sum? First, let's reword this slightly: what is the path with the maximum sum starting at T[0][0]? Well that would be T[0][0] plus the path starting at T[1][0] or T[1][1] (whichever path is greater). Finding the path itself is incidental to finding the largest sum, so we'll just focus on that.

Let's say that S[x][y] is the maximum sum of a path starting at T[x][y]. Then from the previous observation we get that

S[x][y] = T[x][y] + MAX(S[x + 1][y], S[x + 1][y + 1])

Unless x is the last row of the tree. Let R be the last row of our tree, in that case

S[R][y] = T[R][y]

In Ruby, we could write the function like this:

def largest_sum_path(tree, x = 0, y = 0)
  path = [tree[x][y]]

  return path if x == tree.length - 1

  left  = largest_sum_path(tree, x + 1, y)
  right = largest_sum_path(tree, x + 1, y + 1)

  return path.concat([left, right].max_by { |p| p.reduce(:+) })
end

However, I suspect that this approach will be extremely slow for large trees. I'll leave it up to you to see how it can be optimized.

Answer 4

With these types of problems, my first step is to understand the relationships between the array indices. Given an array at level n of this tree, what child elements at array level n + 1 can a parent element at index i (in array level n) access? The answer is elements at i and i + 1.

For example: Let [2, 4, 6] be the array at level 2 and [8, 5, 9, 3] be the array at level 3. What child elements can element 6 (at index 2) access? 9, 3 can be accessed because their indices are 2, 3.

Now we can create a recursive solution to this problem:

@res = [] # All paths will be stored here
def paths(arr, temp, lvl = 0, idx = 0)
  if arr[lvl] # we haven't hit end of path
    # loop through elements at i and i + 1
    arr[lvl][idx..idx+1].each_with_index do |x, i|
      # go one level deeper into tree
      paths(arr, temp.dup << x, lvl + 1, i)
    end
  else
    @res << temp # `temp` has complete path, push it into results
  end
end

paths(array, []) # initialize temporary path to empty array

@res.map { |x| x.reduce(:+) }.max # => 23