Top Coder Problem - WolfDelaymaster

During my last SRM 593 on TopCoder I found the medium problem quite interesting and I was happy that I have been able to solve it relatively quickly using the technique of Dynamic Programming.

Solving this problem taught me two important lessons:

1. The power of Dynamic Programming
2. The trap of over-optimization

The interesting thing is that I didn't realize the second lesson until I wrote this post so I am really glad I decided to write it.

I am going to quickly describe my solution.

The problem statement: WolfDelaymaster (Why register on TopCoder?)
My solution: WolfDelaymaster implementation.

The definition of the problem suggest an immediate recursive implementation.

You can first check that the string satisfy the first condition. You start checking against "wolf", then "wwoollff" and so on. Considering that the maximum input string is 50 characters the biggest string to test against contains 12 times each individual character.

1. For each positive integer n, the string which consists of n copies of 'w', then n copies of 'o', then n copies of 'l', and finally n copies of 'f' is a valid word.

If this test fail, we can use the second rule and split the original string in two parts and recursively check them. It is important to try all the possible split points that are multiple of 4 (there are no valid strings shorter than 4 characters).

1. The concatenation of two valid words is a valid word.

This is the initial implementation:

Does this implementation works?

Yes, it works!

Are you concerned about the performance implication of having two recursive branches?

I was and for some reasons I decided to apply the technique of dynamic programming in order to speed up the program. You can learn more about dynamic programming on Wikipedia. It basically consist of caching the intermediate result of computation to quickly cut the recursion tree.

Here the implementation (addition highlighted).

Does this effort was required?

Absolutely not!!! The original implementation was good enough.

What is the worst case?

The worst case is a string that is invalid with a length of 50 characters like "fofflwllwooowowwwllllwlwllwwlwwfwwfwofwwfolowlolwo".

The execution time of the original algorithm on the worst case is: 0.0110 seconds.
The execution time of the optimized algorithm on the worst case is: 0.00056 seconds

Dynamic programming is powerful as it improved the speed of the algorithm of a factor of 19 but in this case it was not necessary. This is the biggest mistake I made. I wasted a lot of time that I could have spent on the next problem.

It is worth to mention that the problem could have being solved in an iterative way but for some reasons the I didn't get it during the competition and the recursive implementation was more natural for me.

This is a possible implementation adapted from the winner of the competition (I didn't test it using the TopCoder system tests).

The time of the iterative version on the worst case is: 7.1E-06

This version is absolutely the quickest version!