DEV Community

Cover image for Boiling Boulders
Robert Mion
Robert Mion

Posted on

Boiling Boulders

#watercooler

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 
[ ..., ..., ..., ..., ... ]
Enter fullscreen mode Exit fullscreen mode

2D grid - rows and columns:

  • Arrays inside an array
  • Each item is a row
  • Each item in there is a column 
[ [ ..., ..., ... ], [ ..., ..., ... ], [ ..., ..., ... ] ]
Enter fullscreen mode Exit fullscreen mode

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 
[ [ [ ..., ..., ... ], [ ..., ..., ... ], [ ..., ..., ... ] ] ]
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

Compare the first and second cubes:

X Y Z 1,1,1 2,1,1 MD 1 0 0 = 1 Adjacent! 6 - 1 = 5
Enter fullscreen mode Exit fullscreen mode

Compare the second and first cubes:

X Y Z 2,1,1 1,1,1 MD 1 0 0 = 1 Adjacent! 6 - 1 = 5
Enter fullscreen mode Exit fullscreen mode

Accumulate the totals:

5 + 5 = 10
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

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.

Top comments (0)