- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
#-*-coding:utf8;-*-
combinators = {
'I': lambda x: x if len(x) <= 1 else calc(x[1:]),
'K': lambda x: x if len(x) <= 2 else calc((x[1],) + x[3:]),
'W': lambda x: x if len(x) <= 2 else calc(x[1:3] + x[2:]),
'S': lambda x: x if len(x) <= 3 else calc((x[1], x[3], (x[2], x[3])) + x[4:]),
'B': lambda x: x if len(x) <= 3 else calc((x[1], (x[2], x[3])) + x[4:]),
'C': lambda x: x if len(x) <= 3 else calc((x[1], x[3], x[2]) + x[4:]),
'U': lambda x: x if len(x) <= 2 else calc((x[2], (x[1], x[1], x[2])) + x[3:]),
'Y': lambda x: x if len(x) <= 1 else calc(('S',('K',('S','I','I')),('S',('S',('K','S'),'K'),('K',('S','I','I')))) + x[2:])
}
def calc(x):
def f(x, top = False):
if type(x) is not tuple or len(x) == 0:
return x
if top:
while type(x[0]) is tuple:
x = x[0] + x[1:]
else:
if type(x[0]) is tuple:
return (calc(x[0]),) + f(x[1:])
print(termrepr(x))
input('Press Enter...')
return combinators.get(x[0], lambda _: (x[0],) + f(x[1:]))(x)
return f(x, True)
def parse(s):
def f(s, n):
res = ()
i = n
while i < len(s):
if s[i] == '(':
t, j = f(s, i + 1)
res += (t,)
i = j - 1
elif s[i] == ')':
return (res, i + 1)
else:
res += (s[i],)
i += 1
return (res, i)
return f(s, 0)[0]
def termrepr(x):
if len(x) == 0:
return ''
if type(x[0]) is tuple:
return '(' + termrepr(x[0]) + ')' + termrepr(x[1:])
else:
return x[0] + termrepr(x[1:])
print('>> ', end = '')
while True:
print(termrepr(calc(parse(input()))))
print('\n>> ', end = '')
Теперь ясно, почему зацикливает. GU(GU)R = U(GU)R = R((GU)(GU)R) и дальше ничего не сделать.
Можно реализовать детектор циклов: складывать куда-нибудь промежуточные значения, а потом каждый новый результат сравнивать со всеми предыдущими.
Куда-куда, в префиксное дерево.
Продолжи ряд чисел:
1, 11, 21, 1112, 3112, 211213, 312213, 212223, 114213, 31121314, 41122314, 31221324, 21322314, 21322314, ...
Если начинать этот ряд с каких-нибудь других чисел, можно собрать какое-то количество таких self-describing чисел. Наименьшее из них — 22.
21322314
31123314
3122331415
41322324151617
5132231425161718
613223141526171819