Accelerated turing machine simulators in python utilizing memoization

fasttm.py

from bbconv import *

# Machine, N - segment length, s - initial state, p in [0..N) - initial position, t - tape state encoded as an integer
# returns (p, t) - final position and tape state
# OR None if 
def segrun(M, N, s, p, t, limit=-1):
    seen = set()
    while 0 <= p < N:
        #print(": " + bin(t)[2:].zfill(N)[::-1])
        #print("- " + " "*p + "^")
        # Detect loops
        key = ((t << 4 | s) << 8) | p
        if key in seen: break
        seen.add(key)

        limit -= 1
        if limit == 0: break
        # Perform forward transition
        w, d, s = M[s][(t>>p)&1]
        if s < 0: break
        if w:
            t |= 1<<p
        else:
            t &= ~(1 << p)
        if d:
            p += 1
        else:
            p += -1
    return (p, t, s), limit

def accelrun(M, N=8, s=0, p=0, T=[]):
    assert N>=1
    idx, dp = divmod(p, N)
    t = T[idx] if idx < len(T) else 0
    left = T[:idx]
    right = T[idx+1:][::-1]
    (p, t, s), _ = segrun(M, N, s, dp, t)
    if s>=0 and 0<=p<N: return "loop"
    if s<0: return "halt"
    if p<0:
        t<<=N
        p+=N
        if left: t|=left.pop()
    else:
        if right: t|=right.pop()<<N
    MASK = (1<<(2*N)) - 1
    memo = {}
    for i in range(50000000//N):
        if len(left) + len(right) > 10000: break
        key = (t << 4 | s) << 8 | p
        if key in memo: (p, t, s) = memo[key]
        else:
            (p, t, s), _ = segrun(M, N*2, s, p, t)
            memo[key] = (p, t, s)
        if s>=0 and 0<=p<N: return "loop"
        if s<0: break
        if p<0:
            if right or t>>N: right.append(t>>N)
            t = (t<<N)&MASK
            p+=N
            if left: t |= left.pop()
            elif key == (t << 4 | s) << 8 | p:
                return "loop left"
        else:
            if left or t&(MASK>>N): left.append(t&(MASK>>N))
            t>>=N
            p-=N
            if right: t|=right.pop()<<N
            elif key == (t << 4 | s) << 8 | p:
                return "loop right"
    return (left, t, right), p, s

N = 15
class HashNode:
    instances = {}
    hashtables = []
    def __init__(self, left, right):
        if isinstance(left, int):
            assert isinstance(right, int)
            self.level = 0
            self.left = left&((1<<N)-1)
            self.right = right&((1<<N)-1)
        else:
            assert isinstance(left, HashNode) and isinstance(right, HashNode)
            assert left.level == right.level
            self.left = left
            self.right = right
            self.level = left.level + 1
        self.hash = hash((self.left, self.right))
        HashNode.instances[(left, right)] = self
        if len(HashNode.hashtables) <= self.level: HashNode.hashtables.append({})
    def __hash__(self):
        return self.hash
    @staticmethod
    def new(left, right):
        return HashNode.instances[(left, right)] if (left, right) in HashNode.instances else HashNode(left, right)
    def center(self):
        if self.level:
            return HashNode.new(self.left.right, self.right.left)
        else:
            return self.left >> N | (self.right << N)&((1<<(N))-1)
    def __str__(self):
        if self.level == 0:
            return bin(self.left)[2:].zfill(N)[::-1] + " " + bin(self.right)[2:].zfill(N)[::-1]
        return str(self.left) + " " + str(self.right)
    def sim(self, M, s, p):
        key = (self, s, p<0)
        ht = HashNode.hashtables[self.level]
        if key in ht: return ht[key]
        if self.level == 0:
            (p, t, s), st = segrun(M, 2*N, s, N-(1 if p<0 else 0), self.left | (self.right << N))
            t = HashNode.new(t & ((1<<N)-1), t>>N)
            #print("base sim:", t, (s, p))
            if s>=0 and 0<=p<2*N: ret = (t, -2, p), -st-1
            elif s<0: ret = (t, s, p), -st-1
            else: ret = (t, s, p), -st-1
            ht[key] = ret
            return ret

        l = self.left
        r = self.right
        i = 1
        seen = set()
        steps = 0
        while 0 <= i <= 2:
            skey = (i, l, r, s, p)
            if skey in seen:
                ret = (HashNode.new(l, r), -2, p), steps
                ht[key] = ret
                return ret
            seen.add(key)
            #print("- step, pos %d, s,p: %d, %d" % (i, s, p))
            #print(l, r)
            if i == 0:
                (l, s, p), st = l.sim(M, s, p)
            elif i == 2:
                (r, s, p), st = r.sim(M, s, p)
            else:
                (c, s, p), st = HashNode.new(l.right, r.left).sim(M, s, p)
                l = HashNode.new(l.left, c.left)
                r = HashNode.new(c.right, r.right)
            steps += st
            #print("* now:  pos %d, s,p: %d, %d" % (i, s, p))
            #print(l, r)
            if s<0: break
            if p<0:
                i -= 1
            else:
                i += 1
        #print("ret %d (%d), state %d, tape %s" % (i, p, s, HashNode.new(l, r)))
        ret = (HashNode.new(l, r), s, p), steps
        ht[key] = ret
        return ret

    @staticmethod
    def clear_hash():
        for ht in HashNode.hashtables: ht.clear()

if __name__ == "__main__":
    champion = ruleparse("1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA")
    n = 0
    for i in range(20): n = HashNode.new(n, n)
    print(n.sim(champion, 0, 0))