aboutsummaryrefslogtreecommitdiff
path: root/Puzzle15.hs
blob: 1a1d5964a72c965ab84a621a7f4495b305050414 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
{-# LANGUAGE BangPatterns #-}

import Data.Int

stepA :: Int -> Int
stepA !x = x * 16807 `rem` 2147483647
stepB :: Int -> Int
stepB !x = x * 48271 `rem` 2147483647

stepA' :: Int -> Int
stepA' !x = until ((==0) . flip rem 4) stepA (stepA x)

stepB' :: Int -> Int
stepB' !x = until ((==0) . flip rem 8) stepB (stepB x)

toInt16 :: Int -> Int16
toInt16 = fromIntegral

stepAB :: ((Int, Int), Int) -> ((Int, Int), Int)
stepAB ((!x, !y), !n) = ((stepA x, stepB y), if (toInt16 x) == (toInt16 y) then n + 1 else n)

stepAB' :: ((Int, Int), Int) -> ((Int, Int), Int)
stepAB' ((!x, !y), !n) = ((stepA' x, stepB' y), if (toInt16 x) == (toInt16 y) then n + 1 else n)

f :: Int -> ((Int, Int), Int) -> ((Int, Int), Int)
f 0 acc = acc
f m !acc = f (m - 1) (stepAB acc)

f' :: Int -> ((Int, Int), Int) -> ((Int, Int), Int)
f' 0 acc = acc
f' m !acc = f' (m - 1) (stepAB' acc)

solve1 :: (Int, Int) -> Int
solve1 (x, y) = snd $ f 40000000 ((x, y), 0)

solve2 :: (Int, Int) -> Int
solve2 (x, y) = snd $ f' 5000000 ((x, y), 0)

input :: (Int, Int)
input = (783, 325)

input0 = (65, 8921) :: (Int, Int)

--main = (putStrLn . show . solve1) input
main = (putStrLn . show . solve2) input