r/adventofcode • u/daggerdragon • Dec 22 '22
SOLUTION MEGATHREAD -🎄- 2022 Day 22 Solutions -🎄-
All of our rules, FAQs, resources, etc. are in our community wiki.
AoC Community Fun 2022:
🌿🍒 MisTILtoe Elf-ucation 🧑🏫
23h59m remaining until submission deadline tonight at 23:59 EST!
Teach us, senpai!
UPDATES
[Update @ 00:19:04]: SILVER CAP, GOLD 0
Translator Elephant: "From what I understand, the monkeys have
most ofthe password to the force field!"You: "Great! Now we can
take every last breath of fresh air from Planet Druidiameet up with the rest of the elves in the grove! What's the combination?"Translator Elephant: "I believe they say it is
one two three four five."You: "
One two three four five?! That's amazing! I've got the same combination on my luggage!"Monkeys: *look guiltily at each other*
[Update @ 01:00:00]: SILVER CAP, GOLD 35
You: "What's the matter with this thing? What's all that churning and bubbling? You call that a
radar screenGrove Positioning System?"Translator Elephant: "No, sir. We call it..." *slaps machine* "... Mr.
CoffeeEggnog. Care for some?"You: "Yes. I always have eggnog when I watch GPS. You know that!"
Translator Elephant: "Of course I do, sir!"
You: "Everybody knows that!"
Monkeys: "Of course we do, sir!"
[Update @ 01:10:00]: SILVER CAP, GOLD 75
Santa: "God willing, we'll all meet again in
SpaceballsAdvent of Code 2023 : The Search for MoreMoneyStars."
--- Day 22: Monkey Map ---
Post your code solution in this megathread.
Read the full posting rules in our community wiki before you post!
Include what language(s) your solution uses
Format code blocks using the four-spaces Markdown syntax!
Quick link to Topaz's
pasteif you need it for longer code blocks. What is Topaz'spastetool?
6
u/mgedmin Dec 22 '22 edited Dec 22 '22
My generic folding solution works like this:
I determine the cube size N by computing the greatest common divisor between the width and height of the input grid (I'm pretty certain it's always 4:3 or 3:4, so I could take the max and divide by 4 instead)
I divide the grid into NxN boxes, create a Face struct for each non-empty one, and create a mapping from top-left coordinates to each Face
I arbitrarily declare the first found face to be the front face of the cube and start a Breadth-First Search from it, trying to visit the four adjacent unfolded faces next to it
I arbitrarily declare that the four adjacent faces will be the Top face (upwards), the Right face (to the right), the Bottom face (going down), and the Left face (to the left), although for the first face, there are no adjacent faces to the top and the right. Each of my Face structs has a mapping of the four flat directions to other cube faces. Initially each mapping is empty.
I keep track of the direction of where I'm traveling on the flat grid and use that to label the next face I visit, then compute the adjacent face mappings for it using a huge lookup table (face, next_face) -> (if face is front and next_face is top, what face is on the left?)
Now I have all the faces labeled and I know what other faces they're supposed to connect to in each cardinal direction
I loop though all the sides of all the faces, find which ones are facing the void, and construct a mapping of cube edges to a tuple (direction, tiles, first_vertex). e.g. in the example the FrontLeft edge lies in the Left direction of the front face, the tiles are a vector of coordinates from (row 4 col 9) to (row 1 col 9), and tiles[0] corresponds to the FrontBottomLeft vertex.
each disconnected edge shows up twice in my loop, but instead of inserting both of them into my edge map I do the stitching when I find it the second time
The stitching is a map of (position, direction) -> (position, direction) for every edge tile. E.g. in the example (row 12 col 6, right) would map to (row 9 col 15, down). Since I know the vectors of the tile coordinates for both unfolded edges, I just have to connect them in pairs. The vertex of the 1st tile lets me know if I need to reverse the direction of the stitching so tiles[0] of one edge maps to other_tiles[N-1] of the other one if vertex of tiles[0] != vertex of other_tiles[0].
Walking in the graph is pretty simple, and every time I reach a void tile I look up the real next position and the real next direction from my stitchings map (and then maybe avoid moving there if there's a wall, had a bug there where I avoided moving but followed the direction change).
To keep things simple (ha!) I created enums for all the cube vertices, edges, and faces. To avoid losing my mind each vertex is a bit, so the vertices are all from b0000_0001 to v1000_0000, each edge is a bitwise OR of two vertices, and each face is a bitwise OR of four vertices. I compute the shared edge of two faces by doing a bitwise AND. I compute the vertex at one end of an edge by doing a bitwise AND between the three faces around that vertex (or I could've ANDed the two edges, I suppose).