Facebook Hacker Cup Subround 1B - Slot Machine Hacker

Question

Source: Facebook Hacker Cup.

I've tried generating a few lists of return values from the function below but can't seem to find what makes it possible to predict future random numbers. How would I go about solving a problem like this one?

Slot Machine Hacker

You recently befriended a guy who writes software for slot machines. After hanging out with him a bit, you notice that he has a penchant for showing off his knowledge of how the slot machines work. Eventually you get him to describe for you in precise detail the algorithm used on a particular brand of machine. The algorithm is as follows:

int getRandomNumber() {
  secret = (secret * 5402147 + 54321) % 10000001;
  return secret % 1000;
}

This function returns an integer number in [0, 999]; each digit represents one of ten symbols that appear on a wheel during a particular machine state.secret is initially set to some nonnegative value unknown to you.

By observing the operation of a machine long enough, you can determine value of secret and thus predict future outcomes. Knowing future outcomes you would be able to bet in a smart way and win lots of money.

Input The first line of the input contains positive number T, the number of test cases. This is followed by T test cases. Each test case consists of a positive integer N, the number of observations you make. Next N tokens are integers from 0 to 999 describing your observations. Output For each test case, output the next 10 values that would be displayed by the machine separated by whitespace. If the sequence you observed cannot be produced by the machine your friend described to you, print “Wrong machine” instead. If you cannot uniquely determine the next 10 values, print “Not enough observations” instead.

Constraints T = 20 1 ≤ N ≤ 100 Tokens in the input are no more than 3 characters long and contain only digits 0-9.

sample input

5
1 968
3 767 308 284
5 78 880 53 698 235
7 23 786 292 615 259 635 540
9 862 452 303 558 767 105 911 846 462

sample output

Not enough observations
577 428 402 291 252 544 735 545 771 34
762 18 98 703 456 676 621 291 488 332
38 802 434 531 725 594 86 921 607 35
Wrong machine

Answer 1

Got it!

Here is my solution in Python:

a = 5402147
b = 54321
n = 10000001

def psi(x):
    return (a * x + b) % n

inverse1000 = 9990001
max_k = (n-1) / 1000 + 1

def first_input(y):
    global last_input, i, possible_k
    last_input = y
    possible_k = [set(range(max_k))]
    i = 0

def add_input(y):
    global last_input, i
    c = inverse1000 * (b + a * last_input - y) % n
    sk0 = set()
    sk1 = set()
    for k0 in possible_k[i]:
        ak0 = a * k0 % n
        for k1 in range(max_k):
            if (k1 - ak0) % n == c:
                sk0.add(k0)
                sk1.add(k1)
                #print "found a solution"
    last_input = y
    possible_k[i] = possible_k[i] & sk0
    possible_k.append(sk1)
    i += 1
    if len(possible_k[i-1]) == 0 or len(possible_k[i]) == 0:
        print "Wrong machine"
        return
    if len(possible_k[i]) == 1:
        x = y + 1000 * possible_k[i].copy().pop()
        for j in range(10):
            x = psi(x)
            print x % 1000,
        print
        return
    print "Not enough observations"

It could probably be optimized (and cleaned), but since it runs in less than 30sec on my 3 years old laptop I probably won't bother making it faster...

The program doesn't accept exactly the same input as requested, here is how to use it:

>>> first_input(767)
>>> add_input(308)
Not enough observations
>>> add_input(284)
577 428 402 291 252 544 735 545 771 34

>>> first_input(78)
>>> add_input(880)
Not enough observations
>>> add_input(53)
698 235 762 18 98 703 456 676 621 291
>>> add_input(698)
235 762 18 98 703 456 676 621 291 488
>>> add_input(235)
762 18 98 703 456 676 621 291 488 332

>>> first_input(862)
>>> add_input(452)
Not enough observations
>>> add_input(303)
Wrong machine
>>> add_input(558)
Wrong machine

As you can see, usually 3 observations are enough to determine the future outcomes.

Since it's a pain to write math stuff in a text editor I took a picture of my demonstration explanation: