1
\$\begingroup\$

I have solved the 3rd day puzzle of Advent of Code but wanted some feedback on my solution. The puzzle here wants to find where two jumbled wires intersect closest to the origin.

Puzzle input is provided like so: R8,U5,L5,D3 representing the path of each string. Part A of the puzzle asks you to find the closest intersection to the origin calculated by Manhattan distance, and part B looks for the intersection that is the fastest path for both strings.

My solution was to store every point visited by each wire and use that path to then locate the closest or fastest intersection:

# frozen_string_literal: true

data = File.read('day3.txt').split("\n")
direction_code_arrays = data.map { |string_path| string_path.split(',') }

def calculate_path(direction_code_array)
  path = [[0, 0]]

  direction_code_array.each do |direction_code|
    direction = direction_code.slice(0, 1)
    number = direction_code.slice(1..-1).to_i

    while number.positive?
      prev_position = path.last
      new_position = Array.new(2, 0)
      new_position[0] = prev_position[0]
      new_position[1] = prev_position[1]

      case direction
      when 'R'
        new_position[0] += 1
      when 'L'
        new_position[0] -= 1
      when 'U'
        new_position[1] += 1
      when 'D'
        new_position[1] -= 1
      end

      number -= 1
      path << new_position
    end
  end
  path
end

def intersection_points(path1, path2)
  intersections = path1 & path2
  # origin at (0,0) should be excluded
  intersections.slice(1..-1)
end

def manhattan_distance(point)
  point[0].abs + point[1].abs
end

def number_steps_to_point(point, path1, path2)
  path1.find_index(point) + path2.find_index(point)
end

def shortest_manhattan_distance(path1, path2)
  shortest_distance = nil

  intersection_points = intersection_points(path1, path2)

  intersection_points.each do |intersection|
    if shortest_distance.nil? || manhattan_distance(intersection) < shortest_distance
      shortest_distance = manhattan_distance(intersection)
    end
  end
  shortest_distance
end

def fastest_intersection_point(path1, path2)
  fastest_point = nil

  intersection_points = intersection_points(path1, path2)

  intersection_points.each do |intersection|
    if fastest_point.nil? || number_steps_to_point(intersection, path1, path2) < fastest_point
      fastest_point = number_steps_to_point(intersection, path1, path2)
    end
  end
  fastest_point
end

string_1_path = calculate_path(direction_code_arrays[0])
string_2_path = calculate_path(direction_code_arrays[1])

print shortest_manhattan_distance(string_1_path, string_2_path)
print fastest_intersection_point(string_1_path, string_2_path)

To my understanding the time complexity of this solution is \$\mathcal{O}(n)\$, as each direction code in the array is iterated over once, while the space complexity is really poor as each code can generate hundreds of points in the path array. If anyone can explain the time and space complexity of my solution more clearly or offer any advice in optimizing I would very much appreciate it!

\$\endgroup\$
  • \$\begingroup\$ Welcome to CodeReview@SE. Please give 1) a definition of $n$ 2) a reference about the resource consumption of Ruby's array & operator. \$\endgroup\$ – greybeard Mar 11 at 7:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.