Advent of Code 2022 Day 18
Part 1
- Third in a row. Grrr!
- Trying again: using arrays to represent a 3D grid
- Scrap that: use Manhattan Distance instead?
- My algorithm in JavaScript
Third in a row. Grrr!
- First was Day 16: a search algorithm
- 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
- 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.
Top comments (0)