Two Steps Forward

Advent of Code 2016 Day 17

Try the simulator to find both paths for your puzzle input!

Part 1

1. This calls for a simulator!
2. Searching for a hashing algorithm
3. Learning to use the hashing algorithm
4. Building my simulator
5. Testing my simulator on the example strings
6. 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 keyCodes 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!

I found a winning path!

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

1. I was ready to forego an attempt
2. Writing a working recursive algorithm in under a half hour
3. 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