Regolith Reservoir

Advent of Code 2022 Day 14

Try the simulator using your puzzle input!

Part 1

Not this again!
Revealing the grid
Drawing the walls
Starting the fall
Attempting to re-create the fall with an algorithm
My near-flawless algorithm in JavaScript

Not this again!

A 2D grid
The input is a list of lines that make up walls
Something falls downward endlessly from a single point at the top
Goal: identify all the places where it lands on or slightly above a wall

The last time I encountered this puzzle I got as far as rendering the grid and it's many walls.

I wasn't about to try solving the puzzle visually. The grid was ridiculously tall. It would have taken ages.

And I had no idea how to even begin attempting to solve the puzzle algorithmically.

Thus, I earned 0/2 stars.

I suspect the same outcome this time:

I'll be successful at rendering the grid and its walls
Due to the area of the grid, I'll be too intimidated to attempt to solve it visually
I doubt I'll think of a way to solve it algorithmically

Still, I've got to try!

Revealing the grid

Parsing the input into lists of points

Given this:

498,4 -> 498,6 -> 496,6
503,4 -> 502,4 -> 502,9 -> 494,9

I want this:

[
  [ [ 498, 4 ], [ 498, 6 ], [ 496, 6 ] ],
  [ [ 503, 4 ], [ 502, 4 ], [ 502, 9 ], [ 494, 9 ] ]
]

My algorithm in JavaScript:

let walls = input
  .split('\n')
  .map(wall => {
    return wall
      .split(' -> ')
      .map(xy => {
        return xy
          .split(',')
          .map(Number)
      })
  })

Finding the bounding box

I need to programmatically find the smallest and largest X and Y coordinates among the lists of points.

For the example input, those four values are:

  <--X--->  <-Y->
[ 494, 503, 4, 9 ]

My algorithm in JavaScript:

let points = walls.flat()
let [minX, maxX, minY, maxY] = [
  Math.min(...points.map(xy => xy[0])),
  Math.max(...points.map(xy => xy[0])),
  Math.min(...points.map(xy => xy[1])),
  Math.max(...points.map(xy => xy[1]))
]

Creating the grid

I need a 2D array filled with . characters that has as many rows as the highest Y value and as many columns as the highest X value.

My algorithm in JavaScript:

let grid = new Array(maxY + 1)
  .fill(null)
  .map(el => new Array(maxX + 1)
      .fill(null)
      .map(el => '.')
  )

For the example input, this gets me a grid that is much wider than it needs to be.

But I'm betting that my puzzle input will feature coordinates that span X values that are closer to 0 than 494.

If that's not the case, then I can modify my algorithm to treat the smallest X value as the left-most column, making the grid far less wide.

Checking my puzzle input

My smallest X value is 460. How surprising!

I guess I need to update my grid-drawing algorithm to only make the grid much narrower - not creating an additional 460 columns.

Luckily, it was a simple edit to one line:

// Old
  .map(el => new Array(maxX + 1)

// New
  .map(el => new Array(maxX + 1 - minX)

My grid is a roughly 80 x 160 tile area.

That is a lot smaller than the grid in the previous Reservoir-themed puzzle.

Which makes me slightly more interested in attempting to solve it visually...

...assuming I can draw the walls correctly.

Drawing the walls

Lots of conditions that account for the directions of each wall segment
Then updating the correct cell in the grid, accounting for the reduced number of columns from the left edge

My algorithm in JavaScript with comments:

walls.forEach(wall => {
    for (let i = 0; i < wall.length - 1; i++) {
      if (wall[i][0] == wall[i + 1][0]) {
        // Same column
        if (wall[i][1] > wall[i + 1][1]) {
          // Line up
          for (let y = wall[i][1]; y >= wall[i + 1][1]; y--) {
            grid[y][wall[i][0] - minX] = "#"
          }
        } else {
          // Line down
          for (let y = wall[i][1]; y <= wall[i + 1][1]; y++) {
            grid[y][wall[i][0] - minX] = "#"
          }
        }
      } else {
        // Same row
        if (wall[i][0] > wall[i + 1][0]) {
          // Line left
          for (let x = wall[i][0]; x >= wall[i + 1][0]; x--) {
            grid[wall[i][1]][x - minX] = "#"
          }
        } else {
          // Line right
          for (let x = wall[i][0]; x <= wall[i + 1][0]; x++) {
            grid[wall[i][1]][x - minX] = "#"
          }
        }
      }
    }
  })

It worked, and therefore revealed the walls in my reservoir:

How interesting!

Doing this visually will be tricky...but seems possible!

At least worth a try!

Starting the fall

Simulating sand falling to cover the first wall in my puzzle input, before spilling over the left side:

Then, the second platform fills it's right side before sand overflows:

And here's the third platform before the next sand dropped will overflow:

And the fourth platform before the next sand dropped will overflow:

Playing all of this out gives me enough confidence to attempt re-creating as much of it as possible in an algorithm.

Attempting to re-create the fall with an algorithm

Three conditions:

Is the value in the cell below a .? Move down
Is the value in the cell left and below a .? Move down-left
Is the value in the cell right and below a .? Move down-right

It was that easy to re-create the first 24 steps outlined in the example!

Then came the abyss-identifying conditions:

Is the location of the cell that is down, down-right or down-left outside of the grid? Falls into the abyss.

Add to that some variables to track previous and current position, and previous and current sand counts.

Finally, some troubleshooting of the operators I used in my conditions and accounting for the lack of columns beyond the left edge.

Eventually, my algorithm worked as expected on the example input!

My near-flawless algorithm in JavaScript

let oldSand = -1
let newSand = 0
while (oldSand !== newSand) {
  oldSand = newSand
  let was = [500,0]
  let now = [500,1]
  while (
    String(was) !== String(now) && 
    now[0] - 1 - minX >= 0 &&
    now[0] + 1 - minX < maxX - minX &&
    now[1] + 1 < maxY
  ) {
    was = now.slice()
    if (grid[now[1] + 1][now[0] - minX] == '.') {
      // move down
      now[1]++
    } else if (grid[now[1] + 1][now[0] - 1 - minX] == '.') {
      // move down-left
      now[1]++
      now[0]--
    } else if (grid[now[1] + 1][now[0] + 1 - minX] == '.') {
      // move down-right
      now[1]++
      now[0]++
    }
  }
  if (
    now[0] - minX == 0 ||
    now[0] - minX == maxX - minX ||
    now[1] == maxY
  ) {
    // fall into abyss
  } else {
    grid[now[1]][now[0] - minX] = "o"
    newSand++
  }
}

So, I ran it on my puzzle input.

And everything was looking incredible!

I kept scrolling down, noticing the sand resting as expected.

Until I reached the bottom wall.

And I saw this discrepancy:

There are 10 particles of sand mistakenly resting upon the abyss!

How did that happen?

Thankfully, after some inspection of my code and trying a few modifications to my conditions, I spotted and fixed the error:

// Old
while (
  String(was) !== String(now) && 
  now[0] - 1 - minX >= 0 &&
  now[0] + 1 - minX < maxX - minX &&
  now[1] + 1 < maxY
) {}

// New
while (
  String(was) !== String(now) && 
  now[0] - 1 - minX >= 0 &&
  now[0] + 1 - minX < maxX - minX &&
  now[1] + 1 <= maxY
) {}

Can you spot the difference?

Spoiler: it's the = in the last operand of the logical AND check.

With that in place, I re-ran my algorithm and rendered my seemingly correct reservoir filled with rested sand:

I submitted my answer.

It was the correct answer!

Building a simulator

This was relatively simple.

My algorithm is already set up to be repurposed for a step-based design.

Thankfully, the result was worth building.

Isn't that cool to watch?

I encourage you to try it using your puzzle input.

Part 2

Accounting for a floor

Accounting for a floor

It's two rows lower than the lowest wall
Thus, I can't just amend my input. I have to programmatically add it.
And I can't make it endlessly wide. I think I'll start with making it 1000 tiles wide and see how far that gets me.

Changes to my grid:

// Part 1
let grid = new Array(maxY + 1)
  .fill(null)
  .map(el => new Array(maxX + 1)
      .fill(null)
      .map(el => '.')
  )

// Part 2
let grid = new Array(maxY + 3)
  .fill(null)
  .map(el => new Array(1000)
      .fill(null)
      .map(el => '.')
  )

I then removed every instance of - minX, since my grid now has columns spanning all 500 tiles left of the starting spot.

Finally, drawing the floor required this new line:

grid[grid.length - 1] = grid[grid.length - 1].map(el => '#')

The sole condition in my inner while loop is now just:

String(was) !== String(now)

Once that while loop is terminated, I perform this check to determine whether to draw a grain of sand:

String(now) !== '500,0'

Lastly, I increment the sand count by 1 before returning it to account for the last grain of sand covering the starting point.

All of that took a bit of trial and error to work out.

Thankfully, I eventually returned the correct answer for the example input.

Then, I ran my algorithm on my puzzle input...hoping that a grid 1000 tiles wide would catch all of the newly rested grains of sand.

So, how'd I do?

...

I got the correct answer!

I'm truly blown away!

Updating the simulator

As small as it may be on screen, I want the simulator to play out Part 2 for any puzzle input.

Updating it wasn't too hard.

A lot of copy-paste.

I made the font size 2px to squeeze the 1000 x 115 grid into a single viewport.

It's small, but still a sight to behold.

My simulation plays out in 10 minutes.

After a lot of converting, speeding up and removing frames, I got it down to sub-500 frames in a GIF that feels like watching sand fall!

I did it!!

I solved both parts!
No, really! I solved them both!
Using algorithms!
After drawing enough of the sand to feel confident in attempting to write an algorithm!
And I [built a simulator]((https://aocregolithreservoir.rmion.repl.co/)!
For both parts!

This will rank in my book as one of the top 5 puzzles, and one of my top 5 achievements.

I'm really glad I went slow, used my design tool to visualize the sand and the walls, and then had the guts to attempt an algorithm.

What an incredible puzzle experience!