add day 13

Dependencies

Change contents

• file addition: 13 (dxwrx-rx-r)
  [1.0]
• file addition: input.txt (-xw-x--x--)
  [0.5]
  + 1000052

  + 23,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,37,x,x,x,x,x,863,x,x,x,x,x,x,x,x,x,x,x,19,13,x,x,x,17,x,x,x,x,x,x,x,x,x,x,x,29,x,571,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,41
• file addition: crt.hs (-xw-x--x--)
  [0.5]
  + -- solved part 1 in the python REPL

  +

  + -- Copied from stack overflow

  + crt :: [(Integer, Integer)] -> (Integer, Integer)

  + crt = foldr go (0, 1)

  + where

  + go (r1, m1) (r2, m2) = (r `mod` m, m)

  + where

  + r = r2 + m2 * (r1 - r2) * (m2 `inv` m1)

  + m = m2 * m1

  +

  + -- Modular Inverse

  + a `inv` m = let (_, i, _) = gcd a m in i `mod` m

  +

  + -- Extended Euclidean Algorithm

  + gcd 0 b = (b, 0, 1)

  + gcd a b = (g, t - (b `div` a) * s, s)

  + where

  + (g, s, t) = gcd (b `mod` a) a

  +

  + mkPairs :: String -> [(Integer, Integer)]

  + mkPairs s =

  + let s' = map delComment s

  + nums = zip [0 ..] $ words s'

  + in nums >>= mkPair

  + where

  + delComment ',' = ' '

  + delComment x = x

  +

  + mkPair :: (Integer, String) -> [(Integer, Integer)]

  + mkPair (_, "x") = []

  + mkPair (i, n) = [(- i, read n)]

  +

  + solve2 :: String -> Integer

  + solve2 = fst . crt . mkPairs