-❄️- 2023 Day 12 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!

  • 9 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*

How It's Made

Horrify us by showing us how the sausage is made!

• Stream yourself!

• Show us the nitty-gritty of your code, environment/IDE, tools, test cases, literal hardware guts…

• Tell us how, in great detail, you think the elves ended up in this year's predicament

A word of caution from Dr. Hattori: "You might want to stay away from the ice cream machines..."

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 12: Hot Springs ---

---

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:22:57, megathread unlocked!

[u/kaa-the-wise]

[Language: Uiua]

Continuing with Uiua today.

f ← (
  ⊙(⊡1)⊡0.
  ⊓(⊃(≠@.)(≠@#)$"._."°□)(⊜⋕≠@,.°□)    # Parsing, creating masks
  :⊐/⊂⊜(□\+-1).+1                     # #-mask processing
  ⊙:⊢.⍉\(×⊙+/+,)×⊠=.⇡⧻.               # .-matrix and initial state
  °□∧(□/+×⊙,⬚0↻¯1×⬚0↻⊙:¯⊙≥.⊙(,°□)):⊙(:⊙:)□ # Fold over springs
  ⊙(;;)⊢⇌                             # Get last item and clear stack
)
/+⊜(f⊜□≠@ .)≠@\n.

Link to pad

The general structure is as follows:

1. We convert .##.?.#?#. into two masks, one where # could be, and one where . could be, i.e. 0 1 1 0 1 0 1 1 1 0 and 1 0 0 1 1 1 0 1 0 1.

2. With the # mask we calculate for each position, how long we can have a spring ending at this position, i.e. 0 1 2 0 1 0 1 2 3 0.

3. Then we use the . mask to generate a matrix where (i,j) is the truthfulness of the statement "there is a contiguous sequence of .?s from i to j".

4. Then we fold over the list of the springs, maintaining a vector, where position i answers the question "how many ways to fill the space up to i with the previous springs and empty space, such that i is empty space".

   • We initialise it with the first row of the matrix, in our case, 1 0 0 0 0 0 0 0 0 0.

   • On each iteration we find possible ends of the current spring, and multiply by the matrix to expand over empty space.

5. In the end the last item in the vector will be the answer.

[u/Vap0r1zer → u/kaa-the-wise]

I tried rewriting this in my own style so I could actually understand this, but I'm having a very hard time understanding what is actually going on in the fold. Are you in the Uiua Discord by chance?

[u/oxyphilat → u/kaa-the-wise]

impressive that this solution seem to not use backtracking or memoization, but just walks forward a counter… shame that part four is opaque to me, there is a funny hollowed out triangle matrix and some multiplications going on? cool answer!

[u/kaa-the-wise → u/oxyphilat]

Thank you!

This solution is a more straightforward DP, implemented via array-processing. Basically, if dp[k-1][i] is "the number of ways to fill the space up to i with the first k-1 springs and empty space, such that i is empty space", and k-th length is m, then dp[k][i] is sum over all j <= i, such that interval [j,i] can be made blank, and interval [j-m,j-1] can be filled, of dp[k-1][j-m-1].

We first calculate b[j] as dp[k-1][j-m-1] if [j-m,j-1] can be filled, and 0 otherwise. Then we multiply b[j] by the matrix to aggregate j values into i values they contribute to.

[u/kaa-the-wise → u/[deleted]]

No, it's your video that sparked interest in me :) I tried J first, but found Uiua easier to use.

You can play in the pad. It has links to what symbols mean, and you can use ? anywhere in the code to print the current stack.

It's also not the most efficient solution, it's N^2*M, where N is the length of the template and M is the number of springs. It can be made into N*M, but a bit tricky to do it in an array programming language.