module Common (crt, egcd, readEntire) where

import Data.Text (Text)
import qualified Data.Text as T (null)
import Data.Text.Read (Reader)

-- |Chinese remainder theorem.
--
-- prop> crt (r1, q1) (r2, q2) == (r3, q3) ==>
--           r3 `mod` q1 == r1 && q3 `mod` q1 == 0 &&
--           r3 `mod` q2 == r2 && q3 `mod` q2 == 0
crt :: (Integral a) => (a, a) -> (a, a) -> (a, a)
crt :: (a, a) -> (a, a) -> (a, a)
crt (a
r1, a
q1) (a
r2, a
q2) = (a
r3 a -> a -> a
forall a. Integral a => a -> a -> a
`mod` a
q3, a
q3) where
    q3 :: a
q3 = a -> a -> a
forall a. Integral a => a -> a -> a
lcm a
q1 a
q2
    -- r3 * q2 == r1 * q2 (mod q3)
    -- r3 * q3 == r2 * q1 (mod q3)
    -- r3 * (q1 + q2) = r1 * q2 + r2 * q1 (mod q3)
    (a
t, a
_, a
g) = a -> a -> (a, a, a)
forall a. Integral a => a -> a -> (a, a, a)
egcd (a
q1 a -> a -> a
forall a. Num a => a -> a -> a
+ a
q2) a
q3
    -- t * (q1 + q2) == g (mod q3)
    -- r3 = (r1 * q2 + r2 * q1) * t / g (mod q3)
    (a
r3, a
0) = ((a
r1 a -> a -> a
forall a. Num a => a -> a -> a
* a
q2 a -> a -> a
forall a. Num a => a -> a -> a
+ a
r2 a -> a -> a
forall a. Num a => a -> a -> a
* a
q1) a -> a -> a
forall a. Num a => a -> a -> a
* a
t) a -> a -> (a, a)
forall a. Integral a => a -> a -> (a, a)
`divMod` a
g

-- |Extended GCD.
--
-- prop> gcd a b == (s, t, g) ==> a * s + b * t == g
egcd :: (Integral a) => a -> a -> (a, a, a)
egcd :: a -> a -> (a, a, a)
egcd a
a a
0 = (a
1, a
0, a
a)
egcd a
a a
b = (a
t, a
s a -> a -> a
forall a. Num a => a -> a -> a
- a
q a -> a -> a
forall a. Num a => a -> a -> a
* a
t, a
g) where
    (a
q, a
r) = a
a a -> a -> (a, a)
forall a. Integral a => a -> a -> (a, a)
`quotRem` a
b
    (a
s, a
t, a
g) = a -> a -> (a, a, a)
forall a. Integral a => a -> a -> (a, a, a)
egcd a
b a
r

readEntire :: Reader a -> Text -> Either String a
readEntire :: Reader a -> Text -> Either String a
readEntire Reader a
reader Text
input = do
    (a
a, Text
t) <- Reader a
reader Text
input
    if Text -> Bool
T.null Text
t then a -> Either String a
forall a b. b -> Either a b
Right a
a else String -> Either String a
forall a b. a -> Either a b
Left String
"incomplete read"