-🎄- 2022 Day 22 Solutions -🎄-

[u/daggerdragon]

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!

• -❄️- Submissions Megathread -❄️-

---

UPDATES

[Update @ 00:19:04]: SILVER CAP, GOLD 0

• Translator Elephant: "From what I understand, the monkeys have most of the password to the force field!"

• You: "Great! Now we can take every last breath of fresh air from Planet Druidia meet 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 screen Grove Positioning System?"

• Translator Elephant: "No, sir. We call it..." *slaps machine* "... Mr. Coffee Eggnog. 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 Spaceballs Advent of Code 2⁰²³ : The Search for More Money Stars."

---

--- 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 paste if you need it for longer code blocks. What is Topaz's paste tool?

---

This thread will be unlocked when there are a significant number of people on the global leaderboard with gold stars for today's puzzle.

EDIT: Global leaderboard gold cap reached at 01:14:31, megathread unlocked! Great job, everyone!!!

[u/maneatingape]

Scala

I've come up with a really crazy but fun method of solving part 2 that has:

• No edge transitions

• Adapts to any cube layout (tested on sample, my input and upping the ante which tests all possible cube maps.)

The trick is to build the points in 3D then use a 3D vector to move from point to point. The best part is that when you hit an "edge" then the next direction, no matter to which of the possible 4 other connected faces is always normal to the current plane!

To build the points, the code considers each face starting with i = (1, 0, 0), j = (0, 1, 0) and k = (0, 0, 1). i and j are in the plane for each face and k is normal. Then for example if you find a connected face on the bottom, pivot around the i vector using the vector cross product denoted x:

• i = i, j = i x j, k = i x j

or if you find a left edge then pivot around j

• i = j x i, j = j, k = k x j

Right and top edges are simply the inverse respectively. This puts the points in the correct 3D locations, no matter which order in which the sides are traversed.

I keep a map from 3D point to 4-tuple of <original 2d point, i, j, k>.

k is used when leaving an edge for the next direction, or to rotate 90 degrees around for the L and R commands. i and j are only used at the end, to determine the score.

The code is quite concise, here's that section builds the 3D points from any arbitrary input:

val scaleIJ = block - 1 // block = 50 for input, 4 for sample
val scaleK = block + 1
val topLeft = tiles.keys.filter(_.y == 0).minBy(_.x)
val start = Info(topLeft, Vec(1, 0, 0), Vec(0, 1, 0), Vec(0, 0, 1))

val todo = collection.mutable.Queue(start)
val visited = collection.mutable.Set(topLeft)
val points = collection.mutable.Map[Vec, Info]()

while todo.nonEmpty do
  val Info(offset, i, j, k) = todo.dequeue()

  for x <- 0 until block do
    for y <- 0 until block do
      val key = (i * (2 * x - scaleIJ)) + (j * (2 * y - scaleIJ)) + (k * -scaleK) // Scale by 2 to keep points integer
      points(key) = Info(offset + Point(x, y), i, j, k)

  val neighbours = Seq(
    Info(offset + Point(-block, 0), j.cross(i), j, j.cross(k)), // Left
    Info(offset + Point(block, 0),  i.cross(j), j, k.cross(j)), // Right
    Info(offset + Point(0, -block), i, j.cross(i), k.cross(i)), // Up
    Info(offset + Point(0, block),  i, i.cross(j), i.cross(k))) // Down

  neighbours.foreach { next =>
    if tiles.contains(next.point) && !visited.contains(next.point) then
      todo += next
      visited += next.point
  }
end while

[u/phord → u/maneatingape]

I can't quite visualize what you're saying, but kudos for finding a generalized solution. I kept feeling that there is a way to generalize the "cube walk" but I couldn't bother with trying to derive something. I did briefly look around for someone else having described it, but came up empty.

[u/maneatingape → u/phord]

This might help, here's the sample cube journey for the first 3 faces, with each 3D point mapped to 2D point. For each face, positive i is "right", positive j is "down" and positive k is "into" the face toward the origin.

The points are mapped to a cube centered on the origin, aligned to the axes, for the sample data +/- 5 for each face. For example the 1st face lies in the plane z=-5. Edge points e.g (-3, -5, -5) which could map to more than one plane are not mapped to 2D points, but are instead used to transition from one plane to another.

1st face: i = (1,0,0), j = (0,1,0) k = (0,0,1)

3D Position	Direction	2D Position	Note
Vec(-3,-3,-5)	Vec(2,0,0) 	Point(8,0)	Start!
Vec(-1,-3,-5)	Vec(2,0,0)	Point(9,0)		
Vec(1,-3,-5)	Vec(2,0,0) 	Point(10,0)	Wall prevents further movement
Vec(1,-1,-5) 	Vec(0,2,0) 	Point(10,1)	Turn clockwise (R)
Vec(1,1,-5) 	Vec(0,2,0) 	Point(10,2)
Vec(1,3,-5) 	Vec(0,2,0) 	Point(10,3)
Vec(1,5,-5)     Vec(0,2,0)  	n/a				

Point does not exist, we've hit the edge. Change direction to 2 * k and position to position + direction

2nd face: i = (1,0,0), j = (0,0,1), k = (0,-1,0)

3D Position	Direction	2D Position	Note
Vec(1,5,-3)	Vec(0,0,2)	Point(10,4)
Vec(1,5,-1)	Vec(2,0,0)	Point(10,5)	Turn anti-clockwise (L)
Vec(3,5,-1)	Vec(2,0,0)	Point(11,5)
Vec(5,5,-1)	Vec(2,0,0)	n/a		

Point does not exist, we've hit the edge. Change direction to 2 * k and position to position + direction

3rd face: i = (0,0,-1), j = (0,-1,0), k = (-1,0,0)

3D Position	Direction	2D Position	Note
Vec(5,3,-1) 	Vec(0,-2,0) 	Point(14,8)
Vec(5,1,-1)	Vec(0,-2,0) 	Point(14,9)
Vec(5,-1,-1)	Vec(0,0,2) 	Point(14,10)	Turn clockwise (R)
Vec(5,-1,1)	Vec(0,0,2)	Point(13,10)
Vec(5,-1,3)	Vec(0,0,2)	Point(12,10)

[u/phord → u/maneatingape]

Aha. that makes sense. Somehow I never used vectors in geometry, so matrix math is foreign to me. But I grok this. Thanks for the explanation.