You are hereProgramming Problems / 2009 Programming Solutions

2009 Programming Solutions


By gconway - Posted on 17 April 2012

Table of contents 

Fibonacci

In C++:


#include <iostream>
using namespace std;

int main(void)
{
    int fib[42];
    fib[0]=0;
    fib[1]=1;                     //Set-up
    int input=0;
    int next=0;
    int sum=0;

    cin>>input;

    for(int i=1; i!=input+1; i++)
    {
        next = fib[i] + fib[i-1];   //Create the fibonnacci series
        fib[i+1] = next;
    }
    sum = fib[input+1]-1;

    cout<<sum;                     //Print the result

}

 

Blocks

Most people solved this by storing all the blocks and then comparing each pair of blocks to see if they summed to 1,000. This has complexity O(N^2). It would be very slow if you had to read in a million block sizes.

The solution below works in linear time, O(N). It does not store the block sizes, it just has an array of size 1000, indicating which blocks have already come up. So if we get a block of size 450, it's easy to check for a block of size 550.

 

int main(void) {
    int i, n;
    int bsize;
    int best = -1;
    int isused[1000];

// setup

    for (i=0 ; i<1000; i++)
        isused[i] = 0; // block size "i" has not been found

printf("How many blocks? :");

    scanf("%d", &n);

for (i=0 ; i<n ; i++) {

        printf("Enter block %d:", i+1);
        scanf("%d", &bsize);

if ((bsize >= 1) && (bsize <= 999)) {

            if (isused[1000-bsize] == 1) {
                solution = (bsize <= 500)?bsize:(1000-bsize);
                if (solution > best)
                    best = solution;
            }
            isused[bsize] = 1; // we have this size block
        }
    }

printf("Solution: size %d & size %d\n", best, 1000-best);

return 0;

}

 

Randomness

So...given a sequence of 1,000,000 non-negative integers, with each number smaller than 256, how do we determine how random the sequence is?

So the first question is: what exactly is randomness?

Wikipedia says "Randomness is a lack of order, purpose, cause, or predictability"

Let's take the first clause: "a lack of order".

That would suggest that:

4,3,5,4,4,3,1,2,1,4,2,5,3,3,2,1,2,1,1,5,5,2,4,1,3

is more random (less ordered) than:

1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5

 

That seems to agree with our intuition.
So if we can measure "order" (some kind of pattern) then we can determine how random or non-random a sequence is.

 

However, as many people pointed out in their submissions, there are a huge (possibly infinite) number of "patterns" .... digits of pi, increasing/decreasing sequences, fibonacci sequence numbers, etc.

So let's look at another clause in the definition.

"Randomness is a lack of ... predictability"

So, the more difficult it is to predict the next element in the sequence, the more random it is. This seems like a good place to start. If we can write a computer program that can often "predict" the next number in the sequence, then the sequence is less random.

Let's look at some very basic predictors

(1) Just guess a number between 0 and 255
On average it will get 1 right out of every 256 guesses (0.39% right)

(2) Look at the frequencies of the numbers: f(i)
Pick number i with probability f(i) / (f(0)+f(1)+...+f(255))

Let's take an example sequence, and see how well it would guess:

SEQ A: 1,2,3,2,1,2,3,2,1,2,3,2,1,2,3,2,1,2,3,2,???

f = {0, 5, 10, 5}

So it will pick 1 with probability 5/20 = 1/4
So it will pick 2 with probability 10/20 = 1/2
So it will pick 3 with probability 5/20 = 1/4

(on average it would get 25% right)

(3) Method 3 is to look at the last digit in the sequence ("2" in this case)
See what digits followed it when it occurred previously in the sequence.
Well, when 2 occurred previously, it was followed by 3 five times,
and followed by 1 four times.

So it wi ll pick 1 with probability 4 / (5+4) = 4/9
So it will pick 3 with probability 5 / (5+4) = 5/9

(on average it would get 44.4% right)

 

So building a good predictor is a good way to measure randomness. Randomness = a low percentage of correct guesses.

 

Some submissions suggested (as well as counting number frequencies) counting the frequencies of pairs of numbers. This would be a good way to detect repeating sequences like this:

SEQ B:
1,2,3,4,....250,251,252,253,254,255, 1,2,3,4,5,...,255,1,2,3,...

Since the pair (1,2) occurs a lot, but (1,6) never occurs (also making it quite predictable using predictor method 3)

 

--- One final note. Sequences of numbers contain information. If we can often predict the sequence, then there is less information present and the information can be expressed by a shorter sequence. This is essentially what data compression does (software such as: WinZip, 7-zip, PKZip, etc).

 

So an easy way to measure randomness is to try to compress the data. If it shrinks to a small size, then it contained patterns, or easily predictable parts, and therefore is not very random. One way to express this is:

Randomness = compressed_size / original_size

Further reading:
http://en.wikipedia.org/wiki/Randomness_tests
http://en.wikipedia.org/wiki/Kolmogorov_complexity