solving a facebook interview question in haskell

I loathe the new trend of interview olympics - the requirement that candidates submit themselves to a dog-and-pony show of solving puzzles in order to get an interview. A generation of hackers is now wasting time re-solving the same puzzles instead of providing lasting value by contributing to open source.

To that end, I would like to post a solution to one of the puzzles people seem to be chatting about, which is apparently used by facebook and interviewstreet, mostly because it was another fun opportunity to get some mental exercise. the problem is described as follows (partially copied from some site discussing this):

Given a string consisting of a,b and c's, we can perform the following operation: Take any two adjacent distinct characters and replace it with the third character. For example, if 'a' and 'c' are adjacent, they can replaced with 'b'. What is the smallest string which can result by applying this operation repeatedly?

Sample Input:

cab
bcab
ccccc

Sample Output:

2
1
5

Here is a solution in haskell:

gist

Another reader offered an alternative solution which in many ways is more elegant and haskell-y:

gist

last update 2012-04-05