# Python implementation of Conway's chained arrow notation

A year ago, I implemented an evaluation algorithm for Conway's chained arrow notation in Python. I'd like to get a review on my code, especially about readability and if it is pythonic. I'd also like to know if there is a bug. I'm not too much concerned about performance since this notation runs faster into unsolvable memory problems than it runs into long loops. For example, resolve('3->3->2->2') would have to build a list with 7.6 trillion strings if it didn't raise a MemoryError manually before.

# coding: utf-8

MAX_BYTES = 1 << 30

def do_brackets_match(chain):

open_brackets = 0
for c in chain:
if c == '(':
open_brackets += 1
if c == ')':
open_brackets -= 1
if open_brackets < 0:
return False
return open_brackets == 0

def split_by_inner_bracket(chain):

start, part3 = chain.partition(')')[::2]
start, middle = start.rpartition('(')[::2]
return [start, middle, part3]

def is_arrow_chain(chain):

return '->' in chain

def resolve_pure(chain):

assert '(' not in chain and ')' not in chain

# remove whitespace
chain = chain.replace(' ', '')
chain = chain.replace('\t', '')

# get values
str_values = chain.split('->')

# handle short chains
length = len(str_values)
if length == 1:
return str_values[0]
b = int(str_values[-2])
n = int(str_values[-1])
if length == 2:
if n.bit_length() > 1024 or b.bit_length() * 8 * n > MAX_BYTES:
raise MemoryError
return str(b ** n)

if b > MAX_BYTES:
raise MemoryError

# remove everything after a 1
for i, s in enumerate(str_values):
if str_values[i] == '1':
str_values = str_values[:i]
break

# construct the next iteration step
resolved_chain += (')->' + str(n-1)) * (b-1)
resolved_chain = resolved_chain.replace('->1)', ')')
if resolved_chain.endswith('->1'):
resolved_chain = resolved_chain[:-3]
return resolved_chain

def resolve(chain, show_progress=False, depth=0):

while is_arrow_chain(chain):
if show_progress:
print(' ' * depth + chain)
if '(' in chain or ')' in chain:
part = split_by_inner_bracket(chain)
if is_arrow_chain(part[1]):
part[1] = resolve(part[1], show_progress, depth+1)
chain = ''.join(part)
else:
chain = resolve_pure(chain)
return chain

def main():

print(resolve('2->3->3', True))
print('----------------')
print(resolve('2->2->3->3', True))
print('----------------')
print(resolve('3->2->3', True))

if __name__ == '__main__':

main()


Output:

2->3->3
2->(2->(2)->2)->2
2->(2->2->2)->2
2->2->2
2->(2)
2->2
2->4->2
2->(2->(2->(2)))
2->(2->(2->2))
2->2
2->(2->4)
2->4
2->16
65536
----------------
2->2->3->3
2->2->(2->2->(2->2)->2)->2
2->2
2->2->(2->2->4->2)->2
2->2->4->2
2->2->(2->2->(2->2->(2->2)))
2->2
2->2->(2->2->(2->2->4))
2->2->4
2->(2)->3
2->2->3
2->(2)->2
2->2->2
2->(2)
2->2
2->2->(2->2->4)
2->2->4
2->(2)->3
2->2->3
2->(2)->2
2->2->2
2->(2)
2->2
2->2->4
2->(2)->3
2->2->3
2->(2)->2
2->2->2
2->(2)
2->2
2->2->4->2
2->2->(2->2->(2->2->(2->2)))
2->2
2->2->(2->2->(2->2->4))
2->2->4
2->(2)->3
2->2->3
2->(2)->2
2->2->2
2->(2)
2->2
2->2->(2->2->4)
2->2->4
2->(2)->3
2->2->3
2->(2)->2
2->2->2
2->(2)
2->2
2->2->4
2->(2)->3
2->2->3
2->(2)->2
2->2->2
2->(2)
2->2
4
----------------
3->2->3
3->(3)->2
3->3->2
3->(3->(3))
3->(3->3)
3->3
3->27
7625597484987


After looking at the code again I was able to discover some issues.

def do_brackets_match(chain):

Actually a nice function to check if the input is a valid chain notation ... I was really surprised when I didn't find any call to it. resolve_pure() doesn't accept chains with parenthesis, so do_brackets_match() would be used in resolve()

def split_by_inner_brackets(chain):

It looks a bit ugly to slice the result of str.partition() in order to discard the separator. Today I would prefer str.split() with maxsplit=1.

def resolve_pure(chain)

First of all, I consider renaming this function to expand_chain or similar. I would also rename the variable resolved_chain to expanded_chain in that case. Secondly, this loop is a bit confusing:

for i, s in enumerate(str_values):
if str_values[i] == '1':


I should definitly rewrite the second line to if s == '1'. I mean, that's the whole point of using enumerate(), isn't it?

As you might have noticed from the examples, a chain which starts with '2->2->' always results in '4'. I could handle that special case.

def resolve(chain, show_progress=False, depth=0):

As mentioned before, this function should call do_brackets_match(), probably right at the start. If it fails, it should raise an exception or at least print a message and return ''. When evaluating the inner bracket, it might be useful to call eval in order to evaluate common arithmetic expressions like (2*5+3).

Neither resolve_pure() nor resolve check for negative values which should be avoided as they can cause an error