Python implementation of Conway's chained arrow notation

Question

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
 leading_chain = '->'.join(str_values[:-2])
 resolved_chain = '->('.join([leading_chain] * b)
 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

Answer 1

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