I always start to struggle when AOC moves into spatial challenges, and this is where the code starts to get a bit ugly. In this challenge, I have to think about two wires moving across a coordinate plane, and look for positions where they intersect. Then I’ll score each intersection, first by Manhattan distance to the origin, and then by total number of steps from the origin along both wires, and return the minimum.

Challenge

The puzzle can be found here. I’m given two lines of input, where each is a series of moves with a direct (up, down, left, right) and a distance. I’m asked to find where the two wires cross. For the first part, I’ll return the crossing with the shortest Manhattan distance to the origin. For the second part, I’ll return the intersection with the fewest steps back to the origin combined for the two wires.

Solution

Part 1

I decided that for each wire, I would take the list of moves and convert it into two lists, vertical_segments and horizontal_segments. For the vertical_segments, I’ll store a segment as (x, (y1, y2)), and for horizontal_segments, (y, (x1, x2)). To see if two segments cross, I can simply check that v[1][0] < h[0] < v[1][1] and h[1][0] < v[0] < h[1][1].

On my first attempt, I didn’t differentiate between the two wires, just finding all segments, and looking for crossings. This worked for the initial example input, but in the second example, it didn’t match the given expectation of 159. The program produced the following output (with some debug printing on to identify the intersections and their distances):

$ ./day3.py 03-test_input-1.txt
intersection: 158,4 162
intersection: 158,11 169
intersection: 158,-12 170
intersection: 146,11 157
intersection: 146,46 192
intersection: 155,4 159
intersection: 155,11 166
Part 1: 157

The correct answer is in the list, but there’s extra intersections, including one with a lower distance than the expected answer. That tells me that I need to only consider when the two wires cross, and not when a wire crosses itself.

I updated the code (and again, this isn’t pretty) and got a working result:

#!/usr/bin/env python3

import sys
from collections import defaultdict

dir_key = {"R": 1, "U": 1, "L": -1, "D": -1}
vertical = ["U", "D"]

def wire_rel_to_abs(wire):

    vertical_segments = []
    horizontal_segments = []
    x,y = 0,0
    for w in wire:
        if w[0] in vertical:
            delta = dir_key[w[0]] * int(w[1:])
            vertical_segments.append(((x,sorted((y,y+delta)))))
            y += delta
        else:
            delta = dir_key[w[0]] * int(w[1:])
            horizontal_segments.append(((y,sorted((x,x+delta)))))
            x += delta
    return vertical_segments, horizontal_segments


def check_intersect(verts, hors):
    intersects = []
    for v in verts:
        for h in hors:
            if h[1][0] < v[0] < h[1][1] and v[1][0] < h[0] < v[1][1]:
                intersects.append((v[0],h[0]))
    return intersects


def min_manhattan_dist(points):
    min_dist = abs(points[0][0]) + abs(points[0][1])
    for p in points[1:]:
        dist = abs(p[0]) + abs(p[1])
        min_dist = min(min_dist, dist)
    return min_dist


with open(sys.argv[1], 'r') as f:
    wires = [x.strip().split(',') for x in f.readlines()]

verts1, hors1 = wire_rel_to_abs(wires[0])
verts2, hors2 = wire_rel_to_abs(wires[1])


min_dist = None
intersections = check_intersect(verts1, hors2)
intersections.extend(check_intersect(verts2, hors1))
print(f"Part 1: {min_manhattan_dist(intersections)}")

Basically I get two sets of segments, and then run check_intersect for each vertical set of segments on the other wire’s horizontal segments. Once I have the list of intersections, I can run over them to find the minimum Manhattan distance.

When I run this, I get the result:

$ time ./day3.py 03-puzzle_input.txt 
Part 1: 260

real    0m0.050s
user    0m0.039s
sys     0m0.011s

I’m still watching the time of execution, but this is instant.

Part 2

Now the metric for each intersection is changing, from a simple Manhattan distance to the sum of the number of steps along each wire to reach the intersection point. I suspect there’s a better way to do this, but I just walked each wire again, this time checking each point along the wire, and if it was an intersection, saving the number of steps.

intersect_delay = defaultdict(int)
for wire in wires:
    x,y = 0,0
    steps = 0
    for w in wire:
        for _ in range(int(w[1:])):
            if w[0] in vertical:
                y += dir_key[w[0]]
            else:
                x += dir_key[w[0]]
            steps += 1
            if x == 5 and y == 6:
                z = 1
            if (x,y) in intersections:
                intersect_delay[(x,y)] += steps

print(f"Part 2: {intersect_delay[min(intersect_delay, key=lambda k: intersect_delay[k])]}")

I’ll use a defaultdict to store the steps for each intersection, so that I don’t have to check if the key exists when I want to add the steps to an intersection.

To find the minimum, I’ll use min with the key parameter basically saying to get the value of the item. Without the key parameter, it would return the minimum dictionary key, not the value.

When I run this, it does take just over a second to run:

$ time ./day3.py 03-puzzle_input.txt 
Part 1: 260
Part 2: 15612

real    0m1.118s
user    0m1.110s
sys     0m0.008s

That’s not too long, so I’m still in the phase where I can afford to make brute force decisions like re-walking the each wire.

Final Code

#!/usr/bin/env python3

import sys
from collections import defaultdict

dir_key = {"R": 1, "U": 1, "L": -1, "D": -1}
vertical = ["U", "D"]

def wire_rel_to_abs(wire):

    vertical_segments = []
    horizontal_segments = []
    x,y = 0,0
    for w in wire:
        if w[0] in vertical:
            delta = dir_key[w[0]] * int(w[1:])
            vertical_segments.append(((x,sorted((y,y+delta)))))
            y += delta
        else:
            delta = dir_key[w[0]] * int(w[1:])
            horizontal_segments.append(((y,sorted((x,x+delta)))))
            x += delta
    return vertical_segments, horizontal_segments


def check_intersect(verts, hors):
    intersects = []
    for v in verts:
        for h in hors:
            if h[1][0] < v[0] < h[1][1] and v[1][0] < h[0] < v[1][1]:
                intersects.append((v[0],h[0]))
    return intersects


def min_manhattan_dist(points):
    min_dist = abs(points[0][0]) + abs(points[0][1])
    for p in points[1:]:
        dist = abs(p[0]) + abs(p[1])
        min_dist = min(min_dist, dist)
    return min_dist


with open(sys.argv[1], 'r') as f:
    wires = [x.strip().split(',') for x in f.readlines()]

verts1, hors1 = wire_rel_to_abs(wires[0])
verts2, hors2 = wire_rel_to_abs(wires[1])


min_dist = None
intersections = check_intersect(verts1, hors2)
intersections.extend(check_intersect(verts2, hors1))
print(f"Part 2: {min_manhattan_dist(intersections)}")

intersect_delay = defaultdict(int)
for wire in wires:
    x,y = 0,0
    steps = 0
    for w in wire:
        for _ in range(int(w[1:])):
            if w[0] in vertical:
                y += dir_key[w[0]]
            else:
                x += dir_key[w[0]]
            steps += 1
            if x == 5 and y == 6:
                z = 1
            if (x,y) in intersections:
                intersect_delay[(x,y)] += steps

print(f"Part 2: {intersect_delay[min(intersect_delay, key=lambda k: intersect_delay[k])]}")