https://adventofcode.com/2017/day/16

Day 16 defines a language of renaming and permutations and asks us to iterate the program one billion times!

The key to this solution is that stimes can used repeated squaring to efficiently compute the result of multiplication by a large factor.

There are two kind of dance moves: permutation of positions, and renamings of dancers. These two kinds of moves commute with each other. Both renamings and permutations can efficiently compose, so we represent a dance as a single renaming and a single permutation. This representation means that our dance combination operation (<>) is associative, as required for dances to be a Monoid because the component permutations themselves support an associative composition.

$setup >>> :set -XDataKinds -XNumDecimals

>>> let steps = map danceStep (parseInput "s1,x3/4,p3/b\n")
>>> let dance = mconcat steps :: Dance 5
>>> mapM_ (putStrLn . runDance) (scanl (<>) dance steps)
baedc
cbaed
cbade
ceadb

>>> putStrLn (runDance (stimes (1e9 :: Int) dance))
abcde