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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
{-
Copyright (C) 2017 Yuchen Pei.
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU Affero General Public License as
published by the Free Software Foundation, either version 3 of the
License, or (at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU Affero General Public
License along with this program. If not, see
<https://www.gnu.org/licenses/>.
-}
{-# 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
|
