92 lines
1.8 KiB
Python
92 lines
1.8 KiB
Python
from functools import (reduce)
|
|
from itertools import (chain)
|
|
|
|
|
|
# modInv :: Int -> Int -> Maybe Int
|
|
def modInv(a):
|
|
return lambda m: (
|
|
lambda ig=gcdExt(a)(m): (
|
|
lambda i=ig[0]: (
|
|
Just(i + m if 0 > i else i) if 1 == ig[2] else (
|
|
Nothing()
|
|
)
|
|
)
|
|
)()
|
|
)()
|
|
|
|
|
|
# gcdExt :: Int -> Int -> (Int, Int, Int)
|
|
def gcdExt(x):
|
|
def go(a, b):
|
|
if 0 == b:
|
|
return (1, 0, a)
|
|
else:
|
|
(q, r) = divmod(a, b)
|
|
(s, t, g) = go(b, r)
|
|
return (t, s - q * t, g)
|
|
return lambda y: go(x, y)
|
|
|
|
|
|
# TEST ---------------------------------------------------
|
|
|
|
# Numbers between 2010 and 2015 which do yield modular inverses for 42:
|
|
|
|
# main :: IO ()
|
|
def main():
|
|
print (
|
|
mapMaybe(
|
|
lambda y: bindMay(modInv(42)(y))(
|
|
lambda mInv: Just((y, mInv))
|
|
)
|
|
)(
|
|
enumFromTo(2010)(2025)
|
|
)
|
|
)
|
|
|
|
# -> [(2011, 814), (2015, 48), (2017, 1969), (2021, 1203)]
|
|
|
|
|
|
# GENERIC ABSTRACTIONS ------------------------------------
|
|
|
|
|
|
# enumFromTo :: Int -> Int -> [Int]
|
|
def enumFromTo(m):
|
|
return lambda n: list(range(m, 1 + n))
|
|
|
|
|
|
# bindMay (>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
|
|
def bindMay(m):
|
|
return lambda mf: (
|
|
m if m.get('Nothing') else mf(m.get('Just'))
|
|
)
|
|
|
|
|
|
# Just :: a -> Maybe a
|
|
def Just(x):
|
|
return {'type': 'Maybe', 'Nothing': False, 'Just': x}
|
|
|
|
|
|
# mapMaybe :: (a -> Maybe b) -> [a] -> [b]
|
|
def mapMaybe(mf):
|
|
return lambda xs: reduce(
|
|
lambda a, x: maybe(a)(lambda j: a + [j])(mf(x)),
|
|
xs,
|
|
[]
|
|
)
|
|
|
|
|
|
# maybe :: b -> (a -> b) -> Maybe a -> b
|
|
def maybe(v):
|
|
return lambda f: lambda m: v if m.get('Nothing') else (
|
|
f(m.get('Just'))
|
|
)
|
|
|
|
|
|
# Nothing :: Maybe a
|
|
def Nothing():
|
|
return {'type': 'Maybe', 'Nothing': True}
|
|
|
|
|
|
# MAIN ---
|
|
main()
|