Unstable Diffusion

Advent of Code 2022 Day 23

Try the simulator for Part 2 using your puzzle input!

Part 1

1. A turducken of a puzzle
2. Parsing and padding the grid
3. Find each elf
4. First half, part one
5. First half, part two
6. Second half
7. Update the grid
8. Multiple rounds
9. Debugging using the larger example input
10. The marquee tool
11. Running on my padded puzzle input

A turducken of a puzzle

Oh my! How many smaller challenges are stuffed in this puzzle?!

• Input is a rectangular grid
• Each iteration consists of multiple steps that queue up to a final action
• Check all eight adjacent cells
• Rotate which direction to check first
• Identify the smallest possible rectangular area
• Count all of a certain type of tile
• For now, process only a few iterations
• Hunch: process as many as needed until a desired end-state (each Elf has no Elves adjacent)

This is going to be quite the algorithmic gauntlet.

Thankfully, I feel confident that I can work my way toward earning the gold star.

And hopefully my hunch is correct and I can earn a second gold star. One star at a time, though.

Parsing and padding the grid

Creating a 2D array from the input has become a menial task for me by now:

let grid = input.split('\n').map(row => row.split(''))

I've had to add rows and columns around the edges of a grid in several past puzzles.

I recall doing it in a single command.

But for now, this method will suffice:

Function expects two parameters:
  1. The array to pad
  2. The number of times to add a single layer of padding all around

  Create a copy of the input array
  Do as many times as told
    Insert a single character at the beginning and end of each nested array
    Insert a row at the beginning and end of the outer array that is the same length as each nested array
  Return the cloned, padded array

My algorithm in JavaScript:

function padBy(RA, times) {
  let paddedGrid = RA.slice().map(row => row.slice())
  for (let i = 0; i < times; i++) {
    paddedGrid = paddedGrid.map(row => ['.', ...row, '.'])
    paddedGrid.unshift(
      new Array(grid[0].length).fill(null).map(el => '.')
    )
    paddedGrid.push(
      new Array(grid[0].length).fill(null).map(el => '.')
    )
  }
  return paddedGrid
}

let grid = input.split('\n').map(row => row.split(''))
grid = padBy(grid, 10)

Calling the function with 5 on the larger example input:

....#..
..###.#
#...#.#
.#...##
#.###..
##.#.##
.#..#..

Results in this padded array:

.................
.................
.................
.................
.................
.........#.......
.......###.#.....
.....#...#.#.....
......#...##.....
.....#.###.......
.....##.#.##.....
......#..#.......
.................
.................
.................
.................
.................

Fantastic!

Find each elf

It seems foolish to check every cell each round.

Especially with the newly padded array, the majority of cells won't have an elf.

Thankfully, I only have to perform this check once.

Then, in each iteration, I only need to iterate through each elf and not every cell in the padded grid.

Create elves as an empty list
Check every cell
  If the cell contains a #
    Add the coordinates of the elf to elves

My algorithm in JavaScript:

let elves = []

for (let row = 0; row < grid.length; row++) {
  for (let col = 0; col < grid[0].length; col++) {
    if (grid[row][col] == '#') {
      elves.push([row, col])
    }
  }
}

Processing the 5-padded grid of the small example input:

...............
...............
...............
...............
...............
...............
.......##......
.......#.......
...............
.......##......
...............
...............
...............
...............
...............
...............

Results in this list of elves:

[ [ 6, 7 ], [ 6, 8 ], [ 7, 7 ], [ 9, 7 ], [ 9, 8 ] ]

Fantastic, again!

I hope this gives my upcoming algorithm a bit of a speed boost.

Even though I could have checked every cell with an added condition that does nothing if the cell contains a ..

Still, this feels smart.

First half, part one

Mission:

Should the Elf move or not? Check all eight adjacent cells. If they are all empty, don't move. Otherwise, more instructions to follow.

The relative coordinates of all eight adjacent cells:

let adjacents = [
  [-1,-1],
  [-1, 0],
  [-1, 1],
  [ 0,-1],
  [ 0, 1],
  [ 1,-1],
  [ 1, 0],
  [ 1, 1]
]

Checking each elf's eight adjacent cells and only proceeding if at least one is occupied by another elf:

elves.forEach(([row, col]) => {
  if (
    !adjacents.map(([vrtl, hztl]) => {
      return grid[row + vrtl][col + hztl] == '#'
    }).every(el => el == false)
  ) {
    // Proceed with proposing a move!
  }
})

First half, part two

Mission:

Check the three adjacent cells in each ordinal direction until a direction is completely vacant. Mark the coordinates of the cell in the middle of the first direction with no elves as the one proposed.

I intend to use a nested 4-element array to track the order of proposed directions:

let proposals = [
  [
    [-1,-1],
    [-1, 0],
    [-1, 1]
  ],
  [
    [ 1,-1],
    [ 1, 0],
    [ 1, 1]
  ],
  [
    [-1,-1],
    [ 0,-1],
    [ 1,-1]
  ],
  [
    [-1, 1],
    [ 0, 1],
    [ 1, 1]
  ],
]

At the end of each round, a simple combination of shift() and push() should move the first item to the end:

proposals.push(proposals.shift())

Checking only as many sides as needed, determine whether a side is clear of any elves:

let i = 0
while (
  !proposals[i].map(([y, x]) => {
    return grid[row + y][col + x] == '#'
  }).every(el => el == false)
) {
  i++
}

Next, I need two variables to store the proposed positions and map each position to the elf who proposed it:

let proposed = {}
let moveTo = []

With i corresponding to the correct face, I need the coordinates of the middle cell (N/E/S/W). Then, I both create a key for that coordinate and increment its occurrence by 1. Lastly, I build a list of the proposed coordinates in the same order as the elves.

let target = [
  row + proposals[i][1][0], 
  col + proposals[i][1][1]
].join('|')
proposed[target] = proposed[target] || 0
proposed[target]++
moveTo[index] = target

I now have an algorithm that:

• Checks all eight adjacent cells for elves
• Identifies the appropriate cell to propose moving
• Tracks how many elves proposed any given cell
• Tracks which elf proposed which cell

Second half

Mission:

Update each elf's position based on whether they are allowed to move: they were the only elf to propose their new position

For each proposed position, if it's number of occurrences is 1, find the location of that position in the ordered list and update the coordinates of the elf in the same order in its list to match the proposed position:

for (let coord in proposed) {
  if (proposed[coord] == 1) {
    let index = moveTo.indexOf(coord)
    elves[index] = coord.split('|').map(Number)
  }
}

Update the grid

My elves have their new coordinates.

But the grid remains unchanged.

I need the grid to reflect the elves' new coordinates.

I'll replace all #s with .s. Then I'll put #s in the appropriate positions.

grid = grid.map(row => row.map(col => '.'))
elves.forEach(([row, col]) => {
  grid[row][col] = '#'
})

Lastly comes the first-to-last command shown earlier to correctly update the order of the sides to check when searching for the correct position to propose.

How am I looking?

Using the small example input with padding:

...............
...............
...............
...............
...............
...............
.......##......
.......#.......
...............
.......##......
...............
...............
...............
...............
...............
...............

After one round, I see the expected arrangement:

...............
...............
...............
...............
...............
.......##......
...............
.......#.......
........#......
.......#.......
...............
...............
...............
...............
...............
...............

Nice!

Multiple rounds

My algorithm works for one round on the small example input.

Does it work for three?

Yes!

How about 10 rounds of the larger example input?

Nope! Doesn't even do a single round!

What's the deal?

Debugging using the larger example input

The larger example input is:

....#..
..###.#
#...#.#
.#...##
#.###..
##.#.##
.#..#..

My algorithm appears to process two elves, then get stuck on the third.

That means it gets stuck on the elf marked with an *:

..#
#*#
..#

• It has more than 0 elves around it, so it passes that test
• And it has an elf on each side
• Oh no! I never check for that!

Wow. I overlooked accounting for no valid directions.

To account for it, I add a clause to check for an out of bounds index in my proposals array:

let i = 0
while (
  i < 4 && !proposals[i].map(([y, x]) => {
    return grid[row + y][col + x] == '#'
  }).every(el => el == false)
) {
  i++
}
if (i < 4) {
  let target = [row + proposals[i][1][0], col + proposals[i][1][1]].join('|')
  proposed[target] = proposed[target] || 0
  proposed[target]++
  moveTo[index] = target
}

It's not my finest solution, but it successfully renders 10 correct rounds of the larger example input!

The marquee tool

Mission:

Count the number of empty ground tiles contained by the smallest rectangle that contains every Elf

How do I identify the boundaries of that rectangle, especially with my padded grid?

After Round 10, my padded larger example input looks like this:

.................
.................
.................
.........#.......
.............#...
....#.#..#.......
........#........
.....#.....#..#..
...#......##.....
.......##........
....#........#...
......#.#..#.....
.................
......#..#..#....
.................
.................
.................

One strategy I can of is:

• Left edge: find the smallest index among all positive indices marking the first instance of a # in each row
• Right edge: find the largest index among all positive indices marking the last instance of a # in each row
• Top edge: find the top-most row whose values are not all .
• Bottom edge: find the bottom-most row whose values are not all .

Here are each of those in algorithm form.

Left edge:

Math.min(
  ...grid.map(row => row.indexOf('#'))
         .filter(el => el !== -1)
)

Right edge:

Math.max(
  ...grid.map(row => row.lastIndexOf('#'))
         .filter(el => el !== -1)
)

Top edge:

grid.findIndex(row => !row.every(el => el == '.'))

Bottom edge:

grid.length 
- 1 
- grid.reverse()
    .findIndex(row => !row.every(el => el == '.'))

For the example above, I get the correct numbers:

  3
 +-+
3| |14
 +-+
 13

To count the open tiles within that rectangle:

Set count to 0
For each row inclusive of the top and bottom boundaries
  For each column inclusive of the left and right boundaries
    If the cell contains a .
      Increment count by 1

My actual algorithm generates the correct answer for the larger puzzle input!

Running on my padded puzzle input

The moment of truth!

I'll pad my input generously before running.

Fingers crossed it doesn't error due to insufficient padding or some other bug I didn't account for.

...

No errors, but wrong answer. Too low.

Bummer.

I decided to clean up my code by storing the edge calculations above in variables, then using those variables in my for loop.

Surprisingly, doing that generated a new, higher answer!

I submitted it.

Still the wrong answer, but now I am 'Too high'.

Huh.

I feel confident that my movement algorithm works correctly.

I'm just not sure my marquee algorithm does.

I really want to manually crop my padded grid and run my for loop on it.

...

After running my algorithm on the manually cropped grid, the answer I generated was one less that earlier!

I submitted it.

It's the correct answer!

Part 2

1. Just as I predicted!
2. Building a simulator

Just as I predicted!

Mission:

Process enough rounds to cause the elves to spread out until none of them move. How many rounds did it take?

Enter: simulator!

Building a simulator

Like nearly all prior, this was mostly a copy-paste task.

I added some text elements and code to track and display the current round and number of movers.

Watching it work on my puzzle input was pretty cool. It ended up resembling a thumb print!

I did it!!

• I solved both parts!
• By building an algorithm one piece at a time!
• And studying some logged output to diagnose rules that I had overlooked!
• Then manually cropping the grid to generate the correct answer for Part 1!
• And finally building a simulator to identify the first round where no elves moved!

What a challenging gauntlet of small algorithmic puzzles!

Great news:

• I'm one star away from tying my lowest star count!

Fingers remain crossed that I can earn one more star in the next two days!