Introduction

For this challenge we are given a game for which we must write two players, Alice and Bob. Alice is given an integer $k$ between $0$ and $255$ and a $256$ element array $xs$ of booleans. Alice then chooses one of these booleans $i$ to flip. Bob is then given the array $xs$ with the $i$th boolean flipped and must determine the integer $k$ originally given to Alice.

The algorithm

The intuition for our approach is to associate with every element of $xs$ its index $j$ and then let Bob return the xor sum $t$ of the indexes $j$ for which $xs$ is $True$.

$$t = \bigoplus_{j \textrm{ for which } xs[j] = True} j$$

This allows alice to ensure that this gives the correct value simply by calculating $t$ for the original $xs$ and then requesting that $i = t \oplus k$ is flipped. The python code for Alice and Bob is then essentially:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def alice(xs, k):
    t = k
    for j, x in enumerate(xs):
        if x:
            t ^= j
    return t

def bob(xs):
    t = 0
    for j, x in enumerate(xs):
        if x:
            t ^= j
    return t

Limits

The challenge here is that we cannot simply give a python function as the solution, but must deliver python bytecode which is inserted into functions of the form:

1
2
3
4
5

def alice(xs, k):
    ...

def bob(xs):
    ...

This limits the amount of scratch space we have available. Alice has two variables (the parameters) available while Bob only has one. Additionally both functions only have a single spot available on the their stacks, at least according to spec. By experimentation we determined that Alice was able to use 3 stack spots without crashing while Bob could use just 2. Also the bytecode must be for Python 3.9 as this was what the challenge was running.

Bytecode

Generally our bytecode mimics the Python code presented above. In an attempt to save stack and variable space all of our state is packed into a tuple $(t, j, xs)$ which is then stored in the variable slot where $xs$ was passed to the function.

Alice

1
2
3
4
5
6
7

LOAD_FAST 1
DUP_TOP
DUP_TOP
BINARY_XOR
LOAD_FAST 0
BUILD_TUPLE 3
STORE_FAST 0

This initial part loads in $k$, creates a $0$, and loads $xs$, packages these as the tuple $(t, j, xs)$ and stores it back to variable slot $0$,

 8
 9
10
11
12

LOAD_FAST 0
UNPACK_EX 0x0200
POP_TOP
BINARY_SUBSCR
POP_JUMP_IF_FALSE 52

This section unpacks our tuple on to the stack and drops $t$ as it is unneeded. Then we retrieve $xs[j]$ and if $False$ we skip the next section.

13
14
15
16
17
18
19
20
21
22
23
24
25

LOAD_FAST 0
UNPACK_SEQUENCE 3
ROT_THREE
BUILD_TUPLE 2
STORE_FAST 0
LOAD_FAST 0
UNPACK_SEQUENCE 2
POP_TOP
BINARY_XOR
LOAD_FAST 0
UNPACK_SEQUENCE 2
BUILD_TUPLE 3
STORE_FAST 0

This section pulls out $t$ and $j$ from our tuple $(t, j, xs)$ and stores back $(t \oplus j, j, xs)$.

26
27
28
29
30
31
32
33
34
35
36
37

LOAD_FAST 0
UNPACK_SEQUENCE 3
ROT_THREE
ROT_THREE
BUILD_TUPLE 2
STORE_FAST 0
DUP_TOP
DUP_TOP
BINARY_XOR
UNARY_INVERT
UNARY_NEGATIVE
BINARY_ADD

This section pulls out $j$ and calculates $j + 1$. It also stores back the reduced tuple $(t, xs)$.

38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

DUP_TOP
DUP_TOP
BINARY_XOR
UNARY_INVERT
UNARY_NEGATIVE
DUP_TOP
BINARY_ADD
DUP_TOP
BINARY_MULTIPLY
DUP_TOP
BINARY_MULTIPLY
DUP_TOP
BINARY_MULTIPLY
ROT_TWO
DUP_TOP
ROT_THREE
BINARY_SUBTRACT
POP_JUMP_IF_FALSE 124

Now we compare $j + 1$ to $256$ and if these are equal we jump to the final block.

56
57
58
59
60
61

LOAD_FAST 0
UNPACK_SEQUENCE 2
ROT_THREE
BUILD_TUPLE 3
STORE_FAST 0
JUMP_ABSOLUTE 14

This section loads the reduced tuple $(t, xs)$ and combines it with $i + 1$ and stores it back as $(t, i + 1, xs)$. It then jumps back to the second block to start over.

62
63
64
65
66
67

POP_TOP
LOAD_FAST 0
UNPACK_SEQUENCE 2
ROT_TWO
POP_TOP
RETURN_VALUE

This block essentially cleans the stack and loads the reduced tuple $(t, xs)$ to return $t$.

This implementation uses just one variable slot and three stack slots which is appropriate for Alice.

Bob

For Bob we would like to reuse as much as possible of Alice’s code, however we only have two stack slots as opposed to the three used by Alice. However it turns out that the variable slots are located just below the stack, so if we can move our variable out of the way, we essentially have a stack slot $-1$. This gives us the necessary stack slots.

Luckily (for us) STORE_FAST does not really do any bounds checking on the slot number given allowing us to put variables in arbitrary locations. We found that values around $0\mathrm{x}8000$ would often not crash the Python interpreter. In particular $0\mathrm{x}7\mathrm{ffe}$ was used successfully on the challenge setup.

1

STORE_FAST 0x7ffe

This is essentially the magic. At this point the stack is empty so our top-of-stack is actually our parameter $xs$. This is moved out of the way and letting us use an extra stack slot.

 2
 3
 4
 5
 6
 7
 8
 9
10

LOAD_FAST 0x7ffe
DUP_TOP
CONTAINS_OP
DUP_TOP
BINARY_ADD
DUP_TOP
LOAD_FAST 0x7ffe
BUILD_TUPLE 3
STORE_FAST 0x7ffe

Initialization of our tuple here is slightly different from Alice as we need to generate zeroes without having access to any numbers. Instead we ask whether $xs$ contains $xs$, which is of course $False$ and it turns out that $False + False = 0$. So we can initialize $t$ and $j$ to $0$ and create our tuple $(t, j, xs)$. The next long block is equivalent to Alice.

11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

LOAD_FAST 0x7ffe
UNPACK_EX 0x0200
POP_TOP
BINARY_SUBSCR
POP_JUMP_IF_FALSE 78
LOAD_FAST 0x7ffe
UNPACK_SEQUENCE 3
ROT_THREE
BUILD_TUPLE 2
STORE_FAST 0x7ffe
LOAD_FAST 0x7ffe
UNPACK_SEQUENCE 2
POP_TOP
BINARY_XOR
LOAD_FAST 0x7ffe
UNPACK_SEQUENCE 2
BUILD_TUPLE 3
STORE_FAST 0x7ffe
LOAD_FAST 0x7ffe
UNPACK_SEQUENCE 3
ROT_THREE
ROT_THREE
BUILD_TUPLE 2
STORE_FAST 0x7ffe
DUP_TOP
DUP_TOP
BINARY_XOR
UNARY_INVERT
UNARY_NEGATIVE
BINARY_ADD
DUP_TOP
DUP_TOP
BINARY_XOR
UNARY_INVERT
UNARY_NEGATIVE
DUP_TOP
BINARY_ADD
DUP_TOP
BINARY_MULTIPLY
DUP_TOP
BINARY_MULTIPLY
DUP_TOP
BINARY_MULTIPLY
ROT_TWO
DUP_TOP
ROT_THREE
BINARY_SUBTRACT
POP_JUMP_IF_FALSE 158
LOAD_FAST 0x7ffe
UNPACK_SEQUENCE 2
ROT_THREE
BUILD_TUPLE 3
STORE_FAST 0x7ffe
JUMP_ABSOLUTE 28

Finally at the very end we have some slightly different clean-up code as we wish to leave $xs$ behind in the variable slot, or stack slot $-1$, just as we found.

65
66
67
68

POP_TOP
LOAD_FAST 0x7ffe
UNPACK_SEQUENCE 2
RETURN_VALUE

And thus is how we solved this challenge.