Hello, there and welcome to my Advent of Code 2020 Day 23 cruise log. The gods of software did quite the number on me. To be fair, I did bait them into punishing me for today’s challenge. When I look at the final solution I wrote, I have some regrets. We’re in the endgame now and every minute matters. I can’t afford to waste hours writing less than optimal solutions even when I have the biggest hint of all. The hint in question is that the tiny input size for today. Every single time that happens, the naive solution has a complexity which will lead you to run code for days, literally. And yet, that’s what I did, even worse, I did a worse version of the naive solution which required much rework to eventually get right. Let’s jump into it.
Let’s keep the little habits we still maintain in place and start with the lore, shall we? Our hero is still on a raft, the trickster crab is still there as well. The little scoundrel decides to challenge us to a game of cups. We need to guess where cups will end following certain rules. The problem suggests that the cups’ arrangement is circular. There is quite an emphasis which I didn’t pick up. At least not as I should have. I thought about these Hackerrank challenges with array rotations. For some reason, my brain went there and I am still bitter about that choice as I write this. This was my second mistake.
What was my first mistake? I believe it was waking at 4 am and going straight for the challenge at 5. While you can get away with missing cues in a problem and still get round a solution within an hour, problems get harder, especially three days before the end. I need to get my motor running first, maybe with a workout. I will try that tomorrow morning and see how that goes. Maybe I will be at 100% then.
The problem when starting without being fully awake is that after a couple of hours the brain tires. Even with breaks and it gets worse throughout the day. Most days if I couldn’t finish within an hour or two, chances are I won’t close the challenge before nightfall. Yes, I know in winter night falls at 4 but still, that list pretty late when first reading the subject at 5 am.
So yes, rotating arrays is a pet peeve of mine, so imagine doing that so early in the morning half-awake. Only to run into bugs for hours and get the first part answer only after a lunchtime break. The worst was the infinite loops when searching values I didn’t need to search. I didn’t know that yet so I guess I can forgive myself on that. Some bugs were mostly me running into edge cases like a deer in the middle of a motorway bouncing from a car to the next. From wrongful assignments to the result concatenation part. I hit every error I could possibly hit.
The pain was real then came part two. If only I took the time to wake up properly and read through the problem carefully. Then I probably could have picked the right data structure right away. Even though I ran into other issues, I would have finished in half the time, maybe less.
Basically, in part two, we’re doing the same as part one but with about a million more entries to manipulate. This time we need to run ten million iterations over the hundred from part one. I had a funny feeling it would take more a few seconds to get a result. My part one code took about forty seconds to process a hundred iterations of that new game. After some minor adjustments, I managed to reach twenty-five seconds or so to run a hundred iterations. Better but nowhere near an optimal time. My code would take up to seven or eight weeks to run. Not great, as you can imagine.
Now that we know the state of my code and its speed isn’t acceptable, I need to rework it. Going through the problem, I start thinking about using doubly-linked lists. I wouldn’t create array copies so I drop some complexity but would still need to search some values. I ran into plenty of bugs on the insertion part of the algorithm, similarly to my first go at the problem. Infinite loops, wrong assignments and the like. I had to use heavy debugging and luckily VSCode offers this for Go as I recently found out.
After a couple of hours of trial and errors, fixing bugs while making more, I finally get it right. My first part tests went green again. So you can imagine the disappointment when I realised the part two tests didn’t return instantly. I started debugging because I thought that maybe I’m in an infinite loop again but nope. I still have a highly inefficient code. Less inefficient for sure but still horrendous. The search part is still an issue. I’m not sure how to tackle it, there must be some mathematical solution or some more clues in the problem. So I go back at it.
Then I realise something, I don’t need to search for the max value. The max value can’t be the one under our cursor nor one of the three follow-up values. This means that if these are the four biggest values, the fifth-biggest value will be our max. So we only need to search among five values, whether we have ten or a million. From there I hardcode these and update the code to remove my max search loop. Running the code again I see it still is as slow so the gain must be negligible. I actually create an array with the possible max values to iterate and a map where the keys would map the node values to the node pointers. From there getting my max value as a time complexity that goes towards constant which is on a large input equivalent to O(1).
At this point, the only thing that could possibly take so long is the minimum value search. I go over all the nodes until I find the minimal value. Time complexity O(N). Generally, it’s fine but for the sort of work we’re doing we can’t afford that and I feel like I should have spotted this earlier. That’s when it hits me. If I can look up my max value using a map, what is stopping me from doing the same to get my search value? I compute it from my cursor so I can just look it up through the map.
Upon that realisation, I make the change and now the impossible game of ten million moves runs. Finally, I get to run my part two test, it takes a couple of seconds to run but it fails. I felt like I was about to reach nirvana but I end right back in the gutter. I’m so close I can touch it. I run all my tests over and over, uncomment and adjust my past tests to use my new methods. They all pass but my part two keeps failing. From there the only difference is the input. We have more entries and the initialisation varies somewhat.
Going through the problem again I realise the values label begins at one. My loop to get to one million stops shy of one. I’m lacking precisely one value, the million. Same for my max values array. The test passes at last. Finally, here we are, born to be kings, we’re the princes of the universe! I run the now cleaner code against my input and get my forty-sixth star of the year, already six more than my last year record. Two more days, hopefully, I will learn from today and complete the final challenges in a more timely manner.
Thank you for reading my Advent of Code 2020 Day 23 cruise log, I will see you tomorrow, maybe. In the meantime, you can check out my Go Cloud series about building and deploying a Golang app to AWS. Also, I will push my code on Github at CodingNagger/advent-of-code-2020. Feel free to check it out but not before you’ve done the challenge yourself. Bye!
