Boiling Boulders

Advent of Code 2022 Day 18

Part 1

1. Third in a row. Grrr!
2. Trying again: using arrays to represent a 3D grid
3. Scrap that: use Manhattan Distance instead?
4. My algorithm in JavaScript

Third in a row. Grrr!

1. First was Day 16: a search algorithm
2. Second was Day 17: a puzzle that seemed approachable but wound up being a complex state management task that I wasn't able to crack
3. Third is today: another 3D puzzle demanding I identify touching sides

It's no surprise: usually Days 16+ are 0- and 1-star days for me.

I just get mad when I don't even have a working strategy to solve Part 1.

Trying again: using arrays to represent a 3D grid

I've tried before.
But I don't think I was successful.
So, might as well try again.

1D grid - columns:

• An array
• Each item is a column

[ ..., ..., ..., ..., ... ]

2D grid - rows and columns:

• Arrays inside an array
• Each item is a row
• Each item in there is a column

[
  [ ..., ..., ... ],
  [ ..., ..., ... ],
  [ ..., ..., ... ]
]

3D grid - planes with rows and columns:

• Arrays inside arrays inside an array
• Each item is a plane
• Each item inside is a row
• Each item in there is a column

[
  [
    [ ..., ..., ... ],
    [ ..., ..., ... ],
    [ ..., ..., ... ]
  ]
]

Scrap that: use Manhattan Distance instead?

What if I:

• Compared a single cube to all other cubes
• Tallied a count of any that are a Manhattan Distance of 1 away
• Accumulated an amount that is 6 minus that tally for each cube

The small example

The cubes:

1,1,1
2,1,1

Compare the first and second cubes:

X Y Z
1,1,1  
2,1,1

MD
1 0 0 = 1

Adjacent!
6 - 1 = 5

Compare the second and first cubes:

X Y Z
2,1,1
1,1,1  

MD
1 0 0 = 1

Adjacent!
6 - 1 = 5

Accumulate the totals:

5 + 5 = 10

The larger example

The cubes:

2,2,2
1,2,2
3,2,2
2,1,2
2,3,2
2,2,1
2,2,3
2,2,4
2,2,6
1,2,5
3,2,5
2,1,5
2,3,5

Using Manhattan Distance from all other cubes to find the count of each cube:

2,2,2  IIIIII
1,2,2  I
3,2,2  I
2,1,2  I
2,3,2  I
2,2,1  I
2,2,3  II
2,2,4  I
2,2,6  
1,2,5  
3,2,5  
2,1,5  
2,3,5  

Accumulating the totals:

2,2,2  IIIIII -> 6 - 6 = 0
1,2,2  I      -> 6 - 1 = 5
3,2,2  I      -> 6 - 1 = 5
2,1,2  I      -> 6 - 1 = 5
2,3,2  I      -> 6 - 1 = 5
2,2,1  I      -> 6 - 1 = 5
2,2,3  II     -> 6 - 2 = 4
2,2,4  I      -> 6 - 1 = 5
2,2,6         -> 6 - 0 = 6
1,2,5         -> 6 - 0 = 6
3,2,5         -> 6 - 0 = 6
2,1,5         -> 6 - 0 = 6
2,3,5         -> 6 - 0 = 6
---------------------------
                         64

That's the correct answer!

I may have a winning algorithm here!

My algorithm in JavaScript

return cubes
  .reduce((total, cube, index) => {
    let adjacent = 0
    for (let i = 0; i < cubes.length; i++) {
      if (index !== i) {
        adjacent += cube
          .map(
            (side, axis) => Math.abs(side - cubes[i][axis])
          )
          .reduce(
            (sum, count) => sum + count
          ) == 1 ? 1 : 0
      }
    }
    return total += 6 - adjacent
  }, 0)

Running it on:

• The small example generated the correct answer!
• The larger example generated the correct answer!
• My puzzle input (nearly 8 million comparisons!) generated the correct answer...after a few seconds!

Part 2

Does not compute

I'm confused about what it wants me to find.

The cube identified in the larger example makes me even more confused.

I can't attempt to solve a puzzle if I am confused by what it wants me to find.

I did it!

• I solved Part 1!
• Using Manhattan Distance and a boat-load of comparisons!
• I was able to avoid the nightmare of nested arrays to simulate 3D!

Exiting a 3D puzzle at Day 18 with one gold star earned?

That puts a smile on my face, especially after the lack of stars in the past couple of days.