Random hack

[admin]

Generating a test case is relatively easy:
- pick b (4 to 8 bits)
- pick a f value (it's an integer between 0 and 2**b)
- pick a v0 value (it's an integer between 0 and 2**b)
- use the formula to generate some sequence
- then slice the sequence

[demo]

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.

in this case, you assume the number of bits is 8, we can't determine it as for any b>=7, if all f[i]=0, we can get the sequence, right?

[admin]

Actually there's no assumption being made about the number of bits in this example, the value b=8 was used since any bits >= 8 are always 0 in either the sequences or in the values that need to predicted and consequently have no effect on the result. But in this particular example, we don't know the value of b for sure since the xor reduction was never 1.

[_smp]

Hi,

I'm really struggling on this one. A couple of questions:
1. Do the values f = 167, b = 3 make for a valid function?
2. If yes, what should the program answer with this sequence (generated with these values):
1 2
6 112 60 30 15 7 3
22
119

[demo]

what's the upper bound of L[1]+L[2]+...+L[p]? L[i] is the length of the i-th sequence.

[admin]

Hi,

I'm really struggling on this one. A couple of questions:
1. Do the values f = 167, b = 3 make for a valid function?
2. If yes, what should the program answer with this sequence (generated with these values):
1 2
6 112 60 30 15 7 3
22
119

1 & 2: we always consider b to be sufficiently large to hold all of the bits of a value (so here 112 conflicts with b=3).

what's the upper bound of L[1]+L[2]+...+L[p]? L[i] is the length of the i-th sequence.

The sum of the sequence lengths is between b/2 and 2*b (lower/upper bounds).

[demo]

The sum of the sequence lengths is between b/2 and 2*b (lower/upper bounds).

I think the sum my exceed 150 in the "Next year slot machine" case, as my program suggests.

[admin]

Actually it's 4*b not 2*b, what we were counting was the number of transitions sum(L[i]-1) instead of the numbers of values sum(L[i]).