## Random hack

Discuss about the puzzles, but without giving the solutions please !!!

### Random hack

Who never dreamed of predicting the winning sequence in a Casino slot machine ? The goal of this puzzle is to predict the next value from a realistic pseudo random sequence of numbers. Obviously one couldn't stay in front of a slot machine for too long without attracting suspicion, so we will assume that you stay a little while in front of it to observe a sequence, then move away and come back to observe more. Consequently for each test case you are presented with a list of observed sequences and the formula to compute the next value from the current value.

The formula is based on simple boolean shift, and, or and xor operations:

`sj+1 = (sj>>1) | (^(sj & f) << (b-1))`

Where:

• sj+1 is the j+1th value in the sequence s

• sj is the jth value in the sequence s

• f is the function vector (unknown to you)

• b is the number of bits (unknown to you)

• ^ represents the xor bit reduction:

• ^v = 1 if the number of 1 in v is odd (example: ^1011 = 1)

• ^v = 0 if the number of 1 in v is even (example: ^0101 = 0)

Note that this formula is actually used in many modern digital systems, such as TV broadcasting, GPS signals, Linux, etc... For more information, read this Wikipedia article.

Posts: 333
Joined: Thu Dec 23, 2010 1:27 am

### Re: Random hack

Is it possible for first test (4 to 8 bits) to contain an error? My program passes all the other tests...

protocolocon

Posts: 8
Joined: Sat Jan 22, 2011 4:36 am

### Re: Random hack

We tested it pretty thoroughly, but there's always a chance of an error.

One way to test it for low number of bits is to try every possible value of f (that's how we tested it, for 8 bits there are at most 256 values only). If you get it to pass then there's most likely a problem in your solution.

Posts: 333
Joined: Thu Dec 23, 2010 1:27 am

### Re: Random hack

What is the limit for q?
EDIT: never mind.
Instead, now I'm having the same problem that protocolocon is having: my solution fails on the first case only.
In particular, what does the judge program output for this case:
1
1 6
7 64 32 16 8 4 2 1
256
128
90
6
2
1

I believe the intended output should be:
skip
skip
45
3
1
skip

random.johnnyh

Posts: 15
Joined: Wed Apr 20, 2011 6:04 pm

### Re: Random hack

We modified the judge program to now produce this answer:
Code: Select all
`skipskip4531skip`

This is now in accordance with your data.

Posts: 333
Joined: Thu Dec 23, 2010 1:27 am

### Re: Random hack

Shouldn't both of the current passing submissions have 1600 points since neither of us has gotten 100 raw points yet?

random.johnnyh

Posts: 15
Joined: Wed Apr 20, 2011 6:04 pm

### Re: Random hack

You are absolutely right, the scores are now correct.

Posts: 333
Joined: Thu Dec 23, 2010 1:27 am

### Re: Random hack

Now I am a little confused. My program gives for the example, that random.johnny gives the solution as originally given by the judge program. Now my answer is wrong? According to my code there are a lot possible f, b combinations, but for all numbers apart from 1 they give one output number, so why the skips. Am I missing something?

ploffie

Posts: 2
Joined: Mon Jan 17, 2011 2:18 am

### Re: Random hack

Explanation of skip, let's use a variation of the test case from random.johnnyh
Code: Select all
`11 27 64 32 16 8 4 2 1126128`

The answer should be
Code: Select all
`63skip`

The reason is that the sequence 64->32->...->1 proves that the bits f[i]=0 for i=1,..,6
However the bits f[0] and f[7] are unknown, they can be either 0 or 1.
So f can any of these values 00000000, 00000001, 10000000 or 10000001.

Trying each possible value of f to predict the next value of 126, we get:
Code: Select all
`(01111110 >> 1) | (^(01111110 & 00000000)<<7) = 00111111 = 63(01111110 >> 1) | (^(01111110 & 00000001)<<7) = 00111111 = 63(01111110 >> 1) | (^(01111110 & 10000000)<<7) = 00111111 = 63(01111110 >> 1) | (^(01111110 & 10000001)<<7) = 00111111 = 63`
Since all values agree the next value is 63.

Now for 128, we do the same
Code: Select all
`(10000000 >> 1) | (^(10000000 & 00000000) << 7) = 01000000 = 64(10000000 >> 1) | (^(10000000 & 00000001) << 7) = 01000000 = 64(10000000 >> 1) | (^(10000000 & 10000000) << 7) = 11000000 = 192(10000000 >> 1) | (^(10000000 & 10000001) << 7) = 11000000 = 192`
Since not all values agrees, we cannot predict the next one with certainty, consequently we get skip.

Posts: 333
Joined: Thu Dec 23, 2010 1:27 am

### Re: Random hack

I have the same problem that protocolocon and random.johnnyh had few days ago: I pass (with 0.01 time) all tests except the first one . I also have passed the examples that you propose in this thread. Any ideas? Could you provide me a more extensive test example with 4-8 bits?
Thanks a lot.
Regards.
Moises.

Moises Lopez

Posts: 5
Joined: Fri Jul 01, 2011 11:50 pm

Next