Facebook Hacker Cup Subround 1B - Slot Machine Hacker

Sour开发者_开发百科ce: 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

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:

secret is always between 0 and 10,000,000 inclusive due to the mod by 10,000,001. The observed values are always the last 3 digits of secret (with leading zeros stripped) due to the mod by 1,000. So it's the other digits that are unknown and that only leaves us with 10,001 numbers to iterate over.

For each prefix in 0..10,000, we start with secret being constructed from the digits of prefix followed by the first number in the observed sequence with leading zeros. If the list of generated numbers equals the observed list, we have a potential seed. If we end with no potential seeds, we know this must be a wrong machine. If we end with more than one, we don't have enough observations. Otherwise, we generate the next 10 values using the single seed.

This runs in O(10,000NT), which is O(20,000,000) for the constraints given. Here's an extract from my solution in C++ (excuse the heavy use of macros, I only ever use them in competitions):

int N;
cin >> N;
int n[N];
REP(i, N)
  cin >> n[i];
ll poss = 0, seed = -1;
FOR(prefix, 0, 10001) {
  ll num = prefix * 1000 + n[0];
  bool ok = true;
  FOR(i, 1, N) {
    ll next = getRandomNumber(num);
    if (next != n[i]) {
      ok = false;
      break;
    }
  }
  if (ok) {
    poss++;
    seed = prefix * 1000 + n[0];
  }
}
if (poss == 0) {
  cout << "Wrong machine" << endl;
} else if (poss > 1) {
  cout << "Not enough observations" << endl;
} else {
  ll num = seed;
  FOR(i, 1, N)
    getRandomNumber(num);
  REP(i, 10)
    cout << getRandomNumber(num) << " ";
  cout << endl;
}

What is known here? The formula for updating the secret, and the list of observations. What is unknown? The starting secret value.

What could the starting secret be? We can limit the possible starting secret to 10,000 possible values, since the observed value is secret % 1000, and the maximum secret is 10,000,000.

The possible starting secrets are then

possible = [1000 * x + observed for x in xrange(10001)]

Only a subset (if any) of those secrets will update to a value that will show the next observed value.

def f(secret):
    return (secret * 5402147 + 54321) % 10000001

# obs is the second observation.
new_possible = [f(x) for x in possible]
new_possible = [x for x in new_possible if x % 1000 == obs]

Even if every possible value was still in new_possible, we would only be checking 10,000 numbers for every observation. But, it is not likely that many values will match over multiple observations.

Just keep iterating that process, and either the possible list will be empty, longer than one, or it will have exactly one answer.

Here is a function to put it all together. (you need the f from above)

def go(observations):
    if not observations:
        return "not enough observations"

    # possible is the set of all possible secret states.
    possible = [x * 1000 + observations[0] for x in xrange(10001)]

    # for each observation after the first, cull the list of possible
    # secret states.
    for obs in observations[1:]:
        possible = [f(x) for x in possible]
        possible = [x for x in possible if x % 1000 == obs]
        # uncomment to see the possible states as the function works 
        # print possible

    # Either there is 0, 1, or many possible states at the end.
    if not possible:
        return "wrong machine"
    if len(possible) > 1:
        return "not enough observations"

    secret = possible[0]
    nums = []
    for k in xrange(10):
        secret = f(secret)
        nums.append(str(secret % 1000))
    return " ".join(nums)

import sys

def main():
    num_cases = int(sys.stdin.readline())

    for k in xrange(num_cases):
        line = [int(x) for x in sys.stdin.readline().split()]
        print go(line[1:])

main()