DEV Community

Cover image for Boiling Boulders
Robert Mion
Robert Mion

Posted on

1

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
[ ..., ..., ..., ..., ... ]
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.

AWS Security LIVE!

Join us for AWS Security LIVE!

Discover the future of cloud security. Tune in live for trends, tips, and solutions from AWS and AWS Partners.

Learn More

Top comments (0)

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay