SHARE
TWEET

Ordinals in Python

a guest May 24th, 2012 29 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import time
  2. timeout_in_sec = 3
  3.  
  4. """
  5. The functions numterms, add, deepfund, fund, ack, trans, u and
  6. beautify take their natural number inputs as normal Python
  7. integers, and their ordinal inputs in the format
  8. <ord> = <ord> + <ord>
  9.      | <num>w^(<ord>)
  10.      | <num>w
  11.      | <num>
  12. with the usual ordinal addition rules. The notation only
  13. covers the harmless ordinals.
  14. """
  15.  
  16. def numterms(alpha):
  17.     """
  18.    Returns the number of terms in alpha.
  19.    """
  20.     return len(p(alpha))
  21.  
  22. def add(*alphas):
  23.     """
  24.    Calculates alpha + beta with the usual non-commutative
  25.    ordinal addition.
  26.    """
  27.     return up(p("+".join(alphas)))
  28.  
  29. def deepfund(alpha, n):
  30.     """
  31.    Calculates alpha((n)) given an ordinal alpha and a
  32.    natural number n.
  33.    """
  34.     return up(timeout(deepfund_, (p(alpha),n),
  35.                       td=timeout_in_sec))
  36.  
  37. def fund(alpha, n):
  38.     """
  39.    Calculates alpha(n) given an ordinal alpha and a natural
  40.    number n.
  41.    """
  42.     return up(timeout(fund_, (p(alpha),n), td=timeout_in_sec))
  43.  
  44. def ack(alpha, n):
  45.     """
  46.    Calculates f_alpha given an ordinal alpha.
  47.    """
  48.     return up(timeout(timeout(ack_, (p(alpha),),
  49.                               td=timeout_in_sec),
  50.                       (n,),
  51.                       td=timeout_in_sec))
  52.  
  53. def trans(n, alpha, m):
  54.     """
  55.    Calculates T_{n, alpha} as a generator, given an ordinal
  56.    alpha and a natural number n.
  57.    """
  58.     t = timeout(trans_, (n, p(alpha)), td=timeout_in_sec)
  59.     v = 0
  60.     for i in range(m-n+1):
  61.         v = t.next()
  62.     return up(v)
  63.  
  64. def u(n, alpha):
  65.     """
  66.    Calculates U(n, alpha) given an ordinal alpha and a natural
  67.    number n.
  68.    """
  69.     return up(timeout(u_, (n, p(alpha)), td=timeout_in_sec))
  70.    
  71. def beautify(o):
  72.     """
  73.    Fixes the representation of an ordinal.
  74.    """
  75.     return up(p(o)) # nalle
  76.  
  77. class ParseError(Exception):
  78.     def __init__(self, value):
  79.         self.value = value
  80.     def __str__(self):
  81.         return repr(self.value)
  82.  
  83. def p(o):
  84.     if isinstance(o, int): return o
  85.     else:
  86.         o = "".join(filter(lambda a:a!=" ", o))
  87.         try:
  88.             parsed = p_(o,0)[0]
  89.         except ParseError, e:
  90.             return "Parse error near " + str(e.value) + \
  91.                    " in ordinal input."
  92.         except:
  93.             return "Unknown parse error in ordinal input."
  94.     return fix_(parsed)
  95.  
  96. def up(o):
  97.     if isinstance(o,str):return o
  98.     o = fix_(o)
  99.     if isinstance(o, int):return str(o)
  100.     def m(t):
  101.         if isinstance(t, int):return str(t)
  102.         elif t[1]==1:
  103.             r="w"
  104.         else:
  105.             r="w^("+up(t[1])+")"
  106.         if t[0]==1:return r
  107.         return str(t[0])+r
  108.     return " + ".join(map(m,o))
  109.  
  110. def p_(string,i):
  111.     v = []
  112.     while True:
  113.         j=i
  114.         while j < len(string) and string[j].isdigit():
  115.             j+=1
  116.         intstring = string[i:j]
  117.         if intstring == "":
  118.             coef = None
  119.         else:
  120.             coef = int(intstring)
  121.         i=j
  122.         if i == len(string) or string[i] == ")":
  123.             if coef == None: return v, i+1
  124.             v.append(coef)
  125.             return v, i+1
  126.         elif string[i:i+3] == "w^(":
  127.             exp, i = p_(string, i+3)
  128.             if coef == None: coef = 1
  129.             v.append((coef, exp))
  130.         elif string[i]=="w":
  131.             i+=1
  132.             if coef == None: coef = 1
  133.             v.append((coef, 1))
  134.         elif string[i]=="+":
  135.             i+=1
  136.         else:
  137.             raise ParseError(i)
  138.         if i < len(string) and string[i] == "+":
  139.             i+=1
  140.  
  141. def timeout(func, args=(), td=None,
  142.             default="Sorry, I ran out of time."):
  143.     import threading
  144.     class InterruptableThread(threading.Thread):
  145.         def __init__(self):
  146.             threading.Thread.__init__(self)
  147.             self.result = default
  148.         def run(self):
  149.             try:
  150.                 self.result = func(*args)
  151.             except:
  152.                 self.result = punchline
  153.     it = InterruptableThread()
  154.     it.start()
  155.     if td == None:
  156.         it.join()
  157.     else:
  158.         it.join(td)
  159.     return it.result
  160.  
  161. def limit_(alpha):
  162.     if isinstance(alpha, int):
  163.         return False
  164.     lastv = alpha[-1][1]
  165.     return lastv != 0
  166.  
  167. def ord_cmp_(alpha, beta):
  168.     alpha, beta = fix_(alpha), fix_(beta)
  169.     # base cases
  170.     if isinstance(alpha, int):
  171.         if isinstance(beta, int):
  172.             return alpha - beta
  173.         return -1
  174.     if isinstance(beta, int):
  175.         return 1
  176.     c = ord_cmp_(alpha[0][1], beta[0][1])
  177.     if c == 0:
  178.         coefc = alpha[0][0] - beta[0][0]
  179.         if coefc == 0:
  180.             return ord_cmp_(alpha[1:], beta[1:])
  181.         return coefc
  182.     return c
  183.  
  184. def fix_(alpha):
  185.     if isinstance(alpha, int):
  186.         return alpha
  187.     if len(alpha) == 0:
  188.         return 0
  189.     def intfix_(a):
  190.         if isinstance(a, int):return (a,0)
  191.         return a
  192.     def unintfix_(a):
  193.         if isinstance(a, int):a
  194.         elif a[1]==0:return a[0]
  195.         return a
  196.     alpha = list(map(intfix_, alpha))
  197.     if len(alpha) == 1 and fix_(alpha[0][1]) == 0:
  198.         return alpha[0][0]
  199.     alpha = list(map(lambda(c,e):(c,fix_(e)),alpha))
  200.     i = 1
  201.     while i < len(alpha):
  202.         if i == 0:
  203.             i+=1
  204.             continue
  205.         c = ord_cmp_(alpha[i-1][1], alpha[i][1])
  206.         if c < 0:
  207.             alpha = alpha[0:i-1] + \
  208.                     [(alpha[i][0], alpha[i][1])] + \
  209.                     alpha[i+1:]
  210.             i -= 1
  211.         elif c == 0:
  212.             alpha = alpha[0:i-1] + \
  213.                     [(alpha[i-1][0] + alpha[i][0],
  214.                       alpha[i][1])] + alpha[i+1:]
  215.         elif c > 0:
  216.             i += 1
  217.     return list(map(unintfix_,alpha))
  218.  
  219. def prec_(alpha):
  220.     assert not limit_(alpha) and alpha != 0 and \
  221.            alpha != [(0,0)]
  222.     if isinstance(alpha, int):
  223.         return alpha - 1
  224.     beta = alpha[:]
  225.     if beta[-1][0] == 1:
  226.         return fix_(beta[:-1])
  227.     beta[-1] = (beta[-1][0]-1,beta[-1][1])
  228.     return beta
  229.  
  230. def fund_(alpha,n):
  231.     if not limit_(alpha):
  232.         return alpha
  233.     beta = alpha[:-1]
  234.     lastc, lastv = alpha[-1]
  235.     if lastc > 1:
  236.         beta = beta + [(lastc-1,lastv)]
  237.     if limit_(lastv):
  238.         return beta + [(1,fund_(lastv,n))]
  239.     else:
  240.         return beta + [(n,prec_(lastv))]
  241.  
  242. def power_(f,n):
  243.     def pow_f_n(m):
  244.         k=m
  245.         for i in xrange(n):
  246.             k=f(k)
  247.         return k
  248.     return pow_f_n
  249.  
  250. def deepfund_(alpha,n):
  251.     beta=alpha
  252.     while limit_(beta):
  253.         beta=fund_(beta,n)
  254.     return beta
  255.  
  256. def ack_(alpha):
  257.     if alpha == 1 or alpha == [(1,0)]:
  258.         return lambda n: n*2
  259.     if not limit_(alpha):
  260.         return lambda n: power_(ack_(prec_(alpha)),n)(n)
  261.     return lambda n: ack_(fund_(alpha,n))(n)
  262.  
  263. def trans_(n,alpha):
  264.     beta = alpha
  265.     m=n
  266.     while True:
  267.         yield beta
  268.         if beta!=0 and beta!=[(0,0)]:
  269.             beta = prec_(deepfund_(beta,m))
  270.         m+=1
  271.  
  272. def u_(n,alpha):
  273.     g=trans_(n,alpha)
  274.     m=n
  275.     while True:
  276.         beta=g.next()
  277.         if beta==0 or beta==[(0,0)]:
  278.             return m
  279.         m+=1
  280.  
  281. punchline = "I need a bigger universe to compute this."
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top