Well, for every thing I said in yesterday’s notes, today I acted somewhat contrarily.
- I visited a thread (not the solutions thread though) on the subreddit before I had fully solved today’s problem (I’d only solved part 1).
- I spent a good deal of time on optimizing my solution to run quickly rather than settling for the first dumb slow thing that I thought of (I kind of had to this time).
- At the end, I did actually (and with only the barest of prompts) grasp the efficient, readable, elegant, concise FP method to do what I needed.
I preserved my first two false starts in day05-try1.rkt.
The first version I wrote based on simple string substitution was so slow that after five or ten minutes I gave up waiting for it to finish.
Then I thought, well, let’s try vectors. I devised a version that held all the characters as ASCII values in a vector, and instead of removing values it simply flipped the annihilated units to 0 in-place. That version finished in about 64 seconds, which seemed like an improvement, and it did give me the correct answer.
Then I saw part two and realized that I was probably going to have to basically re-solve a new list for every letter in the alphabet. I was pretty sure the correct solution shouldn’t take half an hour to compute!
It was getting to the end of my lunch hour. Hoping for just a hint, I opened a thread on the subreddit — this one, not the solutions thread. It was mainly just a joke about how people’s “optimizations” of their day 5 solutions was making them take longer. But there was this one comment, and it was the hint I needed:
nope. I was getting that too. You want to use a queue or a deque, not repeated applications of "react".
I’d never heard of “deque” before but I guessed what was meant by “queue”: they were talking about a stack! Of course! Just push each unit on to a new stack one at a time and do the aA reactions as you go. That way you only process the input list a single time from start to finish, with no searching and replacing.
My third and final solution for part 1 computed in 6 msec.
With so much new-found speed in my part-1 solution, I had plenty of room to solve part 2 the “dumb” way. Just boil a separate solution for each of the 26 letters of the alphabet and compare them. Still computes in less than a second.
The final versions of my solutions for both parts can be found in day05.rkt.
Extra credit
Finally, in part two, I was curious: A) what letter did the program end up removing to get the shortest-possible reacted list? And B) was it the same letter that simply had the most occurrences in the initial input?
As it turns out: no. In my case, removing v/V yields the shortest reacted list, but x/X had the most occurrences. In hindsight this makes sense; having the most occurrences means little for the problem’s “reduction-by-reaction” mechanic if those occurrences aren’t mostly alternating upper-/lower-case.