Advent of Code 2022 Day 24
Try the simulator using your puzzle input!
Part 1
- It's all been leading up to this
- What I hope to accomplish
- Simulator: re-create the input as a 2D array
- Determining start and end coordinates
- Moving the blizzards
- Cataloging the blizzards
- Wrapping the blizzards
- Re-rendering the grid
- Representing overlapping blizzards with a number
- Accounting for player movement and waiting
- Using my simulator until I get [insert adjective here]
- Tell me where I can go
- Last chance: a recursive algorithm
It's all been leading up to this
- A 2D grid
- A
shortest path
problem - A
graph search
algorithm challenge - Multiple
rounds
- Pieces moving based on rules
- Movement wraps around the grid
- First part dictates whether a piece can move, second part moves all pieces
What I hope to accomplish
- Build a simulator
- Where I can use arrow keys to express each directional move and a specific key to express
don't move
- Prevent an invalid move
- Accept a valid move and update the grid to accommodate the change
- Display the total moves performed
If I can build a simulator to those specifications, then I think I can identify at least one path from start to end...if by no other means than button-mashing.
I kind of hope that building the simulator helps me realize a recursive algorithm that I could use to explore several viable paths thru the maze, with one being the shortest.
Ultimately, I don't anticipate solving Part 1, sadly.
Let's see how this goes!
Simulator: re-create the input as a 2D array
I followed my usual steps for building a new simulator:
- Copy-paste code into a new sandbox
- Update titles, ids, default input values
- Adjust font sizes
- Write the first few lines in my initialization function
At this point, my simulator parses input from a textarea
, creates a 2D array and displays it on the page:
Determining start and end coordinates
Your expedition begins in the only non-wall position in the top row and needs to reach the only non-wall position in the bottom row.
My algorithm in JavaScript:
let start = [
0,
grid[0].indexOf('.')
]
let end = [
grid.length - 1,
grid[grid.length - 1].indexOf('.')
]
I temporarily placed markers on my generated map using E
and X
to validate my algorithm works correctly:
Moving the blizzards
Four types of blizzards, each denoting a direction of movement:
let moves = {
'>': [0,1],
'v': [1,0],
'<': [0,-1],
'^': [-1,0]
}
Then comes the wrapping.
- There are walls on all four edges
- If the next move would push a blizzard into a wall...
- ...it should instead move to the cell two in from the opposite grid edge in the same row or column
When diagramed:
< moves to A
v moves to B
> moves to C
^ moves to D
######
#.B^.#
#<..A#
#C..>#
#.vD.#
######
I foresee an elaborate switch
statement and/or series of if...else if
clauses.
But first, I need to know where all the blizzards are!
Cataloging the blizzards
I need to store the location and facing of each blizzard.
Using the simpler example input:
#.#####
#.....#
#>....#
#.....#
#...v.#
#.....#
#####.#
I'd like a data structure akin to this:
{
'>': [
[2, 1]
],
'v': [
[4, 4]
]
}
I figure it will make things easier to group them by their facing. That way I can reference the earlier data structure to move them.
My algorithm in JavaScript that generates the above data structure:
for (let row = 0; row < grid.length; row++) {
for (let col = 0; col < grid[0].length; col++) {
if (['>','v','<','^'].includes(grid[row][col])) {
blizzards[grid[row][col]].push([row, col])
}
}
}
I now know where each blizzard is and have a map for how to move them.
Time to write the logic that handles wrapping.
Wrapping the blizzards
My helpful diagram again:
######
#.B^.#
#<..A#
#C..>#
#.vD.#
######
My algorithm in pseudocode:
Wrap when the blizzard is:
Facing left and in column 1
To same row, column (row length - 2)
Facing right and in column (row length - 2)
To same row, column 1
Facing up and in row 1
To same column, (grid length - 2)
Facing down and in row (grid length - 2)
To same column, row 1
My movement and wrapping function in JavaScript:
function calculateNewBlizzardPositions() {
let positions = {'>': [], 'v': [], '<': [], '^': []}
for (let blizzard in blizzards) {
switch (blizzard) {
case '<':
blizzards[blizzard].forEach(([row, col]) => {
if (col == 1) {
positions[blizzard].push([row, grid[row].length - 2])
} else {
positions[blizzard].push([row, col - 1])
}
})
break;
case '>':
blizzards[blizzard].forEach(([row, col]) => {
if (col == grid[row].length - 2) {
positions[blizzard].push([row, 1])
} else {
positions[blizzard].push([row, col + 1])
}
})
break;
case '^':
blizzards[blizzard].forEach(([row, col]) => {
if (row == 1) {
positions[blizzard].push([grid.length - 2, col])
} else {
positions[blizzard].push([row - 1, col])
}
})
break;
case 'v':
blizzards[blizzard].forEach(([row, col]) => {
if (row == grid.length - 2) {
positions[blizzard].push([1, col])
} else {
positions[blizzard].push([row + 1, col])
}
})
break;
}
}
return positions
}
Re-rendering the grid
I can render the grid based on the initial puzzle input.
Now I need to re-render the grid based on every blizzard's new position - and eventually the player's position.
I went the long route:
- Convert array to string
- Replace all
<>^v
s with.
s - Convert string to array
- Update appropriate array values with
<>^v
based on their new coordinates
My algorithm in JavaScript:
blizzards = calculateNewBlizzardPositions(blizzards)
grid = grid
.map(row => row.join(''))
.join('\n')
.replaceAll(/[<>v^]/g, '.')
.split('\n')
.map(line => line.split(''))
for (let blizzard in blizzards) {
blizzards[blizzard].forEach(([row, col]) => {
grid[row][col] = blizzard
})
}
gridEl.textContent = grid.map(row => row.join('')).join('\n')
Alas, I can now sit back and watch the storm play out if I so choose:
To truly re-create the diagrams from the instructions, I need to represent any overlapping blizzards with a number (2-4
).
Representing overlapping blizzards with a number
Build a dictionary with coordinates as keys and counts as values
For each coordinate pair in each of the four symbol lists
Create a key if it doesn't exist and set it's value to 0
Increment the value of the key by 1
For each coordinate pair in each of the four symbol lists
Place in the cell of the grid either:
The symbol if the count in the dictionary is 1
The count if the count in the dictionary is greater than 1
My updated algorithm in JavaScript:
let counts = {}
for (let blizzard in blizzards) {
blizzards[blizzard].forEach(b => {
let position = b.join('|')
if (!(position in counts)) {
counts[position] = 0
}
counts[position]++
})
}
for (let blizzard in blizzards) {
blizzards[blizzard].forEach(([row, col]) => {
grid[row][col] = counts[[row, col].join('|')] > 1
? counts[[row, col].join('|')]
: blizzard
})
}
My simulator is now in-line with the example diagrams:
Accounting for player movement and waiting
Now for the real challenge:
- Handling keyboard entry of the next move
- Checking whether the desired move is valid
- Only updating the board when the move is valid
I didn't end up using my four-key-value-pair relative coordinate dictionary moves
.
That's great, because I can re-label the keys to match the four codes of the keys the user can press:
let moves = {
'ArrowRight': [0,1],
'ArrowDown': [1,0],
'ArrowLeft': [0,-1],
'ArrowUp': [-1,0]
}
I'll listen for the keyup
event and perform different actions based on the string value of event.code
, only if the Start
button has been pressed:
document.addEventListener('keyup', function(event) {
if (playEl.getAttribute('disabled') == 'disabled') {
switch (event.code) {
case 'Slash':
break;
case 'ArrowUp':
break;
case 'ArrowDown':
break;
case 'ArrowLeft':
break;
case 'ArrowRight':
break;
}
}
})
I decided to let the forward slash key just above the left arrow key map to the action of waiting.
Luckily, as my algorithm is currently written, that means I can just call the function that moves the blizzards and re-renders the grid:
case 'Slash':
nextMinute()
break;
I need to know what the most recently passed minute is, so I added a tracker for that which increments appropriately.
Handling the Slash
case was easy.
But each of the others will require breaking apart my current nextMinute()
function so that I can play out the next minute in order to determine whether the move is valid, and only if it is actually update the board...otherwise don't move any blizzards.
Off I go!
...
I made things more complicated than necessary.
And I overlooked several things.
Here's what I learned, fixed and refactored:
- My
replaceAll()
'sregex
only accounted for the four symbols. I forgot to reset cells withE,2,3,4
! - When checking whether the proposed player move is valid, I forgot to check whether it was into a wall! This required an extra line in my nested
for
loop to build a new array that tracked the coordinates of all walls. Then an added condition to my valid move check. - I overlooked how waiting could be an invalid move, since a blizzard could move into my spot. This prompted me to add a
Slash
key to mymoves
object with relative coordinates0,0
. And more wonderfully, it let me remove a giantif
clause that just checked for the Slash key being pressed. Now my algorithm accounts for any of the five keys in a single conditional!
After all that delightful debugging, my simulator now correctly plays out the sample walkthrough:
Using my simulator until I get [insert adjective here]
Now that it works - on the sample input, at least - I should probably try exploring a few paths and see if I ever get to the exit.
I suppose I'll try until I get frustrated, bored, or just impatient.
No matter what, I'm proud that I made this simulator.
...
I tried a few times.
I can't make it past the 10th row and 6th column without being unable to move or wait.
It may be helpful to know - at any given minute - which actions I could take.
Tell me where I can go
I want to add five buttons to my simulator that light up if the corresponding action is possible in the next minute.
It required some more DOM manipulation.
But more importantly it required some redundant code to play out the next minute before and after a key press: once to light up the buttons, then again to process the action.
It was a good exercise, though.
And my simulator is cooler because of it:
Sadly, I'm no closer to finding a single path to the finish line.
Last chance: a recursive algorithm
I really want a gold star.
I still doubt I'm going to get it.
But I'm confident I can build a recursive function from the code in my simulator that may be able to find a path through the maze.
Off I go again!
...
I built the recursive function:
- For a while it wasn't getting past the first downward move
- After a lot of head scratching and code analysis, I discovered my error: I wasn't updating the dictionary of blizzard locations
- I set it to display the number of minutes if it ever moves the player to the target end coordinate
- I pressed run and waited, hoping I wouldn't hit any call stack-related errors
- I eventually saw a number!
- Then more of that same number
- Then more of one less than that number!
- Then nothing
- For a while
In the off-chance this was the correct answer, I decided to submit it.
Wrong answer. Too high.
I spent a lot more time trying to optimize my recursive function so it would:
- Stop if the path had a ton of
Wait
s - Stop if the path tried to revisit the starting coordinate
- Stop if the minutes ever got over the smallest number I knew it could reach
- Explore each direction in different orders
Nothing worked.
In fact, I never saw those two numbers again.
It was time to throw in the towel.
What I accomplished
- I built an interactive simulator that should work for any valid puzzle input!
- I practiced tons of techniques used when working with multiple data types in JavaScript!
- I built a recursive algorithm that found a few seemingly valid paths thru the maze!
- I proved yet again that I don't have the skills to solve puzzles involving graphs with paths that double-back on certain nodes (e.g. 'A' -> 'B' -> 'A' -> 'B')
I'm bummed I didn't earn a gold star.
But I'm impressed with all the code I wrote and what I built while attempting to solve today's puzzle.
I'd love to earn one more gold star tomorrow and tie my lowest star count.
But if I don't, at least I'll no longer have a tie for lowest star count (currently 34
from years 2021
and 2019
).
Top comments (0)