# Advent of Code Day 3, how to optimize my ruby solution?

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!

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