Sand Slabs

Advent of Code 2023 Day 22

Part 1

Physics? 3D? Jenga? Uh-oh.

I'm tempted to just move on to Day 23.

I can't fathom solving this.

But...I feel compelled to get as far as I can, just for practice.

Here's what I think I can do:

• Parse the input into each shapes collection of occupied spaces in the stack
• Sort by height, with lower-stacked shapes coming first
• Attempt making a mental map of the lowest shapes to understand whether there's a trick for identifying shapes that can disintegrate solely based on whether two or more shapes are below one of their cubes

Let's see how far I get before I call it a day!

Parsing the input into lines of cubes

Each line of input follows this regex-like blueprint:

\d+,\d+,\d+~\d+,\d+,\d+

Since the ~ represents a range, I think I'll split the string first, then use both regexes to get two 3-element arrays.

let [start, end] = line.split('~')
start = [...start.matchAll(/\d+/g)].map(el => +el[0])
end = [...end.matchAll(/\d+/g)].map(el => +el[0])

By now I should have:

[0,0,2] // start
[0,2,2] // end

And that I do!

input.split('\n').map(line => {
  let [start, end] = line.split('~')
  start = [...start.matchAll(/\d+/g)].map(el => +el[0])
  end = [...end.matchAll(/\d+/g)].map(el => +el[0])
})

I thought I'd have to account for either part being start or end.

But after reviewing several lines of my puzzle input, it seems the author has generously made sure that the direction is consistent for each line: numbers always the same or increasing.

So, I can just go straight into my super-nested loop to write out each cube's coordinate.

First, I need constraints for each loop. For that, I need to know mins and maxes of each X,Y,Z coordinate in the pairs.

let [minX, maxX, minY, maxY, minZ, maxZ] = [
    Math.min(start[0], end[0]),
    Math.max(start[0], end[0]),
    Math.min(start[1], end[1]),
    Math.max(start[1], end[1]),
    Math.min(start[2], end[2]),
    Math.max(start[2], end[2]),
  ]

Maybe not pretty, but gets the job done.

Now I'm ready for my nested loops.

let cubes = []
for (let x = minX; x <= maxX; x++) {
  for (let y = minY; y <= maxY; y++) {
    for (let z = minZ; z <= maxZ; z++) {
      cubes.push([x,y,z])
    }
  }
}

And with that, for a line like A I get B:

A
0,0,2~2,0,2

B
[ [ 0, 0, 2 ], [ 1, 0, 2 ], [ 2, 0, 2 ] ]

Hazaah!

Using the example input, here is my list of slabs with each cube accounted for:

[
  [ [ 1, 0, 1 ], [ 1, 1, 1 ], [ 1, 2, 1 ] ],
  [ [ 0, 0, 2 ], [ 1, 0, 2 ], [ 2, 0, 2 ] ],
  [ [ 0, 2, 3 ], [ 1, 2, 3 ], [ 2, 2, 3 ] ],
  [ [ 0, 0, 4 ], [ 0, 1, 4 ], [ 0, 2, 4 ] ],
  [ [ 2, 0, 5 ], [ 2, 1, 5 ], [ 2, 2, 5 ] ],
  [ [ 0, 1, 6 ], [ 1, 1, 6 ], [ 2, 1, 6 ] ],
  [ [ 1, 1, 8 ], [ 1, 1, 9 ] ]
]

This list is coincidentally pre-sorted with lower-stacked cubes ordered earlier in the list.

My input isn't so lucky.

My next exercise is to sort either input by z - then y and x? - in ascending order.

Sorting the list to reflect stacking order

This was a single statement:

slabs.sort(
  (a,b) => a[0][2] - b[0][2] || 
           a[0][0] - b[0][0] || 
           a[0][1] - b[0][1]
)

• First compare Z-axis values, lowest-first
• Then compare X-axis values, lowest-first
• Lastly compare Y-axis values, lowest-first

The example input remains unchanged - that's good.

And my puzzle input shows all 1 z-axis cubes coming before 2 and 3 and so on, with lowest x-axis values coming first in any given z-axis cluster.

So...now what?

Starting from the bottom and working my way up

As described, no slabs occupy level 0.

Slabs on z-axis level 1 can not fall any further. They're not moving.

The first level with slabs that have room to fall is level 2.

So I'll start there.

Side quest: identify all vertical slabs

These are slabs whose z-axis value changes.

Should be straightforward to identify.

I'll filter my list of slabs to only include items where the 3rd item in the first two sub-arrays are different.

slabs.filter(
  slab => {
    return slab.length > 1 && slab[0][2]!== slab[1][2]
  }
)

That > 1 part is necessary to weed out single-cube slabs.

Success:

• It found G from the example input
• And it found 147 slabs in my input, all of which have changing z-axis values

And single-cube slabs, for good measure

slabs.filter(
  slab => {
    return slab.length == 1
  }
)

Success again:

• None in the example input
• 28 single-sub-array slabs in my input

Why find verticals and single-cube slabs?

They rely on a single brick to hold them up.

So, my algorithm could start at their lowest cube and move downward in search of the nearest slab.

Unlike horizontal slabs, which may rely on one or many slabs to hold them up, and require checking downward from each cube for another slab.

Crazy idea: catalogue each cube

The example input lists six slabs comprised of 20 cubes.

Right now I have an array of arrays that groups cubes by slab.

But no slab really has an id, just an index in an ordered list.

I could give slabs an id, but that wouldn't help when comparing cubes within a slab. That would still require tons of look-up logic to find slab ids.

What if, instead, I create a dictionary where:

• The keys are coordinates
• The values are ids of the associated slab

For the example input, it may look like this:

{
  '1,0,1': 'A',
  '1,1,1': 'A',
  ...
}

Having that, I could easily look up each cube's associated slab, and determine:

• Whether a coordinate is occupied by a slab
• Whether one or more slabs will eventually hold up a falling slab
• Exactly which slabs will hold another slab up

I'm really liking this approach.

My ids will be numbers starting at 0. They should go up to 7 for the example input and just over 1400 for my puzzle input.

And I imagine there will be tens of thousands of cubes - a.k.a. keys in my dictionary.

This algorithm can be done with a reduce:

For each slab
  For each cube
    Add a key of the stringified coordinates
      The value should be the index of the slab

Let's write this and see what comes out.

Wow, that was easy:

const cubes = slabs.reduce(
  (obj, slab, index) => {
    slab.forEach(cube => {
      obj[cube.join(',')] = index
    })
    return obj
  }
, {})

And I see exactly what I wanted:

{
  '1,0,1': 0,
  '1,1,1': 0,
  '1,2,1': 0,
  '0,0,2': 1,
  '1,0,2': 1,
  '2,0,2': 1,
  '0,2,3': 2,
  '1,2,3': 2,
  '2,2,3': 2,
  '0,0,4': 3,
  '0,1,4': 3,
  '0,2,4': 3,
  '2,0,5': 4,
  '2,1,5': 4,
  '2,2,5': 4,
  '0,1,6': 5,
  '1,1,6': 5,
  '2,1,6': 5,
  '1,1,8': 6,
  '1,1,9': 6
}

Revisiting verticals and singles: this time get ids

My algorithms earlier found the correct slab arrays.

But I need ids now.

Thankfully, getting the slab ids is a simple map and key-value look-up:

let verticals = slabs.filter(
  slab => {
    return slab.length > 1 && slab[0][2]!== slab[1][2]
  }
).map(slab => cubes[slab[0].join(',')])

let singles = slabs.filter(
  slab => {
    return slab.length == 1
  }
).map(slab => cubes[slab[0].join(',')])

Merging both groups, because why not?

Vertical and single-cube slabs share a similar truth:

• I only care about the lowest z-axis cube

Therefore, I can combine both id groups knowing that I can look up the full list of cubes and then only use the first sub-array for the downward search.

let tallCubes = verticals.concat(singles).sort((a,b) => a - b)

I think I'm ready: downward search starting at z-axis level 2

Finding all slabs where the lowest cube in the slab is on z-axis level 2:

let z2 = slabs.filter(slab => slab[0][2] == 2)

Success:

• One slab in example
• Six slabs in my puzzle input

Working through what I want to do next:

For each slab
  If it's a vertical or single cube
    Only compare the first cube in the list of cubes
  Else
    For each cube in the list
      Look one z-index lower for a cube
        If a cube is found
          This slab doesn't move
        If multiple cubes from different slabs are found
          Each cube is disintegrate-able
        Else, if no cubes are found
          This slab can move down one z-axis
        Else, if cubes from the same slab are found
          That slab is not disintegrate-able

One step at a time, as usual.

z2.forEach(slab => {
  let id = cubes[slab[0].join(',')]
  if (tallCubes.includes(id)) {
    slab = [slab[0]]
  }
  slab.map(cube => {
    // check cubes one z-axis level lower
  })
})

• For each slab
• Get the id
• Check if its a vertical or single-cube slab
• If so, reduce the list of cubes to the first one

let oneLevelDown = slab.map(cube => {
  cube[2] = cube[2] - 1
  if ((cube.join(',') in cubes)) {
    return cubes[cube.join(',')]
  } else {
    return null
  }
})

• For each cube in the current slab
• Decrement each z-axis value by 1
• Look for a key in the dictionary of cubes matching the mutated coordinate
• Return either the id associated with that cube
• Or null to indicate empty space

So far so good:

• I get [null, 0, null] for the example input, validating that one of the B slab cubes rests atop one of the A slab cubes
• I get no errors and several all-null arrays for my puzzle input, with two slabs sitting atop level-1 slabs

What now?

Sheer terror.

Am I really about to dive down this deep rabbit hole?

I think I'm setting myself up to programmatically move every slab downward, thereby seeing this fall to completion...only to then re-check every slab to see if it rests atop two or more slabs!

I'm gonna have to track so many things.

And check and re-check nearly 1400 slabs spread across 300 z-axis levels.

My head is starting to hurt.

I still doubt that I can come out of all this with a correct answer.

But I gotta try...right?!

...

...

Well, I dove head-first.

And I swam around for a few hours.

Good news is, I accomplished what I sought out to do!

But then - right when I thought I was 'one away' - I discovered a huge detail I had overlooked.

I still haven't written that part yet.

But I wanted to come back here and write a bit about my approach thus far.

Watching the bricks fall, piece by piece

My goal is to assess which bricks can disintegrate:

let disintegrators = new Set()

For logging purposes, I want to reach a state where each brick has landed:

let landed = new Set()

Any bricks on z-axis 1 can't fall any further. So, they can be pre-added to landed:

slabs
  .filter(
    slab => slab[0][2] == 1
  ).map(
    slab => cubes[slab[0].join(',')]
  ).forEach(
    id => landed.add(id)
  )

For all other bricks, which occupy levels 2 thru...whichever value is at index 2 in the first sub-array in the last position in the slab list:

for (let i = 2; i <= slabs[slabs.length - 1][0][2]; i++) { }

Get all slabs in the current z-axis:

let layer = slabs.filter(slab => slab[0][2] == i)

For each slab in the layer:

• Get its id
• Extract its lowest cube(s)
• Make a temporary copy of those cubes
• Attempt to move the temporary copy one z-axis lower until it would intersect with the cube of another slab
• If it would have moved, update all of its cubes' coordinates in the dictionary of cube coordinates
• If it is being held up by cubes from two or more slabs, add each slab to the list of possible disintegrators

Here's all my JavaScript to accomplish the above tasks, and then some:

for (let i = 2; i <= slabs[slabs.length - 1][0][2]; i++) {
  let layer = slabs.filter(slab => slab[0][2] == i)
  layer.forEach(slab => {
    let id = cubes[slab[0].join(',')]
    let tempSlab = slab.map(cube => cube.slice())
    let oneLevelDown
    let isTall = tallCubes.includes(id)
    if (isTall) {
      tempSlab = [tempSlab[0]]
    }
    do {
      tempSlab = tempSlab.map(cube => {
        cube[2] = cube[2] - 1
        return cube
      })
      oneLevelDown = tempSlab.map(cube => {
        if ((cube.join(',') in cubes)) {
          return cubes[cube.join(',')]
        } else {
          return null
        }
      })
    } while (oneLevelDown.every(el => el == null) && tempSlab[0][2] > 0)

    if (i - tempSlab[0][2] - 1 > 0) {
      slab.forEach(cube => {
        delete cubes[cube.join(',')]
      })
      if (isTall) {
        let newLevel = tempSlab[0][2] + 1
        slab = slab.map((cube, index) => {
          cube[2] = newLevel + index
          return cube
        })
        slab.forEach(cube => {
          cubes[cube.join(',')] = id
        })
      } else {
        slab = tempSlab.map(cube => {
          cube[2] = cube[2] + 1
          return cube
        })
        slab.forEach(cube => {
          cubes[cube.join(',')] = id
        })
      }
    }
    landed.add(id)

    // What slabs is it on?
    let ids = new Set(oneLevelDown.filter(el => el !== null))
    if (ids.size > 1) {
      Array.from(ids).forEach(id => disintegrators.add(id))
    }
  })
}

The big revelation

For the example input, my algorithm added four bricks to the list of possible disintegrators.

All four were correct.

But the fifth was missing.

And that's because it was G, the top-most brick, which isn't holding up any other bricks.

First, I thought, "That's ok, I'll just manually add all bricks at the highest z-axis level for my input."

But I would have been way off, probably.

Why?

Because I would have failed to account for all bricks that aren't holding up any other bricks.

Those could exist at any level!

How would I check for that?

Good news is: very similar to how I did my last check!

Checking for bricks not holding anything up

These are any brick where the spaces directly above their top-most cubes are empty.

Thankfully, checking for this should require only some small changes to a copy of my current for loop.

I'm about to find out whether I am right...or I am about to eat those words.

...

Well, after some seriously stupid confusion on account of me mistakenly mutating a slab in-place, my new for loop correctly identifies the remaining top-side-free bricks as distintigrators.

Here's my second for loop:

for (let i = 1; i <= slabs[slabs.length - 1][0][2]; i++) {
  let layer = slabs.filter(slab => slab[0][2] == i)
  layer.forEach(slab => {
    let id = cubes[slab[0].join(',')]
    let isTall = tallCubes.includes(id)
    let temp = slab.map(cube => cube.slice())
    if (isTall) {
      temp = [temp[temp.length - 1]]
    }
    if (temp.map(cube => {
      cube[2] = cube[2] + 1
      if ((cube.join(',') in cubes)) {
        return cubes[cube.join(',')]
      } else {
        return null
      }
    }).every(el => el == null)) {
      disintegrators.add(id)
    }
  })
}

It successfully identifies all five bricks in the example input that could be disintigrated.

Now the gigantic question:

• Can it correctly identify all bricks in my puzzle input that could be disintigrated?

Honestly, I'm afraid to run it:

• Maybe there will be an error
• Maybe I'll get an answer, but it won't be correct

Nails bitten.
Fingers crossed.

...

Wrong answer. Too high.

Bummer!

What might I be missing?

A hunch about an oversight

Imagine bricks A, B and C and D arranged as such:

From above
D.B
CCC

From below
D.A
DCA

So:

• C is held up by D and A
• B is held up by A

The correct number of possible disintegrators is:

• 2 - B and C

In my algorithm, the number would be:

• 4 - all bricks

My algorithm is incorrectly assuming that whenever a brick is held up by more than one brick...any of those bolstering bricks could be disintegrated.

But that's not always true.

Ok.

How will I account for these scenarios?

Another big dictionary mapping each block to the blocks it holds up?

Well, if I made that for the example input, it would be:

{
  'A': ['B', 'C'],
  'B': ['D', 'E'],
  'C': ['D', 'E'],
  'D': ['F'],
  'E': ['F'],
  'F': ['G'],
  'G': []
}

And my algorithm for identifying disintegrators is:

For each key
  If list of items is empty
    It can disintegrate
  Else, For each item
    Does any other key have this item?
      If not, this is the only key holding that item up
        So it cannot disintegrate
      If so
        It can disintegrate

I think I've done it!

Now, to make all this work with code.

Coding my new strategy

I need a new dictionary:

let bottoms = {}

It should initialize to have a key for each slab's id, where each value is an empty list:

for (let i = 0; i < slabs.length; i++) {
  bottoms[i] = []
}

Then, instead of immediately adding to my list of potential disintegrators, I add the current slab's id to the lists of each slab it's on top of:

let ids = new Set(oneLevelDown.filter(el => el !== null))
if (ids.size > 0) {
  Array.from(ids).forEach(ID => bottoms[ID].push(id))
}

Then, the big and fun part - re-creating each step from the above pseudocode:

for (let keyA in bottoms) {
  if (bottoms[keyA].length == 0) {
    disintegrators.add(+keyA)
  } else {
    let results = bottoms[keyA].map(upper => {
      let flag = false
      for (let keyB in bottoms) {
        if (keyA !== keyB && bottoms[keyB].includes(upper)) {
          flag = true
        }
      }
      return flag
    })
    if (results.every(el => el == true)) {
      disintegrators.add(+keyA)
    }
  }
}

The best part is:

• I no longer need my for loop that checks above each slab
• Because I identify those slabs in my clause for empty-listed keys in the for loop just above

Does it work???

It generates the correct answer for the example input.

It generates a lower number for my puzzle input.

That's a good sign, since my last submission was too high.

I submit my new answer.

It's correct!!!!!

Woohoo!!!!

I actually did it!!!!

I got a gold star from today's challenge!!!!

All this effort was worth it!!!!

Ok, Part 2. Whatchugot?

Part 2

Just within reach...maybe?

For each brick, determine how many other bricks would fall if that brick were disintegrated.

The super-ridiculously-extra-long-hard way:

For each brick
  Clone the list of bricks with this brick removed
  Run the brick-falling algorithm
  Track how many bricks fell...
...

No. No. No.

That wouldn't work because it's still going to track all of the bricks that fall regardless of the one brick not existing.

For each brick, determine how many other bricks would fall if that brick were disintegrated.

What if I work backwards - starting from bricks with nothing on them?

I know that each brick like that would result in 0 bricks falling.

Then, I could attempt to identify the brick(s) that those bricks are directly on top of.

If that brick is the only brick holding up the one on top of it, then it would result in 1 + (the sum of bricks on top of it: 0).

And I could work semi-recursively further down the stack.

All the while knowing the counts of items in each brick's list of bricks on top of it.

This sounds like it might work.

I'll start with the example list of bottoms from my Part 1 as practice.

Practice Round 1

This object is known as bottoms in my code, since slabs was already taken:

{
  'A': ['B', 'C'],
  'B': ['D', 'E'],
  'C': ['D', 'E'],
  'D': ['F'],
  'E': ['F'],
  'F': ['G'],
  'G': []
}

I need to track the keys I've visited and know how many bricks would fall if they were disintegrated.

let visited = {}

To kick things off, I'll start at the leaf nodes - the bricks with nothing above them:

For each key in bottoms
  Find keys with values that are empty lists
    Add that key to a set of visited keys
      Where the value is 0

After running that code, I should have this:

let visited = { 'G': 0 }

I now want to work my way down the stack.

I'll look for any keys with G in their list.

Better yet, I should look for any keys with any of the keys in visited in their list, because in my puzzle input there are sure to be more than one leaf node.

For each key in bottoms
  Find keys that meet this criteria:
    - Values list includes any key from visited
    - key is not in visited (may not be necessary)

After running that, I should find 'F' in the example input.

For any key that was found
  For each key in its values list
    If that key is in visited
      Check whether the current key is the only brick keeping it from falling:
        For each key in bottoms
          Does any key aside from the current key have that key in its list?
      If it is, then removing this brick would cause the higher brick to fall, so return true
      Else, return false
  Replace any true values with the value from visited
  Replace any false values with 0
  Store this key in visited with value being the sum of all its replaced list values

I'm not sure if those last few lines will work.

But if they do, here's how the rest would play out, I think.

{
  'A': ['B', 'C'],
  'B': ['D', 'E'],
  'C': ['D', 'E'],
  'D': ['F'],
  'E': ['F'],
  'F': ['G'],
  'G': []
}

visited
{ 'G': 0 }

found
'F': ['G']

no other bricks have 'G'
'F': [true]

'F': [0]

visited
{ 'G': 0,
  'F': 1 }

Oversight no my part:

• I need to add to the sum the length of the list

visited
{ 'G': 0,
  'F': 1 }

found
'D': ['F']
'E': ['F']

for 'D'
one other brick has 'F'
'D': [false]

visited
{ 'G': 0,
  'F': 1,
  'D': 0 }

for 'E'
one other brick has 'F'
'E': [false]

visited
{ 'G': 0,
  'F': 1,
  'D': 0 
  'E': 0 }

Oversight:

• If an item becomes false, that item shouldn't count toward the key's sum
• So for 'F', since it's only item was true, that item added 1 to its sum
• But for 'D' and 'E', since their items were false, neither item added to its sum because disintegrating them wouldn't cause that brick to fall

visited
{ 'G': 0,
  'F': 1,
  'D': 0 
  'E': 0 }

found
'B': ['D', 'E']
'C': ['D', 'E']

for 'B'
for 'D', one other brick supports 'D'
for 'E', one other brick supports 'E'
'B': [false, false]

visited
{ 'G': 0,
  'F': 1,
  'D': 0 
  'E': 0
  'B': 0 }

'C' is the same

visited
{ 'G': 0,
  'F': 1,
  'D': 0,
  'E': 0,
  'B': 0,
  'C': 0 }

found
'A': ['B', 'C']

for 'A'
'B' is only supported by 'A'
'C' is only supported by 'A'
'A': [true, true]
'A': [0, 0]

visited
{ 'G': 0,
  'F': 1,
  'D': 0,
  'E': 0,
  'B': 0,
  'C': 0,
  'A': 2 }

Uh oh. There's my big problem:

• I'm only accounting for a brick's parent in it's score with this algorithm
• And missing the whole tree

What about the opposite approach?

Practice Round 2

{
  'A': ['B', 'C'],
  'B': ['D', 'E'],
  'C': ['D', 'E'],
  'D': ['F'],
  'E': ['F'],
  'F': ['G'],
  'G': []
}

Start with 'A'
'A': ['B', 'C']

No other brick has 'B'

If A falls, B falls

'A': [true, ...]

Continue to B

'B': ['D', 'E']

I don't like where this is headed.

Stopping this Round early.

I think I'm gonna have to do it.

Simulated disintegration of each brick

I already have an algorithm that simulates every brick falling.

I need to update the algorithm to count all bricks that fall instead of bricks that could disintegrate.

For each brick, I'll have to:

• Clone both the slabs list and the cubes dictionary
• Remove entries from each corresponding to the current brick
• Run the algorithm to simulate all bricks falling
• Determine and save the bigger value: the bricks that fell this time or the bricks that fell in the time with the current highest score

In the hand, my hope is that I'll have the correct answer.

My questions are:

• If I process every brick every time, would my algorithm finish in under a minute or two?
• Assuming not - since running it once takes a few seconds - then how can I optimize it to only process bricks that are on the same level or higher than the current brick's level?

It's time to find all this out.

Here I go again to solve Part 2 of what seems like my longest article in this series.

Curse you, splice!

I wrote my new algorithm in about a half hour.

The next two hours were spent debugging it.

Why wasn't I seeing the results I expected?

Surely, I had:

• Created clones of my cubes object and slabs array
• Removed the correct item and its cube coordinates
• Processed each higher brick's downward fall
• Tracked the tally of bricks that had fallen
• Made sure to update any references to original data structures that I had copied to my new clones

But I wasn't getting the right answer for the example input.

Finally, a specific log statement revealed a glaring error:

• I was overwriting the wrong slab item on the highest brick, G

How could this be?

What was wrong in my code?

Well, stupidly, I overlooked my use of splice.

I was mistakenly removing an item from my cloned array.

That was shifting my indices incorrectly.

And things cascaded from there.

As soon as I removed my use of splice, things practically auto-corrected themselves in an instant!

Shortly thereafter, running my program generated the 7 I was looking for.

It was time again for the moment of truth:

• Would I see any errors when running on my puzzle input?
• Would it even finish...in under two minutes?

Gulp.

Run.

45 seconds later.

A single number appears.

Copy-paste-submit.

It's the correct answer!!!

I earned two gold stars today!!!

I can't believe I solved both parts today!!!

What an incredible feeling.

I now have 34 gold stars for the year!

This ties my lowest score shared across a few other years!

I'm so glad that I reached that bar this year! It's felt like the toughest one yet.

Whew.

Wouldn't it be nice to earn another star or two?

Either way though...

I did it!!!