Examining a well-designed programming puzzle

As this past Wednesday was the International Workers’ Day and I was not working, I had time to engage in a little programming-related brain teasery, as I have been known to do from time to time in the past.

This time around, I found a puzzle of the type you can expect to encounter in a programming competition or during the hiring process of a software company with high technical standards, such as Google or Amazon.

This particular problem originated in a course on competitive programming at the National University of Singapore and was designed by Sidhant Bansal but it is universal enough that it could have shown up almost anywhere. That is not to say there was anything bland about the problem, of course. Quite the contrary: I believe that the problem is very elegant in that it is deceptively simple in its statement, but has more complexity underneath than first meets the eye.

My aim with this post is to illustrate the many layers of this problem in such a way that most of the information is accessible to somebody without knowledge of computer programming.

Problem statement

In my wording, rather than the original formulation: Given a number of strings of text (we can think of these strings of text as words, if that helps) and an order in which to assemble them, what does the final resulting string look like?

Example

We are given three strings: hop, skip and jump. We are then told to attach the third string to the end of the second string. Then, we are to attach the first string behind the result of the concatenation of strings 2 and 3. We can call this string 2 + 3 + 1, as the second string comes first, followed by the third string, and finally the first string. The resulting string would then be skipjumphop.

Seems easy enough, right? Well, conceptually it is. Writing a solution that solves this problem is easy for an experienced programmer. The trick is that if care is not taken, and the code bears too many characteristics of what we would call a brute force approach, then the program requires an unacceptable amount of RAM and CPU time for large problem sizes.

Problem size

Let’s formalize what we mean by “problem size”. The original statement of the problem posed two limits, or upper bounds: There may be no more than 100,000 strings (again, think of them as words if that helps you visualize the problem) and the total size of all strings will not exceed 1 million characters. This is very important information when designing a solution as it tells us something about the worst cases we can expect. Some extremes we may want to be extra conscious of includes the case of 100,000 strings of 10 characters each, as well as one case where we have 99,999 strings of one character each, and then a final string that uses some 900,000 characters. Our “nightmare” scenario would then be if the monster string of 900,000 characters repeatedly gets added to the back of all the other strings, growing by one character at a time. We shall see further down in this post why this poses such a problem for us. Can you think of any other cases that might cause us troubles from a performance standpoint?

The many obstacles ahead

I will now try to describe my journey towards a solution and the many pitfalls on my way there. Some of these traps I just ran blindly into, while others I actually anticipated, but verified that they were indeed just as problematic as I had thought.

So what did this process of figuring out what worked and what did not look like? Well, the problem existed on an online platform that allows users to manually submit their own code for many similar problems. This platform is called Kattis and is just plain awesome. What happens then is Kattis runs my code against a set of test cases that I am entirely unaware of what they look like. All I know is that the examples are subject to the restraints discussed above. The feedback can be a number of things, but the most important ones might look like this

• Correct answer - you solved all test cases in 0.53 seconds!
• Wrong answer - your code provided the wrong answer to test case 4 out of 11
• Out of memory - your code used more than the allowed (1 GiB) of RAM allowed on case 5 out of 11
• Time limit exceeded - your code had not finished within the allowed time (1 second) for test case 4 out of 11
• Run time error - your program exited unexpectedly on problem 6 out of 11

The last one is in many ways problematic as it could stem from any number of reasons.

My incorrect approaches and why they failed

1

The brute force approach discussed above: Just naïvely glue strings together and return the end result.

Result: Out of memory. Considering the nightmare case above, of one monster string of about 900,000 characters repeatedly getting attached to the end of the other strings, it is easy to see why this would happen. In the worst case, this would give us 100,000 strings, with lengths between 900,000 and 1,000,000 characters each (as we keep the intermediate results). Resulting in about 100,000 * 950,000 bytes, or about 100 times the allowed amount.

2

New idea: Do the same as above, but delete every string once used. Let’s illustrate this.

Previous approach, using the example from above:

Start: hop skip jump

Step 1: hop skipjump jump

Step 2: hop skipjumphop jump

As we can see, we unnecessarily keep track of hop and jump, even after we no longer need them. So this improved approach would mean:

Start: hop skip jump

Step 1: hop skipjump

Step 2: skipjumphop

Much better! But alas, this still does not cut it. The reason may be a bit subtle if you are not a seasoned programmer, but the kicker is that concatenating strings is a rather costly operation. Especially when done many times and with long strings. Result: Time limit exceeded. So the conclusion is that we need to somehow solve this problem by only concatenating all the strings in one single operation.

3

The next idea is, then, to compile an ordered list of indices for the strings we are interested in. That is, rather than directly appending string #3 to the end of #2, and then subsequently adding #1 to the end of that string, generate something like: 2 3 1.

The final step of this program would then be to concatenate all the strings using these indices. Luckily, this step is quite simple, i.e. (Python 3):

‘’.join(strings[i] for i in orderedIndices)

So, the questions remains, how do we create this list of indices (called orderedIndices above)?

A natural way would be through recursion - a topic familiar to those well-versed in programming or mathematics, but perhaps out of scope for the approach of this article.

Suffice to say, compiling this list of indices through recursion produces Result: Run time error and thus does not work. As mentioned above, run time errors can be hard to interpret on this platform, but experience tells me this is caused by hitting the maximum recursion depth limit.

4

An approach that sometimes works when we hit an RTE due to hitting the maximum recursion depth limit is to simply raise the limit. Given that we might expect 100,000 recursive calls this does not seem like a promising approach, but why not try it? Sure enough, Result: Time limit exceeded. Recursive calls are expensive, so this is not too surprising.

5

Luckily, a recursive algorithm can usually be re-written to what we call an iterative form, meaning we have all the benefits of the approach above, but none of the downsides of repeated recursive function calls.

Sure enough, this approach yielded the Result: Correct answer (0.53 seconds). And thus, I was done.

To reiterate, the most important roadblocks encountered (I’ve actually left out some other, minor ones) were:

• Not eliminating used up strings
• Doing too many concatenations
• Using inefficient recursion instead of iteration

The many layers of this problem, where each new roadblock can be overcome through sound engineership is what makes this an exceptionally well-designed problem in my eyes.