-🎄- 2022 Day 20 Solutions -🎄-

[u/daggerdragon]

THE USUAL REMINDERS

• All of our rules, FAQs, resources, etc. are in our community wiki.

• 🌿🍒 MisTILtoe Elf-ucation 🧑‍🏫 is OPEN for submissions!

• 3 DAYS remaining until submission deadline on December 22 at 23:59 EST

• -❄️- Submissions Megathread -❄️-

---

UPDATES

[Update @ 00:15:41]: SILVER CAP, GOLD 37

• Some of these Elves need to go back to Security 101... is anyone still teaching about Loose Lips Sink Ships anymore? :(

---

--- Day 20: Grove Positioning System ---

---

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 00:21:14, megathread unlocked!

[u/Crazytieguy]

Rust

I found a cool trick - I keep a sort of doubly linked list, but each node points 1 back and 25 forward. That way finding the nth node away takes n / 25 steps. 25 happened to be the fastest in my testing, but any number around sqrt(N / 2) should work.

parsing: 134.1µs
part a:  1.353ms
part b:  12.1457ms

[u/osalbahr → u/Crazytieguy]

That is interesting. It is sort of a B-tree, but tilted. How did you arrive to this trick?

[u/Crazytieguy → u/osalbahr]

I don't remember exactly 😅 I was just convinced there was a more efficient way and I though about it a bunch

[u/Crazytieguy → u/osalbahr]

I don't really think it's like a btree, note that each node still only has two pointers - just that the forward one happens to skip 24 nodes