grove positioning system

approach

the numbers go into a hand-written circular doubly linked list, and the original node order is saved so each number can be moved in turn. to move a node, it's unlinked and a dummy node is left in its place; the code walks k steps from the dummy and splices the node back in after (or, for negative moves, before) the target. k is reduced modulo size - 1, since the moving number isn't in the list while it moves. the custom mod truncates towards zero, so negative values stay negative and walk left.

part 1 mixes once and adds the values 1000, 2000 and 3000 steps after zero. part 2 multiplies every number by the decryption key and mixes ten times by repeating the original order ten times.

the trick

reduce each move modulo n - 1, not n: with the number lifted out, there are only n - 1 gaps to land in.

    def mix(self, order):
        for node in order:
            k = mod(node.val, self.size - 1)
            if k == 0:
                continue
            n_left, n_right = node.left, node.right
            node.remove()
            dummy = Node("__dummy__", left=n_left, right=n_right)
            target = dummy.walk(k)
            if k < 0:
                target.change_prev(node)
            else:
                target.change_next(node)