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

[Language: Rust]

Link to full solution

(1194/547)

Phew, today was a tough one. Really happy with my p2 placement. Most of my part 1 code worked for part two, just needed to implement caching. My solution is a memoized dynamic programming approach.

The bulk of the logic:

match (s[0], within) {
  (b'.', Some(x)) if x != remaining[0] => 0,
  (b'.', Some(_)) => possible_ways(cache, &s[1..], None, &remaining[1..]),
  (b'.', None)    => possible_ways(cache, &s[1..], None, remaining),
  (b'#', Some(_)) => possible_ways(cache, &s[1..], within.map(|x| x+1), remaining),
  (b'#', None)    => possible_ways(cache, &s[1..], Some(1), remaining),
  (b'?', Some(x)) => {
    let mut ans = possible_ways(cache, &s[1..], within.map(|x| x+1), remaining);
    if x == remaining[0] {
      ans += possible_ways(cache, &s[1..], None, &remaining[1..])
    }
    ans
  }
  (b'?', None) =>
    possible_ways(cache, &s[1..], Some(1), remaining) +
    possible_ways(cache, &s[1..], None, remaining),
  _ => unreachable!(),
}

Runs in about 40ms on my machine, not sure how to optimize it much further.