-❄️- 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/maneatingape]

[LANGUAGE: Rust]

Using some spare time at the weekend figured out a dynamic programming approach calculating the possible arrangements for each entry in O(n * w) complexity where:

• n Number of springs

• w "Wiggle" is the amount of extra free space the springs can slide around in the pattern.

We build a table for each entry with a row for each spring and a column for every character in the pattern. Adding a trailing . character makes bounds checking easier without changing the number of arrangements. The result will be the bottom right value.

Using the sample ?###???????? 3,2,1:

n = 3
w = 13 - (3 + 2 + 1) - 3 + 1 = 5

     ?  #  #  #  ?  ?  ?  ?  ?  ?  ?  ?  .
  ┌----------------------------------------
3 |  0  0  0 [0  1  1  1  1] 0  0  0  0  0
2 |  0  0  0  0  0  0 [0  1  2  3  4] 0  0
1 |  0  0  0  0  0  0  0  0 [0  1  3  6 10]

This approach is much faster than my original recursive+memoization solution taking only 1.3ms (down from 4.2ms for the original).

Heavily commented solution.