Module aoc::year2017::day16

Permutation Promenade

The key insight is that a complete dance can be represented by just two transformations. The spin and exchange moves compose into a single transformation and the partner swaps compose into a second independent transformation.

Each transformation can then be applied to itself to double the effect. For example a single complete dance turns into two dances, then doubles to four dances and so on.

This allows us to compute part two with a similar approach to exponentiation by squaring.

Structs

• Dance

Functions

• from_byte 🔒
• parse
  Reduces all 10,000 individual dance moves into just two independent transformations.
• part1
  Apply the transformation once.
• part2
  If a bit is set in the binary representation of 1 billion apply the current transformation, then apply the transformation to itself to double the number of complete dances.
• to_char 🔒