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)
Quick.
$ python3 run-all.py day-19
day-19 python3 networkout.py input.txt 0.24499297142028809 DWNBGECOMY; 17228