selfdescribednumber.cs

using System;

namespace SelfDescribeMe
{
    class Program
    {
        static void Main()
        {
            var random = new Random(); // Random number generator

            var b = 10; // Base
            var number = new int[b]; // The number currently being testes
            int[] counts; // The counts of the digits

            // Fill the number with random digits
            for (int cipher = 0; cipher < number.Length; cipher++)
            {
                number[cipher] = random.Next(b);
            }

            // Measure the distance to correct counts of the number - this is an admisible heuristic
            var distance = Distance(number, out counts);

            // While the measured distance is more than 0 - we are not there yet

            while (distance > 0)
            {
                // Pick what cipher of the number to modify this iteration
                var cipher = random.Next(b);
                // Read the value to be replaced
                var replaced = number[cipher];
                // See if it is equal to the correct count, lesser or greater than it.
                var direction = counts[cipher].CompareTo(replaced);
                // If it is equal, go back to pick another.
                if (direction == 0)
                {
                    continue;
                }

                // Decide the bounds for the replacement value
                int min;
                int max;
                if (direction > 0)
                {
                    min = replaced + 1;
                    max = counts[cipher] + 1;
                }
                else
                {
                    min = counts[cipher];
                    max = replaced;
                }
                if (min == b && b > 0)
                {
                    min = b - 1;
                }
                if (max > b)
                {
                    max = b;
                }

                // Pick the replacement by random
                var replacement = random.Next(min, max);

                // Replace the cipher
                number[cipher] = replacement;

                // Measure the distance after the change
                distance = Distance(number, out counts);
                
                // show the number
                foreach (var digit in number)
                {
                    // We are writing in base 16
                    Console.Write("{0:X}", digit);
                }
                Console.WriteLine();
            }
            // We have found a number that has a distance of 0
            // We are done.
            Console.WriteLine("Done");
            Console.ReadKey();
        }

        private static int Distance(int[] number, out int[] counts)
        {
            counts = new int[number.Length];
            for (int cipher = 0; cipher < number.Length; cipher++)
            {
                counts[number[cipher]]++;
            }
            var result = 0;
            for (int cipher = 0; cipher < number.Length; cipher++)
            {
                result += Math.Abs(number[cipher] - counts[cipher]);
            }
            return result;
        }
    }
}