| Copyright | (c) Eric Mertens 2017 |
|---|---|
| License | ISC |
| Maintainer | emertens@gmail.com |
| Safe Haskell | None |
| Language | Haskell2010 |
Main
Description
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.
Synopsis
- main :: IO ()
- intToLetter :: Int -> Char
- letterToInt :: Char -> Int
- type Dance (n :: Nat) = (Dual (Permutation n), Permutation n)
- runDance :: forall (n :: Nat). KnownNat n => Dance n -> String
- spinDance :: forall (n :: Nat). KnownNat n => Int -> Dance n
- swapDance :: forall (n :: Nat). KnownNat n => Int -> Int -> Dance n
- partDance :: forall (n :: Nat). KnownNat n => Char -> Char -> Dance n
Documentation
>>>:set -XDataKinds
Print the solutions to both parts of the day 16 problem. The input file can be overridden via command-line arguments.
intToLetter :: Int -> Char Source #
Map the numbers starting at 0 to the letters starting at a.
>>>intToLetter <$> [0..3]"abcd"
letterToInt :: Char -> Int Source #
Map the letters starting at a to the numbers starting at 0.
>>>letterToInt <$> ['a'..'d'][0,1,2,3]
type Dance (n :: Nat) Source #
Arguments
| = (Dual (Permutation n), Permutation n) | renaming, permutation |
A dance is a renaming of dancers and a permutation of their positions
runDance :: forall (n :: Nat). KnownNat n => Dance n -> String Source #
Compute the final position of the dancers given a dance where dancers start in order.
>>>let example = spinDance 1 <> swapDance 3 4 <> partDance 'e' 'b' :: Dance 5>>>runDance example"baedc">>>runDance (stimes 2 example)"ceadb"
spinDance :: forall (n :: Nat). KnownNat n => Int -> Dance n Source #
The spin dance where all dancers move some number of positions to the right.
>>>runDance (spinDance 0 :: Dance 3)"abc">>>runDance (spinDance 1 :: Dance 3)"cab"