You're trying to access a secure vault protected by a 4x4 grid of small rooms connected by doors. You start in the top-left room (marked S), and you can access the vault (marked V) once you reach the bottom-right room:
#########
#S| | | #
#-#-#-#-#
# | | | #
#-#-#-#-#
# | | | #
#-#-#-#-#
# | | |
####### V
Fixed walls are marked with #, and doors are marked with - or |.
The doors in your current room are either open or closed (and locked) based on the hexadecimal MD5 hash of a passcode (your puzzle input) followed by a sequence of uppercase characters representing the path you have taken so far (U for up, D for down, L for left, and R for right).
Only the first four characters of the hash are used; they represent, respectively, the doors up, down, left, and right from your current position. Any b, c, d, e, or f means that the corresponding door is open; any other character (any number or a) means that the corresponding door is closed and locked.
To access the vault, all you need to do is reach the bottom-right room; reaching this room opens the vault and all doors in the maze.
For example, suppose the passcode is hijkl. Initially, you have taken no steps, and so your path is empty: you simply find the MD5 hash of hijkl alone. The first four characters of this hash are ced9, which indicate that up is open (c), down is open (e), left is open (d), and right is closed and locked (9). Because you start in the top-left corner, there are no "up" or "left" doors to be open, so your only choice is down.
Next, having gone only one step (down, or D), you find the hash of hijklD. This produces f2bc, which indicates that you can go back up, left (but that's a wall), or right. Going right means hashing hijklDR to get 5745 - all doors closed and locked. However, going up instead is worthwhile: even though it returns you to the room you started in, your path would then be DU, opening a different set of doors.
After going DU (and then hashing hijklDU to get 528e), only the right door is open; after going DUR, all doors lock. (Fortunately, your actual passcode is not hijkl).
Passcodes actually used by Easter Bunny Vault Security do allow access to the vault if you know the right path. For example:
ihgpwlah, the shortest path would be DDRRRD.kglvqrro, the shortest path would be DDUDRLRRUDRD.ulqzkmiv, the shortest would be DRURDRUDDLLDLUURRDULRLDUUDDDRR.Given your vault's passcode, what is the shortest path (the actual path, not just the length) to reach the vault?
This is quite similar to Day 13, where we had to find a short path through the maze. This time around, whether the next point is valid or not (its door is open or closed) depends on the path taken to reach there (so like life!).
At any point, whether the doors are open or not is dependant on the path taken to reach that room. In specific, the MD5 checksum of the input string suffixed by the path - as directions abbreviated:
U UP
D DOWN
L LEFT
R RIGHT
Therefore, the strategy to solve this must be the same as that used on Day 13, where we use a queue to store the paths we have traversed. There is a case that must be stated before we begin - this time, if we move back to a previous point, the doors that are open might change as the path itself has changed. So instead of a queue, we'll use a priority heap to store that paths and work only on those paths that have not been iterated yet.
The priority will be the length of the path - this way, the agorithm will try to iterate over all the shorter paths first - of do a BFS (breadth-first-search). Another option to use instead of a heap is to use a sorted list. Python has the bisect module that can maintain a sorted list.
import bisect
items = []
bisect.insort(items, element)
items.pop(0) <-- smallest element
Algorithm:
Input and Test data
In [1]:
with open('../inputs/day17.txt', 'r') as f:
path_string = f.readline().strip()
TEST_DATA = (
'ihgpwlah',
'kglvqrro',
'ulqzkmiv'
)
Point
As with before, having a namedtuple makes the code cleaner and easier to read.
In [2]:
from collections import namedtuple
Point = namedtuple('Point', ('x', 'y', 'path'))
Checksum
Calculating the checksum is simply taking the MD5 hash of it.
In [3]:
import hashlib
def md5(string):
md5 = hashlib.md5()
md5.update(string.encode('ascii'))
return md5.hexdigest()
Directions
We maintain a tuple of points for directions. This allows the direction to match the specific character in the checksum.
1st character signals open door --> 1st element in tuple gives direction
In [4]:
directions = (
Point(0, -1, 'U'),
Point(0, 1, 'D'),
Point(-1, 0, 'L'),
Point(1, 0, 'R')
)
Start and End states
It is very important to know what exactly is the starting and ending state of the algorithm. In this case, the ending state is the room at the very bottom right, with the co-ordinates (3, 3). Since we do not know its path, and it is not required to declare it, we use None instead.
In [5]:
start_point = Point(0, 0, path_string)
end_point = Point(3, 3, None)
Validating points / moves
A point is valid if it stays within the boundaries of the 4 x 4 matrix.
In [6]:
def valid_point(point):
if 0 <= point.x < 4 and 0 <= point.y < 4:
return True
Checking for open doors
We take the first four characters of the checksum, compare them against the given condition of being less than 10 or 'a' which signlas a closed door. Return only directions that are valid - open doors.
'a' or less --> closed
others --> open
In [7]:
def open_doors(checksum):
def is_open(character):
if character > 'a':
return True
return False
return [
directions[index]
for index, character in enumerate(checksum[:4])
if is_open(character)]
Heap
We declare a states list for holding the heap. The heap contains only the starting point at this time. While the length of the path string at this point is the length of the input, it is not a valid answer nor reflects the final path string. I chose to use the length of the entire string so as to avoid calculating the difference between the input string and the direction string everytime. It also makes code easier to read, IMHO.
In [8]:
from heapq import heappush, heappop
states = []
heappush(states, (len(start_point.path), start_point))
Run the algorithm
In [9]:
while states:
_, current_state = heappop(states)
if current_state.x == end_point.x and current_state.y == end_point.y:
print('answer', current_state.path[len(path_string):])
break
moves = open_doors(md5(current_state.path))
for move in moves:
new_path = Point(
current_state.x + move.x,
current_state.y + move.y,
current_state.path + move.path)
if not valid_point(new_path):
continue
heappush(states, (len(new_path.path), new_path))
You're curious how robust this security solution really is, and so you decide to find longer and longer paths which still provide access to the vault. You remember that paths always end the first time they reach the bottom-right room (that is, they can never pass through it, only end in it).
For example:
ihgpwlah, the longest path would take 370 steps.kglvqrro, the longest path would be 492 steps long.ulqzkmiv, the longest path would be 830 steps long.What is the length of the longest path that reaches the vault?
Now instead of finding the shortest path, we have to find the longest path. While earlier we used BFS, which was great for iterating over shorter path lengths, this time, we must use DFS (depth-first-search) to iterate over the longer branches first. This won't make much of a difference, as we have to iterate all paths anyways.
In depth first search, instead of a heap or queue, we use a stack where we insert and remove elements from the end. This allows consecutive iteration of the last state - hence giving it depth.
We store the lengths of all paths reaching the end point, and later retrieve the largest of them.
Note: The paths stored are prefixed with the input, therefore for the final answer, it is necessary to subtract the length of the input string from it.
In [10]:
states = [(0, start_point)]
paths = []
while states:
_, current_state = states.pop()
if current_state.x == end_point.x and current_state.y == end_point.y:
# print(len(current_state.path))
paths.append(len(current_state.path))
continue
moves = open_doors(md5(current_state.path))
for move in moves:
new_path = Point(
current_state.x + move.x,
current_state.y + move.y,
current_state.path + move.path)
if not valid_point(new_path):
continue
states.append((len(new_path.path), new_path))
print('answer', max(paths) - len(path_string))
== END ==