# JSGame
File is at `pref-max--game.html`. Solution is at `a.py`.
While you can solve this mathematically (I kind of did that by noticing thatyou can increase the number, read counter-clockwise, until 2222 and thenreducing them to 0000), I am going to propose an alternate solution.
Basically, model this game as a graph, where the nodes are the states of the gameand the edges connect two nodes if you can bring a state to the other by aplayer move (and possibly a number of computer moves). Once you have done this,you can run the breadth-first search algorithm and traverse through the statespace.
We start by defining the constants, as well as what a state is:```pythonn = 4k = 2
State = namedtuple("State", ["clock", "is_player_turn"])```
Here, `clock` is a tuple of `n` elements which represents the numbers in theclock, starting from the current clock hand, clockwise. `is_player_turn` is aboolean which is `True` if and only if it is the current player's turn.
The next few functions are copied from the implementation. In retrospect,using Javascript would have been faster as you can just use the implementationsin the HTML file itself.```pythondef shift(old_state):    new_clock = old_state.clock[1:] + (old_state.clock[0],)    return State(clock=new_clock, is_player_turn=new_clock[0] == k)
def player_zero(old_state):    zeroed_clock = (0,) + old_state.clock[1:]    return shift(State(clock=zeroed_clock, is_player_turn=old_state.is_player_turn))
def computer_increment(old_state):    incremented = (old_state.clock[0] + 1,) + old_state.clock[1:]    return shift(State(clock=incremented, is_player_turn=old_state.is_player_turn))
def is_max(s, cur_pos):    rotations = [''.join(str(x) for x in reversed(s[i:] + s[:i])) for i in range(n)]    values = [int(i, k + 1) for i in rotations]    return max(values) == values[cur_pos]
def is_last(s):    new_s = (s[0] + 1,) + s[1:]    if all(i == 0 for i in new_s):        return True
    i = 0    while new_s[(i + n - 1) % n] == 0:        i = (i + n - 1) % n
    return is_max(new_s, i)```
The hardest part is to define what the next state is after a series of computermovements:```pythondef computer_resolve(old_state):    if old_state.clock == (0,):        return State(clock=old_state.clock, is_player_turn=True)
    new_state = old_state    while not new_state.is_player_turn:        if is_last(new_state.clock):            new_state = computer_increment(new_state)        else:            new_state = State(clock=new_state.clock, is_player_turn=True)            if new_state.clock[0] == 0:                new_state = shift(new_state)
    return new_state```
The next part is just some convenience functions. `state_to_int` and`int_to_state` is useful to "pack" the state into an integer, so that it canbe hashed faster. I suppose you can actually just dump the `State` object intothe visited set later, but oh well.```pythondef state_to_int(state):    return int(''.join(str(i) for i in state.clock), k + 1)
def int_to_state(i):    x = []    for _ in range(n):        x.append(i % (k + 1))        i //= (k + 1)    return State(clock=tuple(reversed(x)), is_player_turn=True)
def state_after_zero(old_state):    return computer_resolve(player_zero(old_state))
def state_after_nothing(old_state):    return computer_resolve(shift(old_state))```
Finally, the breadth first search algorithm. The original state is whateverthat has been resolved by the computer from the initial state of `(0, 0, 0, 1)`.```pythonoriginal_state = computer_resolve(State(clock=(0, ) * (n - 1) + (1,), is_player_turn=False))
visited = set()queue = Queue()queue.put((state_to_int(original_state), ''))
while not queue.empty():    top, cmd = queue.get()    if top == 0:        print(cmd)        break
    if top in visited:        continue    visited.add(top)
    queue.put((state_to_int(state_after_zero(int_to_state(top))), cmd + '0'))    queue.put((state_to_int(state_after_nothing(int_to_state(top))), cmd + 'X'))
```
Basically, in the queue, we store the state of the game (represented as aninteger), as well as the series of commands to reach that state from thebeginning (where `X` is doing nothing and `0` is putting zero).
Running this will give `0XXX000X0XXX00XXX0XXXXX0XXX00XXX0XXXXX0XXXXX0000`which, indeed, corresponds to the shortest sequence of moves to win the game.This approach might be better if you are more inclined to programming.
As a bonus, since this code is general enough (I abstracted the `k` and `n`variable away since I am doing this after the CTF so I have plenty of time :p)we can change `n` and `k` to a big number and get the solution as well: with`k = 5` and `n = 4` the solution is```0XXX000X0XXX00XXX0XXXXX0XXX00XXX0XXXXX0XXXXX000XX0XXXXX0XXXXX00XXXXX0XXXXXXXX0XXXXXXXX0XXX00XXXXX0XXXXXXXX0XXXXXXXX0XXXXXX00XXXXX0XXXXXXXX0XXXXXXXX0XXXXXXXX000XXX0XXXXXXX0XXXXXXX0XXXXXXX00XXXXXXX0XXXXXXXXXXX0XXXXXXXXXXX0XXXXXXXXXXX0XXX00XXXXXXX0XXXXXXXXXXX0XXXXXXXXXXX0XXXXXXXXXXX0XXXXXX00XXXXXXX0XXXXXXXXXXX0XXXXXXXXXXX0XXXXXXXXXXX0XXXXXXXXX00XXXXXXX0XXXXXXXXXXX0XXXXXXXXXXX0XXXXXXXXXXX0XXXXXXXXXXX000XXXX0XXXXXXXXX0XXXXXXXXX0XXXXXXXXX0XXXXXXXXX00XXXXXXXXX0XXXXXXXXXXXXXX0XXXXXXXXXXXXXX0XXXXXXXXXXXXXX0XXXXXXXXXXXXXX0XXX00XXXXXXXXX0XXXXXXXXXXXXXX0XXXXXXXXXXXXXX0XXXXXXXXXXXXXX0XXXXXXXXXXXXXX0XXXXXX00XXXXXXXXX0XXXXXXXXXXXXXX0XXXXXXXXXXXXXX0XXXXXXXXXXXXXX0XXXXXXXXXXXXXX0XXXXXXXXX00XXXXXXXXX0XXXXXXXXXXXXXX0XXXXXXXXXXXXXX0XXXXXXXXXXXXXX0XXXXXXXXXXXXXX0XXXXXXXXXXXX00XXXXXXXXX0XXXXXXXXXXXXXX0XXXXXXXXXXXXXX0XXXXXXXXXXXXXX0XXXXXXXXXXXXXX0XXXXXXXXXXXXXX0000```
You can convince yourself that it is true :)