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.

I have a book for review.

This is new to me. A publisher put out a request for reviewers and I thought I would give it a go. "Python in Practice" by Mark Summerfield has arrived.

 I get a book, which is nice. I get to try my hand at writing a book review - new experience, always welcome. But, best of all, someone thinks I'm worth giving the opportunity. (Although they did say they are in humanities when they stated that my blog looked "suitably technical"). Oh well ... :-)

I'm gonna get a smartphone! And I'm gonna run Python on it!

I get by with my company mobile and serious WiFi at home from Virgin: 120Mbs which is fast for the UK. Although our two teenage kids young adults have had (and lost) smartphones for years, I have not succumbed until yesterday when I put in an order for the Nexus 5.

Hell, I haven't worked out if I will have to carry two mobiles or what carrier deal to go for, but I have been watching the market for a while and think I have made the right choice of phone.

From present use of gadgets I think I want to be able to:

1. Read books.
2. Do admin tasks for Rosetta Code whilst out and about.
3. Capture code notes and snippets. I often write Python snippets with the core of an idea that I later expand. I am not thinking of doing nights of development on the Nexus 5, but I do  want to be able to edit and run some code, or, cut-n-paste fifty lines of code from the web and run it on my phone to answer a Stack Overflow question.
4. Use that pedometer function of Android KitKat as I sit for too long :-)
5. Create a WiFi hotspot in the car for those long journeys with family where everyone has either a laptop and/or tablet; and the teenagers would rather use daddy's WiFi than expend their pay-as-you-go credit.

I have a script I wrote on my PC that uses wget to download pages from Rosetta Code then a Python program to search for new pages and display them on a browser as well as prompt me if the page should be deleted and the user blocked if they are spamming. The Python creates a script for iMacros which then deletes pages/blocks users as requested.
It is a lot of functionality to duplicate on Android, but I'll probably give it a go sometime. If you know of anything that could help/substitute for things like wget and iMacros that works on Android then please add to the comments, but I should stress that I haven't started looking myself as yet.

Unifying Pythons string and list sequences for fsplit

I was looking at a particular post A more functional split function by Simon Grondin and wondered what it would look like in Python.

Simon describes his function thus:
"Fsplit takes a single ‘predicate’ function as argument. It loops over the array and adds one element at a time to a ‘buffer’ array. After adding an element, it calls the predicate on the buffer. If the predicate returns true, the buffer without the last element is added to the ‘ret’ array. At the end, that ‘ret’ array is returned, filtered from any 0-length elements."
Now a Python version would take both the predicate and array as arguments and, since it is to be in a functional style I decided to make it a generator function.

fsplit_list

Simon's first fsplit function works on arrays and had as its first test to split an array of integers on the occurrence of  integer 3. The second test was to split to " get all consecutive intervals with a sum of 4 or less"

I coded that up as the following Python:

>>> def fsplit_list(predicate, array):
    buf = []
    for c in array:
        buf.append(c)
        if predicate(buf):
            if buf[:-1]: yield buf[:-1]
            buf = [] if predicate([c]) else [c]
    else:
        if buf: yield buf


>>> # Split on 3
>>> list(fsplit_list(lambda x: 3 in x, [1,2,3,4,5,1,2,3,3,4,5]))
[[1, 2], [4, 5, 1, 2], [4, 5]]
>>> # Get all consecutive intervals with a sum of 4 or less
>>> list(fsplit_list(lambda x: sum(x) > 4, [1,2,3,4,5,1,2,3,3,4,5]))
[[1, 2], [3], [4], [1, 2], [3], [3], [4]]
>>>

fsplit_string

SImon then needed another function in his typed language that took a predicate and a string as arguments and worked in a similar way for strings. The test in this case was to split a string into substreings with no more than two vowels in them. My Python code was the similar function fsplit_string:

>>> import re
>>> def fsplit_string(predicate, string):
    buf = ''
    for c in string:
        buf += c
        if predicate(buf):
            if buf[:-1]: yield buf[:-1]
            buf = '' if predicate(c) else c
    else:
        if buf: yield buf


>>> # String
>>> list(fsplit_string(lambda string: len(re.findall(r'[aeiou]', string)) > 2, "lorem ipsum dolor sit amet"))
['lorem ', 'ipsum d', 'olor s', 'it am', 'et']
>>>

Unification

I wanted to have one function that worked on both lists and strings but without executing separate code dependant on the type of the sequence being split. Specifically it should work equally on lists and strings without testing for sequence type.

Comparing the two functions above I saw differences in the initialization of buf; the fact that iterating through a string leads to c being a string but for a list c is not a list - it is whatever object is in the list. This last point affects how buf is extended - for strings you can use += but lists have to be appended to.

My solution with the same tests is as follows:

>>> def fsplit(predicate, sequence):
    buf = type(sequence)()
    for c in (sequence[i:i+1] for i in range(len(sequence))):
        buf += c
        if predicate(buf):
            if buf[:-1]: yield buf[:-1]
            buf = type(sequence)() if predicate(c) else c
    else:
        if buf: yield buf


>>> # Split on 3
>>> list(fsplit(lambda x: 3 in x, [1,2,3,4,5,1,2,3,3,4,5]))
[[1, 2], [4, 5, 1, 2], [4, 5]]
>>> # Get all consecutive intervals with a sum of 4 or less
>>> list(fsplit(lambda x: sum(x) > 4, [1,2,3,4,5,1,2,3,3,4,5]))
[[1, 2], [3], [4], [1, 2], [3], [3], [4]]
>>> # String
>>> list(fsplit(lambda string: len(re.findall(r'[aeiou]', string)) > 2, "lorem ipsum dolor sit amet"))
['lorem ', 'ipsum d', 'olor s', 'it am', 'et']
>>>

That strange initialization of buf works because calling the type of a sequence gives the empty sequence of that type.

I realised that if I could create successive one member slices from a list as name c then they could be concatenated using += just like for strings hence the for statement that generates successive items from a list as one element lists - it works in a similar way for strings too - giving successive elements of a string as one element strings (but that is what the "normal" for statement did in fsplit_string).

I guess some of the fiddling about is because strings are immutable whereas lists are mutable in Python, but I wonder if there is a better/more pythonic way of writing function fsplit to the same constraints?

END.

Project Euler #8 solution

Someone asked some innocuous question related to a Project Euler question where you had to find the largest number that is produced by multiplying five consecutive digits of a thousand digit number.

The digits were presented as twenty rows of fifty characters and the question was about how to grab the web page and extract the number.

I decided to do a straight-forward copy-paste of the digits into a string and going from there.

The algorithm I use recognises that finding a zero in the digits zeroes out any product and just traverses the digits in order performing appropriate actions based on accumulated state:

# http://projecteuler.net/problem=8#!

xstring = '''73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450'''
x = int(xstring.replace('\n', ''))
xl = [int(ch) for ch in xstring if ch != '\n']

# current product; current maximum and index of where seen; number of digits contributing to prod
prod, mx, digits = 0, (0, -1), 0
for i, digit in enumerate(xl):
    if digit == 0:
        # Need to start again at next non-zero
        prod = digits = 0
    else:
        digits += 1
        if digits == 1:
            prod = digit
        else:
            prod *= digit
        if digits > 5:
            # Remove influence of the first of six digits currently in product
            prod //= xl[i - 5]
            digits -= 1
        if digits == 5 and prod > mx[0]:
            # New max at position i
            mx = (prod, i)
if mx[0]:
    print ("The greatest product of five consecutive digits in the 1000-digit number")
    print ("is %i for ...%s... occurring at digits in position up to %i" %
           (mx[0], ''.join(str(i) for i in xl[mx[1] - 5: mx[1]]), mx[1]))
else:
    print ("The greatest product of five consecutive digits in the 1000-digit number does not occur")

The output is:

The greatest product of five consecutive digits in the 1000-digit number
is 40824 for ...39987... occurring at digits in position up to 368

- END.

Recursive Unix bang-bang in Python

There is a new series that goes 2, 3, 5, 17, 161, 15681, … and has been added to OEIS as well as being blogged about by both Shadab Ahmed and Robin Houston.

The series comes from a recurrence relation that you get by sitting at unix bash terminal session and first typing in
    : '!!'
Then
    : "!!" '!!'
Then after that just hitting the up arrow key to get the last command expanded by the shell then hitting return; add infinitum.

The series comes from counting the number of '!!' pairs in each successive line.

Now I don't always have unix and bash to hand so I decided to write a Python "shell" program with enough functionality to simulate the recurrence relation.

In the bash shell:

1. !! is replaced by the previous command if it is outside of any quotes.
2. !! is replaced by the previous command if it is inside a double quoted string, ("...").
3. !! is NOT replaced by the previous command if it is inside a single quoted string, ('...').
4. Quoted strings do not nest. Single quotes inside double quotes are treated as plain characters and equally double quotes inside single quotes are treated as plain characters; (they don't terminate the current type of quoted string).
5. Apart from when !! is replaced as above, characters are copied to form the latest expanded command.
6. The up-arrow key should put the previous expanded command on the input line.

The following works on windows for me using Python 2.7 (Anaconda) which has a windows version of the readline module.

# -*- coding: utf-8 -*-
"""
Created on Tue Aug 20 17:23:37 2013

@author: Paddy McCarthy
"""

try:    # Python 2/3 compatibility
    raw_input
except:
    raw_input = input
import readline


prev = ": '!!'"
print('$ ' + prev)
while True:
    cmd = raw_input('$ ').rstrip()
    dquote = squote = skipnext = False
    result = []
    for this, nxt in zip(cmd, cmd[1:] + ' '):
        if skipnext:
            skipnext = False
            continue
        elif this == '"' and not squote:
            dquote = not dquote
            result.append(this)
        elif this == "'" and not dquote:
            squote = not squote
            result.append(this)
        elif this == '!' == nxt and not squote:
            skipnext = True
            result.append(prev)
        else:
            result.append(this)
    result = ''.join(result)
    print('%s # bang-bang count = %i' % (result, result.count('!!')))
    readline.add_history(result)
    prev = result

I have used it to verify the first 6 terms of the series so far.

cmd.exe running the Python bang-bang shell simulator

-END.