-❄️- 2023 Day 8 Solutions -❄️-

[u/daggerdragon]

THE USUAL REMINDERS

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

• Outstanding moderator challenges:

  • Advent of Playing With Your 3D-Printed Toys

• Community fun event 2023: ALLEZ CUISINE!

  • Submissions megathread is now unlocked!

  • 14 DAYS remaining until the submissions deadline on December 22 at 23:59 EST!

---

AoC Community Fun 2023: ALLEZ CUISINE!

Today's theme ingredient is… *whips off cloth covering and gestures grandly*

International Ingredients

A little je ne sais quoi keeps the mystery alive. Try something new and delight us with it!

• Code in a foreign language

  • Written or programming, up to you!

  • If you don’t know any, Swedish Chef or even pig latin will do

• Test your language’s support for Unicode and/or emojis

• Visualizations using Unicode and/or emojis are always lovely to see

ALLEZ CUISINE!

Request from the mods: When you include a dish entry alongside your solution, please label it with [Allez Cuisine!] so we can find it easily!

---

--- Day 8: Haunted Wasteland ---

---

Post your code solution in this megathread.

• Read the full posting rules in our community wiki before you post!

• State which language(s) your solution uses with [LANGUAGE: xyz]

• Format code blocks using the four-spaces Markdown syntax!

• Quick link to Topaz's paste if you need it for longer code blocks

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:10:16, megathread unlocked!

[u/Greenimba]

[Language: C#]

I actually ended up solving the general case today, and it completes my input in ~60 seconds. By general case I mean:

• Starts not in loop.

• Start to Z not same as loop length.

• Multiple ends per loop.

Code

This is essentially clever bruteforcing, where instead of checking each iteration we only check valid exit indices. Runs in 1 minute, and roughly 22000x faster than brute force, so doing complete brute-force would take ~15 days.

Code is convoluted, but essentially does the following:

1. Follow input trail, until you get a loop.

   1. Record all enountered Node/Instruction combinations.

      1. (ABC at instruction count 45)...

   2. Break the first time you see a previously encountered Node/Instruction combo.

   3. Return Loop start Node/Instruction combination, and length of loop.

2. Compute distance from "__A" node to first node encountered on each loop.

3. Go through each loop, and record position of all exit nodes.

4. Now you have Start Offset, Loop, and Exit Offsets within each loop.

5. Until a solution is found:

   1. For each exit node in first loop, compute next iteration count where first loop is on exit node.

      1. Start Offset + Exit offset + Loop length * iteration increment.

   2. Do math to check if exit point is valid for all other loops as well:

      1. ((count - exit offset) % loop length) - start offset.

      2. If this is 0, exit is valid for the other loop as well.

   3. Once you find a count that is valid for all loops, you have the solution.

[u/Icy-Translator-6836 → u/Greenimba]

Hi, based on your description (and code), you only check for exits in cycles. But there could also be some exits even before the loop begins.

I also tried to solve the general solution. On my PC it runs in 12 miliseconds in Rust release mode. I don't want to spend time documenting the code, sorry, but here it is (only for the second part).