Source: A Series of Tubes
Part 1: Take a network diagram of the following form:
| | +--+ A | C
F—|–|-E—+ | | | D +B-+ +–+e>
Then, calculate the path:
def path(pt): '''Yield all points along a given path.''' x, y = pt xd, yd = (0, 1) steps = 0 while True: pt = x, y = x + xd, y + yd c = data.get(pt) if not c: break elif is_point(c): yield c elif c == '+': for new_xd, new_yd in [(-1, 0), (1, 0), (0, -1), (0, 1)]: # Back the way we came if new_xd == -xd and new_yd == -yd: continue elif not data.get((x + new_xd, y + new_yd)): continue else: xd, yd = new_xd, new_yd break print(''.join(path(entry)))
That’s fairly elegant. It’s similar to a flood fill except there’s always only one way to go. The two complications that come up are:
- When crossing another line, you have to just ignore it and keep going. Only turn when you see a
- When turning, make sure you don’t go back the way you came.
Part 2: How many steps did you take?
Only a slight tweak to count the path length along the way (using a global variable since I didn’t want to change the return value since it was a generator):
last_step_count = 0 def path(pt): '''Yield all points along a given path.''' global last_step_count last_step_count = 0 ... while True: ... last_step_count += 1 ... print(last_step_count)
$ python3 run-all.py day-19 day-19 python3 networkout.py input.txt 0.24499297142028809 DWNBGECOMY; 17228