permutation promenade

approach

the programs are a list of 16 letters, and each dance move is a match on its first character: s rotates the list, x swaps two positions, p swaps two letters by finding their indices.

part 1 runs the dance once. part 2 needs a billion dances, so it runs the dance repeatedly and records each resulting order until one repeats. it then starts over, plays out the lead-in before the cycle, reduces what's left of the billion modulo the cycle length, and plays only that remainder.

the trick

the dance is a permutation, so the order cycles; find the cycle and skip all but the remainder.

# k steps remaining
k = k % (i - s[res])
for _ in range(k):
   steps(l, instructions)
return "".join(l)