On a Manhattan grid, find the intersection of two paths closest to the origin. input_3.txt
can be found here and the prompts can be found in the original problem statement.
import re
with open("input_3.txt", "r") as f:
coordinates = [wire.split(",") for wire in f.read().splitlines()]
class Point:
def __init__(self, x: int, y: int, cumulative_steps: int):
self.x = x
self.y = y
self.cumulative_steps = cumulative_steps
def __eq__(self, other):
return (self.x, self.y) == (other.x, other.y)
def __hash__(self):
return hash((self.x, self.y))
def __repr__(self):
return f"x:{self.x}, y:{self.y}"
class WirePath:
def __init__(self, **kwargs):
self.origin = Point(0, 0, 0)
self.path = kwargs.get("path", None)
self.points = [
self.origin,
]
self.current_point = None
if self.path:
self.generate_travelled_points(self.path)
def travel(self, direction, velocity):
start = self.origin if not self.current_point else self.current_point
# calculate cumulative steps for each point added
if direction in "RL":
# if R subtract negative (add), if L subtract (minus)
pos = -1 if direction == "R" else 1
# add all points between the two segments
new_points = [
Point(start.x - (pos * p), start.y, start.cumulative_steps + p)
for p in range(1, abs(velocity) + 1)
]
else:
# if U subtract negative (add), if D subtract (minus)
pos = -1 if direction == "U" else 1
new_points = [
Point(start.x, start.y - (pos * p), start.cumulative_steps + p)
for p in range(1, abs(velocity) + 1)
]
self.points.extend(new_points)
self.current_point = self.points[-1]
def generate_travelled_points(self, vectors: list):
for vector in vectors:
# extract the direction & velocity
r = re.compile("([a-zA-Z]+)([0-9]+)")
m = r.match(vector)
direction = m.group(1)
velocity = int(m.group(2))
# add the point to self.points
self.travel(direction, velocity)
def manhattan_distance_between_points(a, b):
return abs(a[0] - b[0]) + abs(a[1] - b[1])
wire1 = WirePath(path=coordinates[0])
wire2 = WirePath(path=coordinates[1])
intersections = set([x for x in wire1.points if x.cumulative_steps != 0]).intersection(
[x for x in wire2.points if x.cumulative_steps != 0]
)
intersections_with_distance_from_origin = [
((x.x, x.y), manhattan_distance_between_points((x.x, x.y), (0, 0)))
for x in intersections
if x.cumulative_steps != 0
]
# part 1
closest_intersection = min(intersections_with_distance_from_origin, key=lambda t: t[1])
print(closest_intersection)
intersection_pairs = []
for intersection in intersections:
# find points from each wire that matches the hash
wire1_intersects = min(
[i for i in wire1.points if i == intersection], key=lambda t: t.cumulative_steps
)
wire2_intersects = min(
[i for i in wire2.points if i == intersection], key=lambda t: t.cumulative_steps
)
intersection_pairs.append([wire1_intersects, wire2_intersects])
min_steps = min(
intersection_pairs, key=lambda t: t[0].cumulative_steps + t[1].cumulative_steps
)
min_combined_steps_wire1 = min_steps[0].cumulative_steps
min_combined_steps_wire2 = min_steps[1].cumulative_steps
comb = min_combined_steps_wire1 + min_combined_steps_wire2
# part 2
print(
f"Min combined steps: {comb}, wire1: {min_combined_steps_wire1}, wire2: {min_combined_steps_wire2} at {min_steps}"
)
My code is quite slow (~7s on my pc) and I have a feeling it's a combination of:
- how I'm storing all points in memory instead of making use of inferred points by storing line fragments instead, and
- my mishandling of the set iteration in the last part that attempts to find the respective pair of points (one for each wire) to get their respective
cumulative_steps
.
I got a little confused as to the best way to treat this because a wire can cross an intersection multiple times (though I believe in this data set that ended up not occurring?) and as a result I needed not just find the intersections but the intersections and the min steps required for each wire to get to that intersection.