2023 Day 12: Hot Springs


just kidding. but this one took me a long time. We seem to have entered the fiendishly difficult phase. Fortunately, difficult problems are usually followed by not-so-difficult ones. Usually.

  • I first completed part 1 using a recursive algorithm that pruned failing branches. No problem, though it was a bit slow, so I knew what was coming next.
  • Yup, Part 2 inflates the input to an insane size. The first record completed quickly, to my surprise but I quit the program after it dawdled on the second record for several minutes.
  • I stared at it a while.
  • Finally, I visited the Reddit solutions page. People were mentioning “DP”. What the heck is DP, thinks I, feeling a little humiliated at not knowing. Scrolling down a little, I see that someone else has the wherewithal to ask. It means “Dynamic Programming”. Oh yeah, says I, albeit a little more colorfully. (i.e., :face_with_symbols_over_mouth:) I remember something about that from my Algorithms class. But… how?
  • Reading a bit more, I see what people say they are doing. Unfortunately, they are writing in languages like C++, D, Python, Rust. Excerpts range from illegible to incomprehensible out of their context. Probably doesn’t help that’s it’s 2am. Oooookayyyyy… time for a nap.

Thinking about it this evening, I realized that I could do the following.

  1. For each line, iterate over the contiguous groups from left to right. So, start with the leftmost.
  2. Assume the group records n damaged springs,
    • Determine the first and last indices where a sequence of n # can appear.
    • For each i in 0 … last index - n (or something like that; I don’t feel like looking at the code now) create a sequence of i . followed by n # followed by ?. Then see if that sequence matches the corresponding subsequence of the recorded condition of springs. A picture is probably worth 1000 words here: if n is 3, and the distance from first to last is 5, look at ###.., .###., ..###. It is easy to tell whether this matches .#?#?.***
    • If it matches, take the next contiguous group and recurse (step 2) with an appropriate starting index for the next string. (Have I mentioned how I :heart: Ada’s custom indexing?.)
    • This is a key point. If you don’t want to wait forever, store the result in a cache of some sort – I used a hashed map.

A couple of additional complications I encountered:

  • The result in part 2 is larger than Natural'Last on my input, so you’ll likely need something larger.
  • If you use a hashed map for the cache, be prepared for some moding. I do wonder if I’d have done better with an ordered map.

There was more, but I can’t remember it now.

***I don’t recall reading this detail anywhere in the Reddit discussion of solutions, but then again, I don’t think so well at 2am. Either way, I’m pleased as punch that it seemed different.


Similar thoughts and feelings…
Since I’m trying to solve everything with HAC, I have to live with its limitations…

  • I chose to attack the lists from the right, in order to preserve the index 1 over recursion.
  • Absent hashed maps, I found another, simple way to memoize partial results.

Latest version is here.

1 Like

Yeah, I looked at your code last night I think. It looks a lot like the little I could fathom of the discussion on Reddit. It seems simpler than the approach I used.