Cedric’s Coding challenge

I noticed Cedric’s Coding challenge while reading Robert Fisher’s blog.

Here is an interesting coding challenge: write a counter function that counts from 1 to max but only returns numbers whose digits don’t repeat.

For example, part of the output would be:

• 8, 9, 10, 12 (11 is not valid)
• 98, 102, 103 (99, 100 and 101 are not valid)
• 5432, 5436, 5437 (5433, 5434 and 5435 are not valid)

Also:

• Display the biggest jump (in the sequences above, it’s 4: 98 -> 102)
• Display the total count of numbers
• Give these two values for max=10000

Because I love coding problems, I whipped up a C# 2.0 solution which is not as succinct as some of the functional solutions, but it works on a ‘fast enough for me’ time scale.

using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace ConsoleApplication1
{
  class Program
  {
    static bool[] used = new bool[10];
    static int value = 0;

    static void Main(string[] args)
    {
      int gap = 0;
      int last = 0;
      int count = 0;
      Stopwatch timer = new Stopwatch();

      timer.Start();
      int mag = 1;
      for (int i = 1; i < 10; i++)
      {
        foreach (int x in Step(1, mag))
        {
          gap = Math.Max(gap, x - last);
          last = x;
          count++;
        }

        mag *= 10;
      }
      timer.Stop();
      Console.WriteLine("Count: {0}", count);
      Console.WriteLine("Gap: {0}", gap);
      Console.WriteLine("Time: {0}", timer.Elapsed);
      Console.ReadKey();
    }

    static IEnumerable<int> Step(int start, int mag)
    {
      for (int i = start; i < 10; i++)
      {
        if (used[i] == false)
        {
          if (mag == 1)
          {
            yield return value + i;
          }
          else
          {
            used[i] = true;
            value += mag * i;

            foreach (int x in Step(0, mag / 10))
            {
              yield return x;
            }

            used[i] = false;
            value -= mag * i;
          }
        }
      }
    }
  }
}

Giving the following output (for 1 - MaxIn, as compared to 1-10,000 in the original challenge)

Count: 5611770
Gap: 10469135
Time: 00:00:02.8350765