DEV Community

Cover image for Blizzard Basin
Robert Mion
Robert Mion

Posted on

Blizzard Basin

Advent of Code 2022 Day 24

Try the simulator using your puzzle input!

Simulator in all its glory

Part 1

  1. It's all been leading up to this
  2. What I hope to accomplish
  3. Simulator: re-create the input as a 2D array
  4. Determining start and end coordinates
  5. Moving the blizzards
  6. Cataloging the blizzards
  7. Wrapping the blizzards
  8. Re-rendering the grid
  9. Representing overlapping blizzards with a number
  10. Accounting for player movement and waiting
  11. Using my simulator until I get [insert adjective here]
  12. Tell me where I can go
  13. 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:
Showing the puzzle input as a grid

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('.')
]
Enter fullscreen mode Exit fullscreen mode

I temporarily placed markers on my generated map using E and X to validate my algorithm works correctly:
Start and End markers correctly placed

Moving the blizzards

Four types of blizzards, each denoting a direction of movement:

let moves = {
  '>': [0,1],
  'v': [1,0],
  '<': [0,-1],
  '^': [-1,0]
}
Enter fullscreen mode Exit fullscreen mode

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.#
######
Enter fullscreen mode Exit fullscreen mode

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.#
#.....#
#####.#
Enter fullscreen mode Exit fullscreen mode

I'd like a data structure akin to this:

{
  '>': [
    [2, 1]
  ],
  'v': [
    [4, 4]
  ]
}
Enter fullscreen mode Exit fullscreen mode

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])
    }
  }
}
Enter fullscreen mode Exit fullscreen mode

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.#
######
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
}
Enter fullscreen mode Exit fullscreen mode

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 <>^vs 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')
Enter fullscreen mode Exit fullscreen mode

Alas, I can now sit back and watch the storm play out if I so choose:
Blizzards moving correctly

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
Enter fullscreen mode Exit fullscreen mode

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
  })
}
Enter fullscreen mode Exit fullscreen mode

My simulator is now in-line with the example diagrams:
Numbers and symbols like in the instructions

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]
}
Enter fullscreen mode Exit fullscreen mode

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;
    }
  }
})
Enter fullscreen mode Exit fullscreen mode

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;
Enter fullscreen mode Exit fullscreen mode

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()'s regex only accounted for the four symbols. I forgot to reset cells with E,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 my moves object with relative coordinates 0,0. And more wonderfully, it let me remove a giant if 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:
Shortest path in example input simulated

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:
Added available move buttons

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 Waits
  • 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)