Tuesday, August 20, 2013

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.