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.

Sentry image

Hands-on debugging session: instrument, monitor, and fix

Join Lazar for a hands-on session where you’ll build it, break it, debug it, and fix it. You’ll set up Sentry, track errors, use Session Replay and Tracing, and leverage some good ol’ AI to find and fix issues fast.

RSVP here →

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

👋 Kindness is contagious

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

Okay