Longest increasing path in a matrix

find_path.rb

def find_longest_rising_route(matrix)

  matrix_with_locations =
    matrix.each_with_index.map do |row, index|
      row.each_with_index.map do |el, inner_index|
        [index, [inner_index, el]]
      end
    end

  sorted_with_locations =
    matrix_with_locations.flatten(1).sort_by { |el| el[1][1] }


  sorted_with_locations.reduce([]) do |memo, el_with_location|
    # Get possible right i paths by adding to 'i'
    right_i_paths = [el_with_location]

    right_next_i = el_with_location[1][0] + 1
    current_el = el_with_location[1][1]
    j = el_with_location[0] # keep js constant
    

    until right_next_i >= matrix.first.length do
      right_el = matrix[j][right_next_i]
      break if right_el <= current_el
      right_i_paths << [j, [right_next_i, right_el]]
      right_next_i += 1
      current_el = right_el
    end

    # Get possible left i paths by subtracting 'i'
    
    left_i_paths = [el_with_location]

    left_next_i = el_with_location[1][0] - 1 # try left i
    current_el = el_with_location[1][1]
    
    j = el_with_location[0] # keep js constant

    until left_next_i == -1 do
      left_el = matrix[j][left_next_i]
      break if left_el <= current_el
      left_i_paths << [j, [left_next_i, left_el]]
      left_next_i -= 1
      current_el = left_el
      left_el = matrix[j][left_next_i]
    end

    # Get greatest of the i paths
    greatest_i_path =
      left_i_paths.count > right_i_paths.count ? left_i_paths : right_i_paths


    end_of_left_ipaths =
      greatest_i_path[-1]

    # Get possible upper j paths by subtracting to 'j' from greatest of the i paths

    upper_j_paths = [end_of_left_ipaths]

    upper_next_j = end_of_left_ipaths[0] - 1
    current_el = end_of_left_ipaths[1][1]
    i = end_of_left_ipaths[1][0] # keep is constant
    

    until upper_next_j == -1 do
      upper_el = matrix[upper_next_j][i]
      break if upper_el <= current_el
      upper_j_paths << [upper_next_j, [i, upper_el]]
      
      upper_next_j -= 1
      current_el = upper_el
      upper_el = matrix[upper_next_j][i]
    end

    # Get possible lower j paths by adding to 'j' from greatest of the i paths

    lower_j_paths = [end_of_left_ipaths]

    lower_next_j = end_of_left_ipaths[0] + 1
    current_el = end_of_left_ipaths[1][1]
    i = end_of_left_ipaths[1][0] # keep is constant
  
    

    until lower_next_j >= matrix.length do
      lower_el = matrix[lower_next_j][i]
      break if lower_el <= current_el
      lower_j_paths << [lower_next_j, [i, lower_el]]
      lower_next_j += 1
      current_el = lower_el
      lower_el = matrix[lower_next_j][i]
    end


    # Find greatest of j paths
    greatest_j_path =
      upper_j_paths.count > lower_j_paths.count ? upper_j_paths : lower_j_paths

    # Find the final count of the longest i path with accompanying longest j path
    greatest_path = greatest_i_path | greatest_j_path

    path_count = greatest_path.count
    if memo.empty?
      greatest_path
    elsif path_count > memo.count
      greatest_path
    else
      memo
    end
  end.map { |el| el.last.last }
end

matrix_1 = [
  [9,9,4],
  [6,6,8],
  [2,1,1]
]

puts "The longest increasing path for #{matrix_1.inspect} is #{find_longest_rising_route(matrix_1).inspect}"

matrix_2 = [
  [3,4,5],
  [3,2,6],
  [2,2,1]
]

puts "The longest increasing path for #{matrix_2.inspect} is #{find_longest_rising_route(matrix_2).inspect}"