• API
• FAQ
• Tools
• Archive
daily pastebin goal
1%
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.
23.     """
24.    Calculates alpha + beta with the usual non-commutative
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."):
145.         def __init__(self):
147.             self.result = default
148.         def run(self):
149.             try:
150.                 self.result = func(*args)
151.             except:
152.                 self.result = punchline
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.

Top