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  
Share

Comments:

Robert Fischer 2008-07-02 12:37:34

Interesting code – I’m having some trouble reading it. Where exactly are you guarantying that the numbers are made up of distinct characters?


Simeon 2008-07-02 12:41:11

The ‘used’ array tracks that. digits 0 - 9 are used or not…