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.
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]}