Advent of Code 2019 Day 3: Crossed Wires

Question

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:

1. how I'm storing all points in memory instead of making use of inferred points by storing line fragments instead, and
2. 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.

Answer 1

These problems are typically performance-bound, and so it doesn't pay for you to design classes for such things as Point unless you are sure you need it.

In this case, I don't think you need it.

Consider using segments rather than points

Consider a worst-case path. It would be a staircase, each segment of length 1. This would generate lines of length 1, making each line effectively a single point (since the origin is included in the previous line).

If you have an algorithm that examines all the points your path traverses (which yours presently does), it would perform exactly equal to an algorithm that examines the line segments as discrete elements.

On the other hand, a non-pessimal path would have at least one line segment of length > 1, which would improve performance.

For this reason, I think you should rewrite your code to use line segments rather than points.

Tell, don't ask.

In the process of decoding the line segments, you use a regular expression, then discard the result, then use a series of string membership checks.

This is all wasted time. You know there are only four possible valid inputs {D, L, R, U}. Check for them explicitly, and dispatch instantly to the appropriate code:

handlers = { "U" : self.up, "D": self.down, "L": self.left, "R": self.right }

for segment in line:
    move_to = handlers[segment[0]]
    move_to(int(segment[1:]))

Take care of updating your current position indicator in the handler. And encode the knowledge of what is happening in the different handlers:

def up(self, how_far: int):
    """Add an upward line segment starting at cur_pos to the wire path."""

    new_xy = Position(self.cur_pos.x, self.cur_pos.y + how_far)
    self.verticals.append((self.cur_pos, new_xy))
    self.cur_pos = new_xy

Don't forget information

Knowing that a line segment is horizontal or vertical is valuable information. You should consider keeping your segments separate, or creating named_tuple types to differentiate between them.

If you keep them separate, then coding intersection code is simpler: you can special-case all the different flavors (an argument for creating separate types!).

Be lazy

You know that you are looking for the closest intersection point. If you are checking a line segment that has a "closest point" which is farther away than your current best match, you could skip that segment entirely!

It may or may not make sense to compute and track this information. You would have to write the code both ways to be sure. But your current approach is already \$N ^2\$ so this might speed things up.