Wednesday, January 22, 2014

Fractran and the Python for-else loop

I don't often get to use the else clause that is part of the Python for loop, so when I had a problem that it was perfect for I made note.

Fractran

Fractran, it seems, is a new (to me), curiosity that someone turned into a Rosetta Code task recently. I couldn't quite understand what was being asked for for a while, but when it finally clicked it was so straight-forward that I thought it couldn't be that simple.
Fractran goes something like this:
  • You are given a finite list of fractions. (You know, numerator over denominator where both are integers).
  • And an integer, n that is the first term in a series
  • Successive terms in the series are found by:
  • Finding the first fraction from the list that when multiplied by n gives an integer result
  • If found then replace n by n times the found fraction to give the next output term
  • In no fraction is found then the series terminates.
The Rosetta code task also restricts the format of the list of fractions.

For-else

Many C-like programming languages have for-loops. The Python for loop has an optional else clause where the body of the else clause is only executed when the for loop finishes by "naturally" coming to the end of what it was iterating over - as opposed to if the for loop is exited by an exception/break.
In [4]:
for i in range(3):
    print(i)
else:
    print('from else clause')
    
0
1
2
from else clause
Else not run due to for-loop executing the break statement:
In [3]:
for i in range(3):
    print(i)
    if i == 1:
        break
else:
    print('from else clause')
0
1
The fractran algorithm has that "terminate if fraction not found" part that happens only after iterating through all the fractions and not finding one that meets a condition.

The Program

fractran is written as a generator and of course uses the fractions module.
If you look up Fraction you will find that it can take a string as input. The string parser is rudimentary and will not accept spaces around the '/' character so I remove them in my input string parsing
In [5]:
from fractions import Fraction

def fractran(n, fstring='17 / 91, 78 / 85, 19 / 51, 23 / 38, 29 / 33,'
                        '77 / 29, 95 / 23, 77 / 19, 1 / 17, 11 / 13,'
                        '13 / 11, 15 / 14, 15 / 2, 55 / 1'):
    flist = [Fraction(f) for f in fstring.replace(' ', '').split(',')]

    yield n
    while True:
        for f in flist:
            if (n * f).denominator == 1:
                break
        else:
            break
        n *= f
        yield n.numerator
    
if __name__ == '__main__':
    n, m = 2, 15
    print('First %i members of fractran(%i):\n  ' % (m, n) +
          ', '.join(str(f) for f,i in zip(fractran(n), range(m))))
First 15 members of fractran(2):
  2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170, 156, 132
There are two break statements in the for loop. The one in the inner if statement breaks out of the for block without running the code in the else clause. The second break is in the else clause which is only run when the list of fractions in flist is exausted. This second break exits the next outer loop i.e. the while loop which then terminates the generator.

END.