Source: Two Steps Forward
Part 1: Create a 4x4 grid of rooms with doors
Up,Down,Left, andRight from each location. To determine if a door is currently open:
- Calculate
MD5(salt + sequence)where sequence is a string containing any combination ofUDLRdepending on how you got to this room- The first four hex values represent the doors
Up,Down,Left, andRight respectively:bcdefmeans open; anything else is closed
Find the shortest path from
(0, 0)to(3, 3).
This problem is interesting because due to the nature of hashes, being in the same location in the grid doesn’t necessarily mean that the same doors are open. At the start, (0, 0) is based on MD5(salt), but if you go Down and then back Up, it’s based on MD5(salt + DU). So different doors may (and quite often will) be open. Quite often, you can go through a door and not go back the way you came.
The solution is still very similar to what we’ve seen before though. A breadth first search, using complex numbers for coordinates:
# Moving in the given direction adds this to the initial position
offset = {
'U': 0-1j,
'D': 0+1j,
'L': -1,
'R': +1,
}
# Order of the first four characters in the hash
order = 'UDLR'
def location(path):
return sum(offset[char] for char in path)
def solved(path):
return location(path) == 3+3j
def moves(path, password):
'''Yield the possible moves from the current and path.'''
current = location(path)
hash = hashlib.md5((password + path).encode()).hexdigest()
for offset_char, hash_char in zip(order, hash):
next = current + offset[offset_char]
if hash_char in 'bcdef' and 0 <= next.real < 4 and 0 <= next.imag < 4:
yield offset_char
def solve(password):
'''Find the shortest path through the maze.'''
q = queue.Queue()
q.put('')
while not q.empty():
path = q.get()
if solved(path):
return path
for move in moves(path, password):
q.put(path + move)
if mode == 'return':
raise Exception('No solution')
print(solve(args.password))
Part 2: How long is the longest path that reaches
(3, 3)? (Don’t count paths that reach(3, 3)and double back.)
One possibility would be just to generate all possible paths recursively:
def list_all_recursive(password):
'''Yield all paths through the maze using a recursive solution.'''
def generate(path):
if solved(path):
yield path
for move in moves(path, password):
yield from generate(path + move)
yield from generate('')
Unfortunately, Python doesn’t deal well with that much recursion. You can up the built in limit with sys.setrecursionlimit
, but that’s as likely to run your computer out of RAM as it is to actually solve the problem. Instead, we can just use the same code as the first time, but expand it with a mode that will yield solutions as we find them:
def solve(password, mode = 'return'):
'''
Find the shortest path through the maze.
Mode can be:
return: return the first = shortest path
yield: yield all paths
'''
q = queue.Queue()
q.put('')
while not q.empty():
path = q.get()
if solved(path):
if mode == 'return':
return path
elif mode == 'yield':
yield path
continue # Don't look for solutions that hit the end and come back
for move in moves(path, password):
q.put(path + move)
if mode == 'return':
raise Exception('No solution')
best_length, best_solution = 0, None
for solution in solve(args.password, mode = 'yield'):
if len(solution) > best_length:
best_length = len(solution)
best_solution = solution
print('{}\n{} steps'.format(best_solution, best_length))
That’s a pretty interesting problem. In theory, there doesn’t have to actually be an upper bound on that solution. In practice, since only 5 of the 16 possible values for each door are open, it will tend to close off solutions eventually.