Robert Mion

Posted on Jan 1, 2023

Blizzard Basin

#adventofcode #algorithms #javascript #programming

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 <>^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')

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()'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:

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 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).

DEV Community