Advent of Code Day 3

In [1]:
with open("AoC/input3.txt") as input_file:
    test_input = input_file.read()
In [2]:
def segments(steps):
    segments = []
    current = (0, 0)
    for step in steps:
        if step[0] == 'R':
            b = (current[0] + step[1], current[1])
        elif step[0] == 'U':
            b = (current[0], current[1] + step[1])
        elif step[0] == 'L':
            b = (current[0] - step[1], current[1])
        elif step[0] == 'D':
            b = (current[0], current[1] - step[1])
        segments.append((current, b))
        current = b
    return segments
In [3]:
def intersect(segmentA, segmentB):
    a1, a2 = segmentA
    b1, b2 = segmentB
    
    for ax0, ax1 in [(0, 1), (1, 0)]:
        if a1[ax0] == a2[ax0] and b1[ax1] == b2[ax1] and \
            min(a1[ax1], a2[ax1]) <= b1[ax1] and b1[ax1] <= max(a1[ax1], a2[ax1]) and \
            min(b1[ax0], b2[ax0]) <= a1[ax0] and a1[ax0] <= max(b1[ax0], b2[ax0]):
                return a1[ax0], b1[ax1]
            
    # Doesn't handle overlaps
    return None
In [4]:
def process(input_str):
    parsed = [[(y[0], int(y[1:])) for y in x.split(",")] for x in input_str.strip().split("\n")]
    lines = list(map(segments, parsed))
    
    min_dist = None
    for lineA in lines[0]:
        for lineB in lines[1]:
            pt = intersect(lineA, lineB)
            dist = abs(pt[0]) + abs(pt[1]) if pt else None
            if dist and (not min_dist or min_dist > dist):
                min_dist = dist
    
    return min_dist
In [5]:
process(test_input)
Out[5]:
221
In [6]:
process("""R75,D30,R83,U83,L12,D49,R71,U7,L72
U62,R66,U55,R34,D71,R55,D58,R83""")
Out[6]:
159
In [7]:
def length(line):
    return abs(line[0][0] - line[1][0]) + abs(line[0][1] - line[1][1])
In [8]:
def process2(input_str):
    parsed = [[(y[0], int(y[1:])) for y in x.split(",")] for x in input_str.strip().split("\n")]
    lines = list(map(segments, parsed))
    
    min_steps = None
    stepsA = 0
    for lineA in lines[0]:
        
        stepsB = 0
        for lineB in lines[1]:
            pt = intersect(lineA, lineB)
            steps = stepsA + stepsB + length((lineA[0], pt)) + length((lineB[0], pt)) if pt else None
            if steps and (not min_steps or min_steps > steps) and not (pt[0] == 0 and pt[1] == 0):
                print(pt, steps, lineA, lineB)
                min_steps = steps
                
            stepsB += length(lineB)
                
        stepsA += length(lineA)
    
    return min_steps
In [9]:
process2("""R75,D30,R83,U83,L12,D49,R71,U7,L72
U62,R66,U55,R34,D71,R55,D58,R83""")

(158, -12) 610 ((158, -30), (158, 53)) ((155, -12), (238, -12))
Out[9]:
610
In [10]:
process2(test_input)

(998, 349) 39290 ((998, 0), (998, 367)) ((584, 349), (1238, 349))
(367, 1211) 25888 ((998, 367), (1733, 367)) ((1211, 823), (1211, -117))
(1733, 823) 23850 ((1733, 367), (1733, 1293)) ((2184, 823), (1211, 823))
(1756, 1665) 18542 ((1756, 1293), (1756, 1750)) ((1330, 1665), (1968, 1665))
Out[10]:
18542

I started this one early in the morning and not at midnight, but timed myself just to see how I perform. I ended up taking 50 minutes, which is pretty slow because of several easy mistakes. Notes to self:

  • Remember to structure the code to allow easily testing sample inputs.
  • Actually remember to test sample inputs.
  • It might be more valuable to edit the solution in place for the second star instead of starting from scratch.
  • Keep my notebook ready to paste strings of test inputs easily

Looking at the winning solutions from the subreddit, I ended up wasting too much time doing intersections instead of simply brute forcing a solution by assembling a collection of grid points -- which is a good trick to remember for grid/integer based problems.

TODO: Try drawing graphs of wires someday.