Slot Machine Hacker

Question

Problem: Slot Machine Hacker from Facebook Hacker Cup 2011 Round 1B

Goal: Shortest code in your favourite language using stdin/stdout. You cannot assume getRandomNumber is defined, i.e. your solution has to include a potentially golfed version as a function or in some other way.

Reference solution: on SO [I chose mine, because it uses stdin/stdout and I'm unsure about dave's solution.]

Problem text follows:

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.

Example 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 

Example 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

Python, 293 chars

import sys
n=1e7+1
for s in[map(int,x.split())for x in sys.stdin][1:]:
 Q=[]
 for i in range(s[1],n,1e3):A=[i];R=[A.append((A[-1]*5402147+54321)%n)or A[-1]%1e3for x in[0]*8+s];Q+=[R[-10:]]*(R[:-10]==s[2:])
 print Q and["%d "*10%tuple(Q[0]),"Not enough observations"][len(Q)>1]or"Wrong Machine"

Answer 2

Python, 316 characters

C=10**7+1
G=lambda:(s*5402147+54321)%C
import sys
I=map(int,sys.stdin.read().split())[1:]
while I:
 n=I[0]+1;S=range(C)
 for x in I[1:n]:S=[G()for s in S if s%1000==x]
 if len(S)-1:V="Not enough observations"if S else"Wrong machine"
 else:
  s=S[0];V=""
  for i in range(10):V+="%d "%(s%1000);s=G()
 print V;I=I[n:]