Today, I have solved Project Euler problem #31. Oh, what a relief.

To be honest, it’s a very simple problem. In fact, the problem’s difficulty is reported back to you after you solve it. This one was rated 5%. To make matters worse, the hardest problem difficulty on that website that I have been able to solve was 35%. Not much greater, but clearly something to take into account when remembering that between my first attempt at this problem and my final solution to it stand 5 whole years.

No, I did not spend every day and every night of those five years trying to come up with the solution to this problem. Far from that. There might have been good months between every attempt that I have had, while each attempt lasted a day or two. I was not extremely focused during those attempts, and neither did it matter to me whether I have solved it or not. Or so I thought.

The importance of solving this problem was hidden from me: not being successful in my half-hearted pursuit after so many equally half-hearted attempts has been eating at my sanity in the corners of my subconscious self. I did not realize how much of an impact it had right until I took a serious look at this problem this morning: I was puzzled; I was annoyed; I was livid. “I am a software developer,” I thought. “My mind is made to tackle problems like that, and yet here I am, not able to solve a silly problem numbered 31.”

I have rules of engagement with problems that I intend to use to test my mental capacities. The internet access is allowed, but there’s a very fine line between looking up a solution and looking up help to direct one’s thought process. It is always hard to know what counts as cheating. I recall, once ChatGPT became huge, I tried putting the description of the problem into it. I cannot tell you what I was expecting it to see, but I saw was exactly what one would expect to see: working code that just had the problem right. I stepped away and did not submit the result: It did not count. I did not solve the problem. A computer did it. So what if a computer can solve this? There are many computers that have solved problems orders of magnitude harder. In the end, this did not teach me anything. I was sad to see the solution and have had to dismiss it. I stepped away from the problem for the next couple of months.

April 20, 2024 came around. I had it in my calendar. I was going to tackle this problem one more time. This time, I was determined to fight with it until I have solved it myself. (We are not going to talk about my determination while I was struggling with it.) Equipped with my freshly-dusted-off CLRS and newly-purchased Skiena, I decided to give it a shot.

Usually, I would start with a code editor open and ready to write hot solutions. As you might know, this is not a good method to solve problems! This time, however, I decided to admit that this indeed might not be the best way to approach something that has been eating at me for so long. I decided, until I have a solution that works on paper, I am not even going to start writing code. (Good job at reinventing the wheel, Seymour.) So I started with a simplified version of the problem and came up with a solution manually. I did not use an algorithm; rather, I have tried to infer the algorithm from my solution.

The following is the simplified problem that I was tackling:

You have an unlimited supply of coins valued 1, 2, and 5. How many possible combinations of coins summing up to 5 are out there?

This one is easy to tackle without writing any code: you just write it out. The solutions are simple enough: [5], [2,2,1], [2,1,1,1,1], [1,1,1,1,1]

The algorithm I used here - which is not the correct algorithm - is roughly this:

1. Pick the largest number in the list.
2. Break it into the maximum number of values just one lower than the given value in the list, while subdividing the ‘rest’ into even smaller values, once you can no longer fit the ‘value’ into the lesser block.

That is, if you have 5, it does not break into 2s cleanly. It breaks into 2x 2s and has a carry-over of one. Luckily, the next smallest value is 1, so that takes care of the carry-over value.

The final solution was to be executed on a list of coins valued [1, 2, 5, 10, 20, 50, 100, 200]. As I successfully - or so I thought - solved further incarnations of the simplified problem, I increased the complexity of the example at hand by including the next coin-value into my simplified list. In that manner, my next list would have been [1, 2, 5, 10]. I did that for a couple of iterations, increasing the complexity of the problem, until I was no longer able to keep track of the outcomes by hand. I revisited previous solutions and saw a critical mistake.

By that time, I was already solving the problem with some sort of “inferred” algorithm. It was not too complex, but I was able to grasp the existence of some sort of “forking.” That is, I could see that while there are some solutions that I could land on only if I always break the largest value in the current list - the algorithm described earlier - there were some solutions that I could only land on if I did the opposite: break only the lowest possible value that is greater than 1. It drove me crazy. I could not grasp the parallel processing of the same values.

At this point, I decided to retreat from my by-hand calculations and get into some reading. Mind that it has been quite some time at the problem and I have not even touched the keyboard.

I opened every student’s beloved ‘The Algorithm Design Manual’ by S. S. Skiena. I knew that the problem had to do with some sort of combinatorics, so it was easy to track down chapter 10.5 (and later, 16.10). For the next hour, I got lost in trying to understand the code and the algorithm intuitively. This book is not an easy one to chew through and my brains started to steam. I decided to retreat into the GYM to let my subconscious mind do the work, while I get my mind off the problem. At the end of the chapter, I found a problem that was very similar to the one at hand. It was sufficiently different for me to take a shot at it without the emotional baggage of the previous failures, while still being solvable by hand. I read that right before leaving my apartment to let it properly marinade my mental landscape.

By the time I was back, I was no longer so convinced that today’s the day the problem would be solved. I re-read the description of the problem stated in chapter 10.5. It was only after some attempts to look up the explanation of the algorithm’s logic that I was able to understand what exactly Mr. Skiena meant. (I am slow, and while I do not mean to seek excuses for that slowness, it has been a while since I read a formal mathematical or computer science text, so I felt rusty.)

I have not implemented this chapter’s Dynamic Programming paradigm, as I was trying to merely understand the algorithm. The core algorithm ended up being something like the following (Mind that the solution here is intentionally left vague as the exact code/pseudo-code is not something that would bother a layperson, while those who are solving PEN31 could benefit from having to jog their mind [Presumably that’s what they are doing it for]):

myHandDrawnRecursiveFunction:

1. Have we solved the problem (base case)? Yes -> return 1. No -> return 0.
2. Do the following in parallel (recursively): 2. Come up with the solution for the array including the current coin selected. 3. Come up with the solution for the array excluding the current coin selected.
3. Return the sum of the two.

Aha! The forking is there! Per Skiena’s explanation, we do have to use some sort of forking to solve the problem. The algorithm is different, so the forking process had to happen between different qualifiers, but the inkling of its existence that I got earlier was reasonable!

Having understood the core algorithm, I opened my code editor. I have already had a file that I set up for solving this problem last time I attempted at it. It so happens that I put a header on top of my code files, and this one spelled:

// problem31.cpp
// Created: Mon 13 Feb 2023
// ------------------------
// Seymour Pashayev
// gitHub:@SeymourPashayev
// ------------------------
// Description:Solution to Project Euler Problem 31

Feb 2023! It has been a while!

I wrote and ran the recursive code for my initial test setup of [1, 2, 5]. It worked, the result was 4! I tried the same for my increasingly-complex simple problem-sets. It worked, although I had to go back to my hand-traced examples (and find more errors in them) to make sure that it did indeed work. I was aware that the solution presented in Skiena’s example was meant to be dynamic. Mine, however, was not. Noticing how fast the code ran, I assumed that my search for a dynamic algorithm might have been universe-old premature optimization, so I ran it for the final problem-set of [1, 2, 5, 10, 20, 50, 100, 200] without even paying the dynamic ’thing’ a mind. After all, if it stalls, I will just revisit it with the dynamic algorithm.

Lo and behold! It returned the answer pretty much immediately! I did not believe that it’s the correct answer! Something must be missing! Almost no first-solution is right-solution! I promptly plugged the answer into the PEN31 prompt. I got that silly green checkmark they give you on a correct answer. I was beyond excited: I started screaming profanities at the top of my voice. “I finally solved it!” This was an event worthy of celebration.

It is on this screen when you get to find out what % on the challenging scale that problem ranks. I was, of course, not expecting it to be the most challenging problem I have solved, but I was appalled to find out that it was rated a mere 5%.

Here are some thoughts and lessons that come out of this, at the very least for me. I was very affected by my previous inability to solve this problem. So much so that every time I have attempted to solve it, it was already stained by my previous attempts at it, carrying the burden over and over, multiplying it with each iteration. It was further compounded by my distracted approach to the problem: Aside from the very first and the very last attempt to crack this, I have not been very attentive or focused. I was opening the webpage to look at these concepts ridicule me when I was bored. I never had an existing desire to solve them - well, I did, but it was only secondary - the main driver of my action was boredom. It was not the kind of boredom that one might find beneficial; I was just trying to “kill time.”

All of that added up to my stress and lack of genuine desire to tackle this problem. One might say, I was like a recursive function that needed a dynamic approach (yes, I give you my permission to execute me for this joke [pun intended, since we are talking recursion here]).

Now, of course, it was clear to me that the problem was not a hard one at all. It was among the simpler problems that I have solved in my career. It was not the challenge of the algorithm that was hanging over me, but that of fear of my own failure. I could not bear the idea of approaching this problem and not solving it one more time. This drove me away from Project Euler. Now that I have faced this issue and put dedicated time aside to solve it, I am more than excited to continue my journey onto the next unsolved problem, which happens to be #38.

There are many more to go.

Ad victoriam.