107 lines
2.5 KiB
Python
107 lines
2.5 KiB
Python
'''Babbage problem'''
|
|
|
|
from math import (floor, sqrt)
|
|
from itertools import (islice)
|
|
|
|
|
|
# squaresWithSuffix :: Int -> Gen [Int]
|
|
def squaresWithSuffix(n):
|
|
'''Non finite stream of squares with a given suffix.'''
|
|
stem = 10 ** len(str(n))
|
|
i = 0
|
|
while True:
|
|
i = until(lambda x: isPerfectSquare(n + (stem * x)))(
|
|
succ
|
|
)(i)
|
|
yield n + (stem * i)
|
|
i = succ(i)
|
|
|
|
|
|
# isPerfectSquare :: Int -> Bool
|
|
def isPerfectSquare(n):
|
|
'''True if n is a perfect square.'''
|
|
r = sqrt(n)
|
|
return r == floor(r)
|
|
|
|
|
|
# TEST ----------------------------------------------------
|
|
|
|
# main :: IO ()
|
|
def main():
|
|
'''Smallest positive integers whose squares end in the digits 269,696'''
|
|
print(
|
|
fTable(main.__doc__ + ':\n')(
|
|
lambda n: str(int(sqrt(n))) + '^2'
|
|
)(repr)(identity)(
|
|
take(10)(squaresWithSuffix(269696))
|
|
)
|
|
)
|
|
|
|
|
|
# GENERIC -------------------------------------------------
|
|
|
|
# identity :: a -> a
|
|
def identity(x):
|
|
'''The identity function.'''
|
|
return x
|
|
|
|
|
|
# succ :: Enum a => a -> a
|
|
def succ(x):
|
|
'''The successor of a value.
|
|
For numeric types, (1 +).
|
|
'''
|
|
return 1 + x if isinstance(x, int) else (
|
|
chr(1 + ord(x))
|
|
)
|
|
|
|
|
|
# take :: Int -> [a] -> [a]
|
|
# take :: Int -> String -> String
|
|
def take(n):
|
|
'''The prefix of xs of length n,
|
|
or xs itself if n > length xs.
|
|
'''
|
|
return lambda xs: (
|
|
xs[0:n]
|
|
if isinstance(xs, (list, tuple))
|
|
else list(islice(xs, n))
|
|
)
|
|
|
|
|
|
# until :: (a -> Bool) -> (a -> a) -> a -> a
|
|
def until(p):
|
|
'''The result of repeatedly applying f until p holds.
|
|
The initial seed value is x.
|
|
'''
|
|
def go(f, x):
|
|
v = x
|
|
while not p(v):
|
|
v = f(v)
|
|
return v
|
|
return lambda f: lambda x: go(f, x)
|
|
|
|
|
|
# FORMATTING ----------------------------------------------
|
|
# fTable :: String -> (a -> String) ->
|
|
# (b -> String) -> (a -> b) -> [a] -> String
|
|
def fTable(s):
|
|
'''Heading -> x display function -> fx display function ->
|
|
f -> xs -> tabular string.
|
|
'''
|
|
def go(xShow, fxShow, f, xs):
|
|
ys = [xShow(x) for x in xs]
|
|
w = max(map(len, ys))
|
|
return s + '\n' + '\n'.join(map(
|
|
lambda x, y: y.rjust(w, ' ') + ' -> ' + fxShow(f(x)),
|
|
xs, ys
|
|
))
|
|
return lambda xShow: lambda fxShow: lambda f: lambda xs: go(
|
|
xShow, fxShow, f, xs
|
|
)
|
|
|
|
|
|
# MAIN ---
|
|
if __name__ == '__main__':
|
|
main()
|