AoC 2016 Day 17: Md5 Maze

Source: Two Steps Forward

Part 1: Create a 4x4 grid of rooms with doors Up, Down, Left, and Right from each location. To determine if a door is currently open:

  • Calculate MD5(salt + sequence) where sequence is a string containing any combination of UDLR depending on how you got to this room
  • The first four hex values represent the doors Up, Down, Left, and Right respectively: bcdef means 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.

comments powered by Disqus