#!/usr/bin/env python

# Definitions of and experiments with sequences from page 137 of GEB.

def memoize(f):
    cache = {}
    def proxy(n):
        return f(n)
    def g(n):
        if n not in cache:
            cache[n] = f(n)
        return cache[n]
    return g

def fn_iter(iter):
    """Turn an iterator into a function taking indexes."""
    cache = []
    def f(n):
        while len(cache) <= n:
            cache.append(iter.next())
        return cache[n]
    return f

@memoize
def g(n):
    """The G function, direct definition."""
    if n == 0:
        return 0
    else:
        return n - g(g(n - 1))

def gp_iter():
    """An iterator producing the elements of the G-flip sequence."""
    yield 0
    yield 1
    queue = [(1, 1)]
    n = 2
    while True:
        parent, state = queue.pop(0)
        if state == 0:
            queue.append((n, 1))
            queue.append((n, 0))
        elif state == 1:
            queue.append((n, 0))
        else:
            assert False
        yield parent
        n += 1

# The "control" G-flip function defined from the tree.
gp = fn_iter(gp_iter())

@memoize
def x(n):
    if n == 0:
        return 0
    else:
        return (n - 1) - g(x(n - 1))

@memoize
def my_gp(n):
    """A conjectured algebraic definition of the G-flip sequence."""
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        # return (n - 1) - g(g(n - 2) - 1)
        return (n - 1) - x(x(n - 1))

@memoize
def h(n):
    """The H function, direct definition."""
    assert(n >= 0)
    if n == 0:
        return 0
    else:
        return n - h(h(h(n - 1)))

def hp_iter():
    """An iterator producing the elements of the H-flip sequence."""
    yield 0
    yield 1
    queue = [(1, 1)]
    n = 2
    while True:
        parent, state = queue.pop(0)
        if state == 0:
            queue.append((n, 1))
            queue.append((n, 0))
        elif state == 1:
            queue.append((n, 2))
        elif state == 2:
            queue.append((n, 0))
        else:
            assert False
        yield parent
        n += 1

# The "control" H-flip function defined from the tree.
hp = fn_iter(hp_iter())

@memoize
def my_hp(n):
    """An incorrect attempt at an algebraic definition of the H-flip
    function."""
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return (n - 1) - h(h(h(n - 2)))

@memoize
def f(n):
    """The F function that is paired with M."""
    if n == 0:
        return 1
    else:
        return n - m(f(n - 1))

@memoize
def m(n):
    """The M function that is paired with F."""
    if n == 0:
        return 0
    else:
        return n - f(m(n - 1))

@memoize
def q(n):
    """The chaotic Q sequence."""
    if n == 1 or n == 2:
        return 1
    else:
        return q(n - q(n - 1)) + q(n - q(n - 2))

def quote(s):
    s.replace('\\', '\\\\')
    s.replace('"', '\"')
    return '"' + s + '"'

def digraph(f, r, title = ""):
    """Print out Graphviz output of the tree defined by function f over the
    range given by iterable r. Too see it, save the output of this function to a
    file (say tmp.dot), and run
        dot -Tpng tmp.dot > tmp.png
    """
    print "digraph %s {" % quote(title)
    for n in r:
        print "\t%d -> %d;" % (n, f(n))
    print "}"

def pairs(s):
    for i in range(len(s) - 1):
        yield s[i:i + 2]

def compare(fns, r):
    """Print a table showing which functions are equal and unequal over a given
    range."""
    for n in r:
        line = "%2d:  %2d" % (n, fns[0](n))
        for f1, f2 in pairs(fns):
            v1 = f1(n)
            v2 = f2(n)
            line += " %s %2d" % (v1 == v2 and "  " or "!=", v2)
        print line

# digraph(hp, range(30), "H'")

# for n in range(100000):
#    assert gp(n) == my_gp(n), "%d %d %d" % (n, gp(n), my_gp(n))

print "G, G-Flip (direct), G-flip (algebraic)"
compare([g, gp, my_gp], range(50))
print
print "H, H-Flip (direct), H-flip (algebraic)"
compare([h, hp, my_hp], range(50))