Random hack

[admin]

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:

• s_j+1 is the j+1^th value in the sequence s


• s_j is the j^th 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.

Go to puzzle

[protocolocon]

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

[admin]

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.

[random.johnnyh]

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

[admin]

We modified the judge program to now produce this answer:

Code: Select all

skip
skip
45
3
1
skip


This is now in accordance with your data.

[random.johnnyh]

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

[admin]

You are absolutely right, the scores are now correct.

[ploffie]

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?

[admin]

Explanation of skip, let's use a variation of the test case from random.johnnyh

Code: Select all

1
1 2
7 64 32 16 8 4 2 1
126
128

The answer should be

Code: Select all

63
skip

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.

[Moises Lopez]

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.