Given the paths of two wires (that move in very straight lines on a grid), we need to find the intersection of these paths that is closest (in Manhattan distance) to the starting point.

``````
def closest_intersection(wire1, wire2):
intersections = get_intersections(wire1, wire2)
distances = [abs(x) + abs(y) for (x, y) in intersections]
return min(distances)

def get_intersections(wire1, wire2):
path1 = set(path(wire1))
path2 = set(path(wire2))
intersections = path1.intersection(path2)
return intersections

def path(wire):
positions = [(0,0)]
for section in wire:
direction = section
distance = int(section[1:])
while distance > 0:
lastpos = positions[-1]
positions.append(nextpos(lastpos, direction))
distance -= 1
return positions[1:]

def nextpos((x, y), dir):
if dir   == 'R': return x+1, y
elif dir == 'L': return x-1, y
elif dir == 'U': return x, y+1
elif dir == 'D': return x, y-1
``````

Part two changes the game on us by asking for the intersection that is "cheapest" to reach rather than just the closest to the starting point. Alright then, we can keep track of that at the same time as creating the path.

``````def best_intersection(wire1, wire2):
path1, distances1 = get_path_and_distances(wire1)
path2, distances2 = get_path_and_distances(wire2)
intersections = path1.intersection(path2)
return min([distances1[i] + distances2[i] for i in intersections])

def get_path_and_distances(wire):
positions = [(0, 0)]
travelled = 0
distances = {}
for section in wire:
direction = section
distance = int(section[1:])
while distance > 0:
lastpos = positions[-1]
newpos = nextpos(lastpos, direction)
positions.append(newpos)
travelled += 1
distance -= 1
if newpos not in distances:
distances[newpos] = travelled
return set(positions[1:]), distances             ``````