Simeon Pilgrim

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