3
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.