111 lines
2.5 KiB
Python
111 lines
2.5 KiB
Python
'''Recaman by iteration of a function over a tuple.'''
|
|
|
|
from itertools import (islice)
|
|
|
|
|
|
# recamanTupleSucc :: Set Int -> (Int, Int, Bool) -> (Int, Int, Bool)
|
|
def recamanTupleSucc(seen):
|
|
'''The Nth in a series of Recaman tuples,
|
|
(N, previous term, boolPreviouslySeen?)
|
|
given the set of all terms seen so far.'''
|
|
def go(n, r, _):
|
|
back = r - n
|
|
nxt = n + r if 0 > back or (back in seen) else back
|
|
bln = nxt in seen
|
|
seen.add(nxt)
|
|
return (1 + n, nxt, bln)
|
|
return lambda tpl: go(*tpl)
|
|
|
|
|
|
# ------------------------- TEST -------------------------
|
|
# main :: IO()
|
|
def main():
|
|
'''First 15, and first duplicated Recaman.'''
|
|
f = recamanTupleSucc(set([0]))
|
|
print(
|
|
'First 15 Recaman:\n',
|
|
list(map(
|
|
snd,
|
|
take(15)(iterate(f)((1, 0, False)))
|
|
))
|
|
)
|
|
f = recamanTupleSucc(set([0]))
|
|
print(
|
|
'First duplicated Recaman:\n',
|
|
until(lambda x: x[2])(f)(
|
|
(1, 0, False)
|
|
)[1]
|
|
)
|
|
|
|
sk = set(enumFromTo(0)(1000))
|
|
sr = set([0])
|
|
f = recamanTupleSucc(sr)
|
|
print(
|
|
'Number of Recaman terms needed to generate',
|
|
'all integers from [0..1000]:\n',
|
|
until(
|
|
lambda x: not x[2] and 1001 > x[1] and sk.issubset(sr)
|
|
)(f)(
|
|
(1, 0, False)
|
|
)[0] - 1
|
|
)
|
|
|
|
|
|
# ----------------- GENERIC ABSTRACTIONS -----------------
|
|
|
|
# enumFromTo :: (Int, Int) -> [Int]
|
|
def enumFromTo(m):
|
|
'''Integer enumeration from m to n.'''
|
|
return lambda n: range(m, 1 + n)
|
|
|
|
|
|
# iterate :: (a -> a) -> a -> Gen [a]
|
|
def iterate(f):
|
|
'''An infinite list of repeated
|
|
applications of f to x.
|
|
'''
|
|
def go(x):
|
|
v = x
|
|
while True:
|
|
yield v
|
|
v = f(v)
|
|
return go
|
|
|
|
|
|
# snd :: (a, b) -> b
|
|
def snd(tpl):
|
|
'''Second component of a tuple.'''
|
|
return tpl[1]
|
|
|
|
|
|
# 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)
|
|
else 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):
|
|
def g(x):
|
|
v = x
|
|
while not p(v):
|
|
v = f(v)
|
|
return v
|
|
return g
|
|
return go
|
|
|
|
|
|
# MAIN ---
|
|
if __name__ == '__main__':
|
|
main()
|