Find the intersection of two paths closest to the origin in a Manhattan grid.

`input_3.txt`

You will find here

The prompts can be found in the original problem description

```
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 pretty slow (~ 7s on my PC) and I feel like it's a combination

a) how to store all points in memory instead of using derived points by storing line fragments instead, and

b) my wrong handling of the set iteration in the last part, trying to find the respective pair of points (one for each wire) in order to get the respective one `cumulative_steps`

.

I was a little confused about how best to handle this because a wire can cross an intersection multiple times (though I believe in this record that ultimately didn't appear?), And as a result, I didn't just have to find the intersections, but also the intersections and the minimum steps required for each wire to get to that intersection.