July 6, 2017 Playing with Problems

You often hear software engineers complain that “real software work” has nothing to do with solving algorithmic problems. Why waste time, they say, doing algorithms when we would never use them?
Sadly this complaint has some truth to it but I think we should still solve problems. And I’ll tell you why – it trains us to spend time playing with and developing a deep understanding of the problem instead of jumping into the first solution we find.
I have grown “through the ranks” of our industry – from a Junior Coder to Team Leader, Project Leader, and so on until my current position as Head of Engineering. Over the years I have found that the worst solutions and the biggest waste of time came when I or my developers rushed to deliver solutions to without truly understanding the problem well. Hours, even days, are wasted building something that no one wants. Then, to salvage the work done, we often shoehorn the solution into a limping, somewhat-usable, delivery.
On the other hand, anyone who has spent time solving algorithmic puzzles develops a feel for playing with problems. We know how rewarding it can be to see a difficult puzzle break down and become tractable.
You disagree? You’re not sure? Well, let’s see what I mean by looking at an example. We take the classic problem:

Given two strings, how would you check if one is the rotation of the other?
(For example “abc” and “bca” are rotations of each other.)

Rushing to a Solution

If we rushed to a solution we would rotate the first string and compare it with the second like so:

bool is_rotated(std::string s1, std::string s2) {
    if(s1.length() != s2.length()) return false;
    for(int i = 0;i < s1.length();i++) {
        std::rotate(s1.begin(), s1.begin()+1, s1.end());
        if(s1 == s2) return true;
    }
    return false;
}

Now this solution works fine and if we don’t like it we can try further improving the solution – perhaps using a modulus index instead of performing a rotating in the loop, perhaps optimizing the rotation itself and so on.

Playing with the Problem

However, instead of doing this, let’s try playing with the problem a bit more. Just try out the problem and take a look at a few rotated strings to see if any ideas jump out.

abcdef      i like programming          ab
fabcde      gi like programmin          ba
efabcd      ngi like programmi          ab
dfabcd      ingi like programm          ba
...         ...                         ...

Playing around like this, to me it ‘feels like’, there is a link between the first and the last character of the string. They are “tied together” somehow:

abcde.f...a
i like programming...i
ab..a

At least, they aren’t as far apart as they initially appear. Once we perform a rotation, we see the same “link” between other characters.

abcde.f...a...b...c...
I like programming...i...l...i...k...e...

So what would it look like if just went ahead and stuck the string to itself again?

abcdefabcdef
i like programmingi like programming

If we look at this carefully, and look at all possible rotations, we see that just sticking them together like this has given us a string with all possible rotations embedded!
Seeing this, our solution can completely change. All we need to do is stick the string in front of itself and see if the second string is a substring. Substrings are something we are much more familiar with. So the algorithm becomes:

bool is_rotated2(std::string s1, std::string s2) {
    if(s1.length() != s2.length()) return false;
    return (s1 + s1).find(s2) != std::string::npos; // (found or not)
}

Conclusion

From our initial O(n2) algorithm we’ve now got a possible O(n) solution that is much simpler! In this way, playing with the problem often can lead to a vastly improved solutions. This is why I feel doing algorithmic puzzles are good practice for real world software issues.