advent25/src/advent25.hs

   1 -- import Debug.Trace
   2
   3 -- import Math.NumberTheory.Moduli.DiscreteLogarithm
   4 -- import Data.Finite (Finite, modulo, getFinite)
   5 -- import GHC.TypeNats (KnownNat)
   6 -- import Data.Maybe
   7
   8 import Data.Semigroup
   9
  10 newtype MExp = MExp Integer
  11   deriving (Show, Eq)
  12
  13 instance Semigroup MExp where
  14   (MExp a) <> (MExp b) = MExp $ (a * b) `mod` modularBase
  15
  16
  17 subject :: MExp
  18 subject = MExp 7
  19
  20 modularBase :: Integer
  21 modularBase = 20201227
  22
  23 main :: IO ()
  24 main =
  25     do text <- readFile "data/advent25.txt"
  26        let [cardKey, doorKey] = map read $ lines text
  27        print $ part1 cardKey doorKey
  28
  29 part1 cardKey doorKey = publicKey
  30   where cardRounds = findRounds cardKey
  31         MExp publicKey = stimes cardRounds (MExp doorKey)
  32
  33 findRounds :: Integer -> Integer
  34 findRounds target = fst $ until (foundRounds t) countingExponential (0, seed)
  35   where t = MExp target
  36         seed = MExp 1
  37
  38 foundRounds :: MExp -> (Integer, MExp) -> Bool
  39 foundRounds target (_n, v) = v == target
  40
  41 countingExponential :: (Integer, MExp) -> (Integer, MExp)
  42 countingExponential (n, v) = (n + 1, v <> subject)
  43