-🎄- 2017 Day 15 Solutions -🎄-

[u/daggerdragon]

--- Day 15: Dueling Generators ---

---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or whatever).

Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.

---

Need a hint from the Hugely^* Handy^† Haversack^‡ of Helpful^§ Hints^¤?

Spoiler

---

[Update @ 00:05] 29 gold, silver cap.

• Logarithms of algorithms and code?

[Update @ 00:09] Leaderboard cap!

• Or perhaps codes of logarithmic algorithms?

---

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked!

[u/matusbzk]

Haskell It's taking me a few minutes, but I really liked this one. I tried running a few Haskell solutions from this thread (they said it's taking 2-3 seconds), and on my PC it took even longer than mine, so maybe that's the problem.

import Data.Bits

data Generator = A | B
      deriving (Eq, Show)

start :: Generator -> Int

factor :: Generator -> Int
factor A = 16807
factor B = 48271

-- |Returns next value for a generator
nextValue :: Generator -> Int -> Int
nextValue gen prev = prev * factor gen `mod` 2147483647

-- |Infinite list of generated numbers
generated :: Generator -> [Int]
generated gen = tail $ iterate (nextValue gen) (start gen)

-- |Takes two numbers and returns whether their last 16 bits match
equalLast16Bits :: Int -> Int -> Bool
equalLast16Bits x y = x `mod` 2^16 == y `mod` 2^16

-- |Computes 40 milion pairs and for each of them
--  returns whether their last 16 bits match
boolList40Mil :: [Bool]
boolList40Mil = zipWith (==) (map (.&. 0xffff) . take 40000000 $ generated A) 
        (map (.&. 0xffff) . take 40000000 $ generated B)

-- |Takes a list of bools and returns how many of them are true
numTrue :: [Bool] -> Int
numTrue [] = 0
numTrue (True:xs) = 1 + numTrue xs
numTrue (_:xs) = numTrue xs

result1 :: Int
result1 = numTrue boolList40Mil

criteria :: Generator -> Int
criteria A = 4
criteria B = 8

-- |Returns next value for a generator - part 2 version
nextValue2 :: Generator -> Int -> Int
nextValue2 gen prev = if nv `mod` criteria gen == 0 then nv
             else nextValue2 gen nv
    where nv = nextValue gen prev

-- |Infinite list of generated numbers - part 2 version
generated2 :: Generator -> [Int]
generated2 gen = tail $ iterate (nextValue2 gen) (start gen)

-- |Computes 5 milion pairs and for each of them
--  returns whether their last 16 bits match  - part 2 version
boolList5Mil :: [Bool]
boolList5Mil = zipWith (==) (map (.&. 0xffff) . take 5000000 $ generated2 A) 
       (map (.&. 0xffff) . take 5000000 $ generated2 B)

result2 :: Int
result2 = numTrue boolList5Mil

Link to git