Part 1:

The code is pretty simple if we go ahead with using recursion. I started with an iterative solution but quickly realised I am dealing with a list of numbers, going through the numbers one at a time. This is the prerequisite of solving a recursive problem.

The Recursive Solution:

The condition is that the input string will have at least one number, otherwise it won’t make any sense. Though we are not dealing with erroneous input here.

The recursive solution is just so easy on the eye and on the mind:

  1. We start with the first character, and if the remaining string is empty then return that character and it’s count.
  2. If we the new character is same as the previous character, then update the count and recursively solve for the remanining substring.
  3. If the new character is different than the previous character, then add the count of this character to the recursive solution of the rest of the string.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

public static string LookAndSay_Recursive(string number)
    {
        return _NumberCounter(1, number[0], number.Substring(1));
    }

private static string _NumberCounter(int currentCount, char currentChar, string remainingChars)
    {
        if (string.IsNullOrEmpty(remainingChars))
        {
            return currentCount.ToString() + currentChar.ToString();
        }
        else if (currentChar == remainingChars[0])
        {
            return _NumberCounter(currentCount + 1, currentChar, remainingChars.Substring(1));
        }
        else
        {
            return (currentCount.ToString() + currentChar.ToString()) +
                _NumberCounter(1, remainingChars[0], remainingChars.Substring(1));
        }
  }

Since c# doesn’t support tail recursion, a lot of the calls in the else-if clause cannot be optimised, nor can we do anything about the else clause.

Running this on my machine for 50 iterations of 3113322113 quickly sends CPU and memory usage through the roof (100% usage of 1 core and nearly 900MB of RAM before I stop it after 15 seconds or so). Ouch!

Back to iteration:

Honestly, the iterative solution is not that bad. We create a string of the number and counts and fill it when we detect a change in the current number-character, or at the end of the input.

This runs through the 50 iterations in a couple of seconds on my machine.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public static string LookAndSay_Iterative(string number)
{
    StringBuilder sb = new StringBuilder();

    int count = 1;
    char currentChar = number[0];

    foreach (char c in number.Substring(1))
    {
        if (c != currentChar)
        {
            sb.Append(count.ToString()); sb.Append(currentChar.ToString());
            count = 1;
            currentChar = c;
        }
        else
        {
            count += 1;
        }
    }
     sb.Append(count.ToString()); sb.Append(currentChar.ToString());
    return sb.ToString();
}

The code is present at github.