Skip to content

Files

Latest commit

 

History

History
43 lines (32 loc) · 1.49 KB

day25.md

File metadata and controls

43 lines (32 loc) · 1.49 KB

Merry Christmas everyone, it's December 25th :D

The Christmas Problem is usually supposed to be a quick and concise one, since Eric wants people to spend the holiday with their family. This one is a bit obscured in the jargon, but once you sort through it, the solution ends up being pretty tidy :)

In the end you are exponentiating the number 7 by a given number of times (the loop count) to get the number you see. So you're solving 7^x = <your number>...so that's basically a logarithm!

The arithmoi library (which I previously used in problems like Day 13) offers a nice discrete logarithm function, so that's really all we need to use:

type Magic = 20201227

magicGroup :: CyclicGroup Integer Magic
Just magicGroup = cyclicGroup

primBase :: PrimitiveRoot Magic
Just primBase = isPrimitiveRoot magicGroup 7

findSecret :: Mod Magic -> Maybe Natural
findSecret = fmap (discreteLogarithm magicGroup primBase)
           . isMultElement

And so our final solution is just (after converting the input numbers to the Mod Magic data type)...

day25 :: Mod Magic -> Mod Magic -> Maybe Integer
day52 x y = do
    secret <- findSecret x
    pure . getVal $ y ^% secret         -- exponentiate by the loop count

Merry Christmas to everyone, and happy New Years too. Thank you for reading these reflections, and I hope they have been helpful in some way :) Special thanks to Eric Wastl too for such a great event as always. Until next year!