src/advent15/advent15other.hs

   1 {-# LANGUAGE BangPatterns #-}
   2 {-# OPTIONS_HADDOCK ignore-exports #-}
   3 -- module Day15 (day15a, day15b) where
   4
   5 import Control.Arrow ((***))
   6 import Data.Bits ((.&.))
   7 import Data.Function (on)
   8 import Data.List (stripPrefix)
   9 import Data.Word (Word64)
  10
  11 -- | Returns the initial values for generators A and B.
  12 parse :: String -> (Word64, Word64)
  13 parse _ =  (873, 583)
  14 -- parse input = (read a, read b) where
  15 --     [line1, line2] = lines input
  16 --     Just a = stripPrefix "Generator A starts with " line1
  17 --     Just b = stripPrefix "Generator B starts with " line2
  18
  19
  20 main :: IO ()
  21 main = do
  22     print $ day15a "none"
  23     print $ day15b "none"
  24
  25
  26 -- | One step of generator A.
  27 genA :: Word64 -> Word64
  28 genA x = x * 16807 `mod` 2147483647
  29
  30 -- | One step of generator B.
  31 genB :: Word64 -> Word64
  32 genB x = x * 48271 `mod` 2147483647
  33
  34 -- | Step generator A until a multiple of 4.
  35 genA' :: Word64 -> Word64
  36 genA' x = let y = genA x in if y .&. 3 == 0 then y else genA' y
  37
  38 -- | Step generator A until a multiple of 8.
  39 genB' :: Word64 -> Word64
  40 genB' x = let y = genB x in if y .&. 7 == 0 then y else genB' y
  41
  42 -- | One step of both generators A and B.
  43 gen :: (Word64, Word64) -> (Word64, Word64)
  44 gen = genA *** genB
  45
  46 -- | Step both generators A and B until a multiple of 4 and 8 respectively.
  47 gen' :: (Word64, Word64) -> (Word64, Word64)
  48 gen' = genA' *** genB'
  49
  50 -- | prop> count p f x n == length (filter p . take n . tail $ iterate f x)
  51 count :: (a -> Bool) -> (a -> a) -> a -> Int -> Int
  52 count p f = count' 0 where
  53     count' !k x 0 = k
  54     count' !k x n = count' (if p y then k + 1 else k) y (n - 1) where y = f x
  55
  56 day15a :: String -> Int
  57 day15a input =
  58     count (uncurry ((==) `on` (.&. 0xffff))) gen (parse input) 40000000
  59
  60 day15b :: String -> Int
  61 day15b input =
  62     count (uncurry ((==) `on` (.&. 0xffff))) gen' (parse input) 5000000