crab cups

approach

the cups are a circular singly linked list of Node objects, plus a dictionary from each label to its node. each move cuts out the three cups after the current one, picks the destination label by counting down (wrapping around and skipping the picked-up cups), finds that node through the dictionary in O(1), and splices the three cups back in after it.

part 1 plays 100 moves on the nine cups and reads the labels after cup 1. part 2 extends the circle to a million cups and plays ten million moves with the same play; because every step is constant time, only the size changes. it returns the two labels right after cup 1, leaving the final multiplication to the caller.

the trick

a linked list for the circle plus a label-to-node map makes every move constant time, which is what makes ten million moves feasible.

def play(current, nodes, rounds, largest = 9):
    for i in range(rounds):
        pick, pnodes = remove_k_nodes(current, 3)
        target = choose_target(current.val, pnodes, largest)
        append_after(nodes[target], pick)
        current = current.next
    return current