Ruby - Project Euler # 18 - Maximum Path Length

Question

I worked on some of the problems of Project Euler, and for the most part, I did everything well. Problem 18, although it puzzled me a lot.

Starting at the top of the tree, I have to find the path that will lead to the maximum amount

      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 stacks up to 23.

I tried to solve the problem by repeating an example.

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

I received an answer that in rare cases will be correct, but it is not really legal.

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

This method basically just picks a random path, and even with this easy example, there is still only 1 out of 24 chances to get it right.

I 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

, .

each_cons, zip, .

- ?

: , . .

Answer 1

.

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

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

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

, 23. 3 (:l) 7 (:r) 4 9 : 3+7+4+9 => 23.

, . , : , ..

a .

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 [h] [7, 4] -:

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

:

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 => [], each_cons(2) 1.

. (7) 10 (3), "" (:l) .

[left, *mid, right] reduce, l arr:

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

:

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

left right arr. 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 - , . map, :

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

10 > 7, :

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

mid. l reduce [left, *mid, right]:

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

. reduce :

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

, . :

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

Answer 2

. , T[3][0] 0- , 0 ( 8).

, , ? -, : , T[0][0]? , T[0][0] , T[1][0] T[1][1] ( , ). , .

, S[x][y] - , T[x][y]. ,

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

x - . R - ,

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

Ruby ​​:

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

, , . , , .

Answer 3

- . n , n + 1 ( n)? - + 1.

: [2, 4, 6] 2 [8, 5, 9, 3] 3. 6 ( 2)? 9, 3 , 2, 3.

:

@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

Answer 4

Start with the last line. Replace it with a line consisting of the maxima of each consecutive pair, therefore 8 5 9 3→ 8 9 9. Add these values ​​to the line above it (2 4 6 → 10 13 15). Repeat until the first line. (10 13 15 → 13 15, 7 4-> 20 19 → 20; 3 → 23.