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.,
) 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.
- For each line, iterate over the contiguous groups from left to right. So, start with the leftmost.
- 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
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.
- Determine the first and last indices where a sequence of n
A couple of additional complications I encountered:
- The result in part 2 is larger than
Natural'Laston 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.