Advent of Code 2016 Day 17
Try the simulator to find both paths for your puzzle input!
Part 1
- This calls for a simulator!
- Searching for a hashing algorithm
- Learning to use the hashing algorithm
- Building my simulator
- Testing my simulator on the example strings
- Using my simulator in hopes of generating my correct answer
This calls for a simulator!
- I don't anticipate solving this puzzle
- Because it is another
pathfinding
one - But I am excited to build my first simulator of 2016
- Because I really want to make traversing the rooms interactive
This will likely take a lot of work.
I'll go one step at a time.
Starting with...how do I make an MD5 hash from some passcode?
Searching for a hashing algorithm
-
MD5
is a cryptographic hashing algorithm - Those sorts of things are not something I'm keen to build from scratch
- Luckily, after a few Google searches, I found a library I can import into my JavaScript program: Crypto JS
Now, how do I use this thing?
Learning to use the hashing algorithm
The documentation lets on that I can do this:
const MD5 = require('crypto-js/md5')
let hash = MD5(passcode)
When I try that - replacing passcode
with hijkl
, I see this in my console:
{
words: [ -824574894, 1142503206, 1182055587, -189106808 ],
sigBytes: 16
}
That's definitely not what I want, nor what I expected.
What I want is a string with ced9
as the first four characters.
Again, how do I get that? Am I even close?
It turns out, yes, I was very close.
Thanks to this Stack Overflow commenter, I found the missing method call:
const MD5 = require('crypto-js/md5')
let hash = MD5(passcode).toString()
Viola! I now see this when replacing passcode
with hijkl
:
ced9fc52441937264674bca3f4ba7588
Just to be sure:
const MD5 = require('crypto-js/md5')
let hash = MD5(`hijklD`).toString()
Correctly outputs:
f2bc...
MD5 hashing: solved!
Building my simulator
My checklist includes:
- Re-build the 4x4 grid
- Listen for arrow key events
- Display the grid for any state
- Mark locked doors with
X
- Prevent the user from performing invalid moves
- Track the current running path
- Store the original passcode for use upon each retry
- Store each failed attempt to display as a list
Wow! That's a lot!
First steps
- Input field for passcode
- Button to start new round
- Display the grid
Build the grid as a nested array
This felt easy:
let map = "#########\n#S| |..."
map.replace('S',' ').split('\n').map(el => el.split(''))
- Replace the
S
with an empty space - Turn each line into an array of strings
- Turn each string into an array of strings
Listen for presses of arrow keys
- DOM event:
onkeydown
- Arrow keyCodes:
37-40
document.onkeydown = (event) => {
if ([37,38,39,40].includes(event.keyCode)) {
// valid key pressed
console.log(CryptoJS.MD5(passcode + directions[e.keyCode]).toString())
}
}
Generate new hash based on pressed arrow key
- Earlier, I found CryptoJS and used it in a NodeJS environment
- Now, I need a
script
to use it in a web client - Thankfully, CryptoJS is hosted as a script on a CDN
I added it to my page:
<script src="https://cdnjs.cloudflare.com/ajax/libs/crypto-js/3.1.2/rollups/md5.js"></script>
Then incorporated it into my event listener:
document.onkeydown = (event) => {
if ([37,38,39,40].includes(event.keyCode)) {
console.log(
CryptoJS.MD5(
passcode + directions[e.keyCode]
).toString()
)
}
}
Using hijkl
as my input, when I press left
, up
, right
, and down
, I correctly see:
17b6066580adc50e8920044e01969994
304303fe46c04cd9d5c64ca76649fd09
451f764c8247b415b72767c325c1c282
f2bc79f0aa56c63811cfc74bea1b4ece
Hooray! The hashing library is working in the browser!
Determining open/locked doors/walls
- I need an array - in directional order
Up
,Down
,Left
,Right
- Where each value is a boolean indicating whether I can move in that direction
- And I need to start from the MD5 hash of the current path
Calculating invalid moves, assuming all are doors:
Extract the first four characters of the hash
Split at each character into a 4-element array of single-character strings
For each character
If the character is one of b,c,d,e,f
Update the character to true
Else
Update the character to false
Accounting for walls where a move was true
:
Based on the row of the player
If in the top row
Update the boolean for Up to false
Else, if in the bottom row
Update the boolean for Down to false
Based on the column of the player
If in the left-most column
Update the boolean for Left to false
Else, if in the right-most column
Update the boolean for Right to false
The array should now accurately reflect all valid moves from the player's current room.
Marking locked doors on the map
I'll use this 4-element array of relative coordinates:
coords = [
[-1,0],
[1,0],
[0,-1],
[0,1]
]
And here's how I'll use it:
Filter the list of coordinates
Keep only the ones that share an index with the boolean false in the array representing valid moves
For each remaining coordinate
If the character in the cell indicated by the relative coordinate in relation to the player's room is a door character
Mark it with an X by updating the cell's value in a temporary clone of the map
Listening for - and handling - arrow key presses
- I'll listen for any key press on the page
- Since it could be any key, I must check for one of the four arrow keys
- Their
keyCode
s are:37-40
- Once I've identified that an arrow key was pressed, I need to ensure the intended move is possible: not thru a wall or locked door
- For this, I'll leverage the four-element array of booleans that I store when parsing the first four characters of a hash
- I'll compare indices in that array with numbers stored as part of a legend mapping keycodes to a directional letter and an index
This is my legend:
{
37: ['L',2],
38: ['U',0],
39: ['R',3],
40: ['D',1]
}
This is one variant of the boolean-ed array:
up down left right
[false, true, false, false]
In this scenario, the only possible move is down.
In my algorithm, the condition looks like this:
If the boolean at the index as specified by the second element in the array associated with the keyCode of the key pressed...is true
It was a valid move, so continue!
Else
It was an invalid move, so do nothing
As long as the move was valid, my algorithm proceeds:
Append to my path string the first element in the array associated with the keyCode of the key pressed
Display the new path string in the simulator
Update the player coordinates to reflect a cell two spaces away in the appropriate direction
If the player landed on the secret vault's cell
Update the path string in the simulator to indicate it was a winning path
Else
Perform the series of steps outlined above to determine the next possible moves
Additional checklist items
- I set the input element to readonly when the button is pressed to generate and display the map - to prevent changes to it unless the page is reloaded
- I use - and append to - an unordered list to display each attempted path
Troubleshooting my simulator
- I didn't reset some values earlier than a dependent operation, causing the map of rooms to incorrectly retain a previous attempt's state after a new attempt was started
- I didn't store a nested array in a variable when attempting to chain several method calls together - this kept resulting in a TypeError until I first created a variable...I'm still unsure why
- I incorrectly attempted accessing array indices using the wrong syntax: beginner mistakes of writing too fast and not double-checking my code
Testing my simulator on the example strings
For the initial, 5-character example:
- I immediately noticed the correctly-marked open and locked doors
- Moving down correctly showed a locked down door and open right and up doors
- Moving right was correctly a dead-end
- Moving up and then right was also correctly a dead-end
For the next two examples, performing the moves resulting correctly in arriving at the secret vault!
I didn't try the last example, since it was really long.
Using my simulator in hopes of generating my correct answer
This was as fun as I anticipated!
Unfortunately, it wasn't the shortest one.
I found a shorter winning path!
Thankfully, it was the shortest one!
Here's an animation of my puzzle input's shortest path:
Part 2
- I was ready to forego an attempt
- Writing a working recursive algorithm in under a half hour
- Updating my simulator to play out both paths
I was ready to forego an attempt
- The thought of using my simulator to find a path longer than 20 steps - let alone hundreds! - felt pointless
- And the reason I built my simulator is because I wasn't confident enough to write an algorithm that could programmatically calculate even a single winning path
- So how was I going to write one that could calculate the longest path?
Thankfully, I had a full afternoon and evening to realize I had already built the integral parts of a working algorithm.
Writing a working recursive algorithm in under a half hour
That's right! I channeled my inner Neo and nailed this challenge!
How my recursive algorithm works:
Setup:
Set paths as an empty list
Set passcode as the input string
Set path as an empty string
Set room as the coordinate (1,1)
Set legend as the ordered list (U,D,L,R)
Set coordinates as the similarly ordered list of relative coordinates ((-1,0),(1,0),(0,-1),(0,1))
Create a sub-routine that expects a path string and a pair of coordinates and returns a four-element array of booleans indicating all subsequent valid moves based on an MD5 hash and the location of the current room
Recursive function:
Accept two parameters: a path string and a pair of coordinates indicating the current room
If the current room is the one with the secret vault (4,4)
Add the accumulated path string to the paths list
Else
Set moves as the 4-boolean array returned from calling the sub-routine
As long as one boolean in moves is true
For each true boolean
Call this recursive function, passing as arguments:
1. The existing path string concatenated with the string in legend at the same index as the index of this boolean in moves
2. The coordinates of the room being entered
Sort paths by length in descending order
Return the length of the first path
- Surprisingly, I did very little debugging!
- After I finished writing it, I tested it on each example input
- At first, I checked for matches of shortest path
- It found them all, including my puzzle input!
- Then, I swapped the sorting function to find longest path
- It generated the correct answer for my puzzle input!
Updating my simulator to play out both paths
- I already have a button to let a user attempt any path
- Now, I want to reveal both paths at the press of a button
- I'll have to run my recursive function to generate the path as a string of directional letters
- Then turn that string into an array of arrow keyCodes
- And start an interval that automatically calls my existing functions to simulate the subsequent pressing of each correct arrow key
Here I go!...
Success!
- Clicking either button immediately after a page refresh simulates that path and builds the path string in real-time
- I had to add a few new variables and adjust some code that I copy-pasted from other functions
- But, overall, it was a relatively easy enhancement!
Here is it simulated an example shortest path:
And here is the same example's longest path:
I did it!!
- I'm shocked and delighted I solved both parts of another shortest path puzzle!
- I built my first simulator of 2016
- I used it to discover the shortest path for my puzzle input!
- I wrote a few small algorithms along the way!
- I used my first cryptographic library, too!
- I almost avoided Part 2 out of intimidation!
- Then - after realizing I already had all the pieces - solved it by writing a recursive algorithm in under a half hour!
I'm thankful the puzzle-maker kept the grid size small, so that I felt incentivized to attempt this puzzle...and not give up due to the seemingly massive scope in which a shortest path might reside.
This puzzle goes in my Top 5, along with Day 19's puzzle:
- It was fun to build the simulator
- It was rewarding to build the recursive algorithm
- It was fulfilling to watch my algorithm play out in the simulator
Top comments (0)