Rich Newman

Attempted Solutions to Random Numbers Problem

using System;
using System.Collections.Generic;

namespace RandomNumber5To7
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] results = new int[7];
            for (int i = 0; i < 100; i++)
            {
                // Change to call RandomNumber1To7Old for a different algorithm
                int result = RandomNumber1To7();
                results[result - 1]++;

                Console.WriteLine(result);
            }

            Console.WriteLine("==============================================");
            foreach (int count in results)
            {
                Console.WriteLine(count);
            }

            Console.ReadLine();
        }

	    // This method is based on the theory that if we 'roll the five-sided dice'
	    // five times, we can treat roll 1 as having values in range 1-5, roll 2 as having values
	    // in the range 6-10 and so on.  We can then decide which of the five 'rolls' we're going 
	    // to use with another roll of the dice, so we're actually picking a number between 1-125
	    // at random.  We can increase this in powers of 5 by then 'rolling' our new 125-sided
	    // dice 5 times, treating the first roll as 1-125, the second as 126-250 etc.  This will
	    // give us a random number in the range 1-625.  We can then do the same thing with 5 625-sided
	    // dice, giving us 3125 and so on.  
	    // Clearly, these are all powers of 5 (5^3 = 125, 5^4=625, 5^5=3125)
	    // To give an exact value in the range 1-7 we need to be able to divide the final range
	    // (1-625 or 1-3125) by 7 to give us 7 equal ranges with a equal possiblities of our random
	    // value falling in each.  Unfortunately this isn't possible because we need integral x and y
	    // such that 5^x = 7 * y, which has no solution.
	    // But we can use this method to randomize to an arbitrary level of accuracy.  
	    // Say we choose '3' as our 'level', so we generate random numbers between 1 and 5^3=125.
	    // Actually the maths is easier if we treat this as 0 to 124 by subtracting 1.
	    // We can then divide into buckets 0 to less than int(125/7), int(125/7) to less than int(2 * 125/7), 
	    // int(2 * 125/7) to less than int(3 * 125/7)
	    // and so on up to int(6 * 125/7) to less than int(7 * 125/7)=125
	    // We can treat the first bucket as '1', the second as 2, up to 7, and get a 'random'
	    // number 1-7.  We can make this as accurate as we like by increasing the original level.
        static int RandomNumber1To7()
        {
            // Set our level. E.g. level 3 corresponds to randomizing 1-125 as above
            int level = 5;
            // Calculate 5 ^ level, the upper bound of the randomization (e.g. 5 ^ 3 = 125 = maxValue)
            int maxValue = (int)Math.Pow(5.0, (double)(level));
            // Genearate a random number Range 0 to maxValue - 1
            int randomValueLessThenMaxValue = CalculateRandomSpread(level) - 1;
            double seventh = maxValue / 7.0;
            // Easiest is to think of this in terms of the example above: if our random
            // value is greater than or equal to int(6 * 125/7) then it's a 7, if greater than or equal to int(5 * 125/7)
            // but less than int(6 * 125/7) it's a 6 and so on.  This is the same as saying the value
            // divided by 125/7 is a 7 if it's greater than or equal to 6, is a 6 if greater than or equal to 5 but less than 6
            // and so on.
            // So if we divide it by 125/7 and apply the 'floor' function and add 1.
            int result = (int)Math.Floor(randomValueLessThenMaxValue / seventh) + 1;
            if (result > 7) System.Diagnostics.Debug.Assert(false);
            return result;
        }

        static int CalculateRandomSpread(int level)
        {
            // Roll a dice at the lowest level
            int total = RandomNumber1To5();
            for (int i = 1; i < leveli++)
            {
            	// Assign that roll to one of 5 buckets based on another random roll
                int random = RandomNumber1To5();
                // Calculate what that means in terms of the value: if level is 2
                // we call this with i=1 only, so multiply our new random number by 5
                // giving us one of 0, 5, 10, 15, 20.  We then add original number to
                // this (it's in range 1-5), giving us 1-25 as our range overall.
                total += (int)Math.Pow(5.0, (double)i) * (random - 1);
            }
            return total;

        }

	    // Accurate, but can take infinite time
	    // Put seven results in a list (values 1-7).  Roll one five-sided dice for each
	    // value in the list (so seven times).  Work out the highest value
	    // rolled and put all the values in the original list for which this number was
	    // rolled into a new, hopefully shorter, list.  Repeat the process for the shorter list
	    // until you get down to just one value.
        static int RandomNumber1To7Old()
        {
            List<intmaxResults = new List<int>();
            int[] values = {1,2,3,4,5,6,7};
            maxResults.AddRange(values);
            do
            {
                maxResults = PickValuesFromList(maxResults);
            } while (maxResults.Count > 1);
            return maxResults[0];

        }

        static List<intPickValuesFromList(List<intresults)
        {
            List<intmaxResults = new List<int>();
            int highestValue = 0;
            for (int counter = 0; counter < results.Countcounter++)
            {
                int thisResult = RandomNumber1To5();
                if (thisResult == highestValue)
                    maxResults.Add(results[counter]);
                else if (thisResult > highestValue)
                {
                    maxResults = new List<int>();
                    maxResults.Add(results[counter]);
                    highestValue = thisResult;
                }
            }
            return maxResults;
        }

        static int RandomNumber1To5()
        {
            System.Threading.Thread.Sleep(100);
            return new Random().Next(1, 6); 
        }
    }
}

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

The Shocking Blue Green Theme Blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

Join 80 other followers

%d bloggers like this: