Balanced Brackets

Let us define a simple recursive language:

balanced = '()' | '(', balanced, ')' | balanced, balanced;

The theorems (valid clauses) of our language are made up only of the parentheses. We will call a string 'balanced' if and only if it can be expressed in our language. A friendlier definition of a balanced string is as follows:

• () is a balanced string
• Putting a balanced string inside a pair of opening and closing parentheses forms a balanced string
• Concatenating two balanced strings forms a balanced string

Here are some examples:

Balanced

()
(())
()()
(()())
((()(()))()(()()))
((())(()))((())(()))

Not balanced

(
)
((
))
)(
(()
())
(()()(())

The task is to write a program which determines whether a given string is balanced. Additionally, the algorithm must reflect the language's definition as closely as possible. To reflect this goal I'm going to propose an arbitrary restriction: the algorithm should not involve any change in state. The only exception is the string being tested, which may change. Essentially what this means is that you can't use any variables which change their value. The algorithm will also almost certainly be recursive -- which makes sense because the language is defined recursively as well.

---

This took me a frustratingly long time. I rewrote the code several times over, each time slightly changing my algorithm to make it cleaner and more logical.

My function takes two parameters: a 'string' to test' (which is actually a list of that string, string) and a character which, when found at the same recursive depth, will signify that the string is balanced (expected).

The first thing in the function is a loop for handling cases where there are two or more balanced strings sitting at the same recursive depth.

I get the first element of the string (while at the same time removing it -- str.pop has that side effect) and store it in the variable first. I then do three tests:

• If first is an opening parenthesis, I check if the string following it is balanced by recursively calling the function on the rest of string. I also tell it to stop when it reaches a ) character on the same recursive depth. If it tells me that it's not balanced, I stop and return False (if the substring isn't balanced then the whole string isn't balanced).
• If first == expecting, this string (possibly a substring) is balanced because we've reached the closing character on the same recursive level as the opening one and so everything in between must have been balanced.
• If anything else has happened, the string isn't balanced and we return False.

The loop can only quit normally (without getting out via a return statement) in two ways:

• The string ended prematurely. In this case, we will still be expecting something, so the expression 'not expecting' will return False. Since the string ended prematurely the string isn't balanced, so we return False correctly.
• The string ended at the top recursive level as it should. We aren't expecting anything, so it will return True.

def balanced(string, expecting=False):
    while string:
        first = string.pop(0)
        if first == '(':
            if not balanced(string, ')'):
                return False
        elif first == expecting:
            return True
        else:
            return False
    return not expecting

And my testing:

assert balanced(list('((()))'))
assert balanced(list('()'))
assert balanced(list('()()'))
assert balanced(list('(())((()))'))
assert balanced(list('()(()()(())()((())()))'))
assert balanced(list('(((((((()))())())())()))'))
assert balanced(list('((()(())())(())()(()()))'))
assert not balanced(list(')('))
assert not balanced(list('(('))
assert not balanced(list('()))'))
assert not balanced(list('(((()))'))
assert not balanced(list(')))'))
assert not balanced(list('(()'))
assert not balanced(list('(()()()'))

Drawing the Koch Curve in Turtle

I love this fractal because it's so simple! I barely need to obfuscate the code and its definition still fits in 3 fairly neat lines. It's simple enough that I won't even bother giving an explanation so as not to insult your intelligence. If you're having trouble understanding the t.forward line, I explain that construction in my explanation for the Dragon Curve Fractal in Turtle (my first post).

import turtle
t = turtle.Pen()

def koch(dist):
    for angle in (60, -120, 60, 0):
        (t.forward if dist <= 10 else koch)(dist / 3.0)  # 10 is the break case. 3.0 is the line:subline ratio
        t.left(angle)

koch(400)

Simulating a Conditional Expression via a List Indexed by a Boolean

It is often the case that you need to shave off just a few characters off a piece of code (there are many competitions where code length is restricted, such as the JS1K competition). The following describes a good way to condense conditional expressions. NOTE: This method only works if your condition returns True or False, or 1 and 0. It will not work if your condition returns, say, a non-zero value for True.

This is what it looks like:

first if condition else second

is equivalent to

[second, first][condition]

This works because condition will return True or False; True in Python is equivalent to 1 and False is equivalent to 0. We then use this 1 or 0 as the index to a list containing first and second; if the condition returns 0, we get the 0th item of the list: second. If it returns 1, we get the 1st item: first.

Pretty neat, huh?

EDIT 05/08/11: True conditional expressions only evaluate the output term. To get this effect, wrap each term in a lambda and call the entire expression's result.

[lambda: second, lambda: first][condition]()

Using reduce() to Implement map() and filter()

map() and filter() are by far the most popular of the big three higher-order functions that Python borrowed from functional programming. reduce(), the most convoluted and intricate of the three, has sadly been removed as a built-in in Python 3.0, forcing us to write neater code. Fortunately map() and filter() were both kept, even though list comprehensions are far easier to understand. There is hope for us yet!

map() is a very rigid function -- its behaviour is very easy to predict because it does exactly what it looks like it does. filter(), too, has very limited use and has a single specific purpose (filtering). map()'s usage has no overlap with filter()'s and vice versa.

reduce() is the odd one out -- it's incredibly flexible and fun to use. In fact, reduce() can be used as a replacement for both map() and filter().

def map(f, list):
    return reduce(lambda p, n: p + [f(n)], 
                  [[]] + list)

def filter(f, list):
    return reduce(lambda p, n: p + ([n] if f(n) else []), 
                  [[]] + list)

Off the top of my head I can't think of a way to accomplish either of these tasks without sticking a [] at the start of list. If you have a way, please comment!

Selecting an Optimal Next Move in Nim

Nim is a mathematical game where you have a number of piles and each pile contains a number of items. Players take turns at each taking at least one and at most all of the items from a single pile of their choosing. The winning player in nim (in its standard form) is the player who has left all piles empty following their move. Nim is traditionally played with 3 piles of 3, 4, and 5 items.

The way to guarantee a win is to always pick a move such that after the move has been executed, the binary digital sum (nim-sum) of each pile is equal to 0. The binary digital sum is the sum of the binary forms of the numbers, without carrying. This turns out to be the same as applying the exclusive-or bitwise operation over all piles.

Given the number of items in each pile, determine the optimal move you should execute in the form (pile to remove from, number of items to remove).
To calculate the nim-sum of the piles we have to apply XOR over all the piles. The easiest way to do this is with the reduce() function. If you haven't encountered reduce() before, it comes from the same functional roots as map() and filter(), but its purpose is to condense a list of type t into a single instance of t** by applying a function between each successive pair and 'folding' itself up. Here's an example of the sum() function implemented as a reduction:

>>> print reduce(lambda a, b: a + b, [1, 2, 4, 8])
15

This is evaluated as (((1 + 2) + 4) + 8). To get the nim sum, we apply a very similar procedure except instead of using a function to add two numbers together, we'll use a function to get the exclusive-or of two numbers. Fortunately Python's already given one to us: int.__xor__. The nim-sum of a game state is therefore:

nim_sum = reduce(int.__xor__, state)

But this is only half the job! We need to go through all possible moves we can make and find one that would leave the game state with a nim-sum of 0.

We're not too concerned about efficiency so we're gonna loop through every possible pile and for each pile, try to remove every possible number of items and see if any of the remaining game states have a nim-sum of 0. The game state will be represented as a list where each element represents the number of items in that pile. The following line of code will give us the result of removing num items from the pile pile:

game[:pile] + [game[pile]-num] + game[pile+1:]

All we're doing is modifying the selected pile then sandwiching the result in between the rest of the piles where it was before.

When you combine all this and add two loops you have yourself a function which, given a game state, will give you a move you can make which results in a nim-sum of 0.

def nextMove(g):
    for p in xrange(len(g)):
        for n in xrange(1, g[p]+1):
            if reduce(int.__xor__, g[:p] + [g[p]-n] + g[p+1:]) == 0:
                return p, n
    return None, None

---

**This is not always the case -- a reduce can theoretically return any type. However, if it is given a list of [t] it will generally return an instance of t.

Finding All Clauses of a Context-Free Grammar

This question was given in week 3 of the 2009 National Computer Science School (NCSS) Challenge. It remains one of my favourite competition problems.


The task is simple. Given a description of a context-free grammar (CFG) in Backus-Naur Form, generate all productions (clauses) of the CFG. Assume the grammar is not recursive (or else there are an infinite amount of clauses).


The solution revolves around the following two observations:

• If <a> ::= <b> <c> the productions of <a> are the Cartesian product of <b> and <c>
• If <a> ::= <b> | <c> the productions of <a> are the concatenation of <b> and <c>

For the record, | has the lowest precedence. That means that if <a> | <b> <c> | <d>, the solution is the concatenation of <a>, (<b> x <c>), <d>. 


The solution naturally lends itself to two parts. We need to parse the grammar into a 
format we can deal with, then we need to generate the productions.



Parsing



BNF is in a key:value format, so it makes sense to use a dictionary. We can use a nested list format for each definition. A list will contain sublists which were separated by | . It's sorta hard to explain so here's an example:


<word> ::= <a> <b> | <c> <d> | <e> "lol i troll you"


Will become

mapping['<word>'] = [['<a>', '<b>'], ['<c>', '<d>'], ['<e>', '"lol i troll you"']]

Note the fact that an entire string in BNF -- including the surrounding quotation marks. We're gonna use some very simple regular expressions to help us identify <these> and "these".

import re

def parse(grammar):
    mapping = {}

    for definition in grammar.strip().splitlines():
        word, meaning = definition.split('::=') # separate key and value                                                                     
        superList = meaning.split('|')
        newSuperList = []

        for ss in superList:
            newSuperList.append(re.findall(r'(<.*?>|".*?")', ss))

        mapping[word.strip()] = newSuperList

    return mapping

Of course, I'm interested in exciting code, even if I have to be a bit ugly about it.

import re
def parse(g):
    return dict([(w.strip(), [re.findall(r'(<.*?>|".*?")', s) for s in m.split('|')]) for w, m in [d.split('::=') for d in g.strip().splitlines()]])

That's better. Where's the fun in readable code?



Generating



Now this is the fun part. We're gonna solve this problem recursively, simply because this problem is a perfect example of one which at first appears complex but can be defined by a set of simple recursive rules. The two recursive rules are in the introduction above. We must also add our break case: we stop recursing whenever we reach a literal (a string in the BNF).

Our recursive function will take in a single parameter: the current term that we're generating clauses from. It will return a list of strings (technically it will be an iterator of strings), where each string is a possible clause in the CFG. If the term parameter is a literal (it matches the pattern ".*") then we've hit the break case and we return a list containing just that term. Otherwise, we expand the term and recurse deeper by applying our recursive rules.


This is a cool challenge, so I'm going to leave you with two options: either figure out how to program that or try to understand my one-liner here. Have fun!

import itertools
def generate(term):
    return re.findall(r'"(.*?)"', term) if re.match('".*', term) else itertools.chain(*[map(''.join, itertools.product(*map(generate, p))) for p in syntax[term]])

Finally, here is the whole code with a CFG provided as an example. It's a very very simplified English sentence CFG. The code works perfectly and because we use itertools.chain() the returned object will be an iterator.

from itertools import chain, product
from re import match, findall

GRAMMAR = '''                                                                                                                                                                         
<sentence> ::= <noun phrase=""> <verb phrase="">                                                                                                                                            
<noun> ::= "boy " | "troll " | "moon " | "telescope "                                                                                                                                 
<transitive verb=""> ::= "hits " | "sees "                                                                                                                                               
<intransitive verb=""> ::= "runs " | "sleeps "                                                                                                                                           
<adjective> ::= "big " | "red "                                                                                                                                                       
<adverb> ::= "quickly " | "quietly "                                                                                                                                                  
<determiner> ::= "a " | "that " | "each " | "every "                                                                                                                                  
<pronoun> ::= "he " | "she " | "it "                                                                                                                                                  
<noun phrase=""> ::= <determiner> <noun> | <determiner> <adjective> <noun>                                                                                                               
<verb phrase=""> ::= <intransitive verb=""> | <transitive verb=""> <noun phrase="">                                                                                                               
'''

def parse(g):
    return dict([(w.strip(), [findall(r'(<.+?>|".+?")', s) for s in m.split('|')]) for w, m in [d.split('::=') for d in g.strip().splitlines()]])

def generate(term):
    return findall(r'"(.*?)"', term) if match('".*', term) else chain(*[map(''.join, product(*map(generate, p))) for p in syntax[term]])

syntax = parse(GRAMMAR)
print list(generate('<sentence>'))

EDIT: Alright, that was a bit mean of me. Here's an expanded version of the generate() function. Whenever I'm obfuscating I always write it up in an expanded version, get it to work, then compress it. In my idiocy, I deleted my expanded 'working' version, so I'm writing this one up on the spot. Note that this one returns a list instead of an iterator.

def generate(term):
    if match(r'".*"', term):
        # if the term is an ebnf string, return it as a single-item list
        #  but strip off the quotation marks
        return findall(r'"(.*?)"', term)
    else:
        # otherwise, solve this subproblem and return a list containing all 
        solutions = []  # this will contain the function's output
        for toConcatenate in syntax[term]:
            expansions = [generate(toExpand) for toExpand in toConcatenate]
            for subsolutions in product(*expansions):
                solutions.append(''.join(subsolutions))
        return solutions

Train Numbers

The train number game is as follows:


Given a 4-digit 'train number', insert mathematical operators between all digits (no concatenation) in a way such that the expression evaluates to 10.


The 'train' bit refers to the fact that the game is often played on Sydney public transport, where buses and train carriages have 4-digit serial numbers.


The task I gave myself is this: given a train number and only the operators +-*/, find all the possible solutions. No bracketing! The order of operations should be the default mathematical system: division, multiplication, subtraction and addition. I wanted my solution to be as concise as possible. This is the result:

from __future__ import division
import itertools
n = map(int, raw_input())

for c in itertools.product(*('+-*/',)*3):
        s = 7*'%s' % sum(zip(c, n[1:]), (n[0],))
        try:
            if eval(s) == 10:
                print s
        except ZeroDivisionError:
            pass

...and this is the line-by-line breakdown:

from __future__ import division
import itertools

The first import statement makes '/' evaluate all division as decimal division. This is generally unwanted in older Python versions but it's useful here. In Python 3.0+ you won't need it as '/' always does decimal division. itertools is a fantastic library which includes a variety of useful functions implemented as iterators including a Cartesian product function, permutations/combinations functions and a function to chain iterables. I'm using the Cartesian product function in this code.

n = map(int, raw_input())

Take in a string as input (e.g. '4917'), use it as an iterable and map the int() function onto each element, resulting in [4, 9, 1, 7].

for c in itertools.product(*('+-*/',)*3):

Heh, this one's neat. itertools.product takes a variable number of iterable arguments and finds the Cartesian product of the arguments. I want it to find all possible 3 arrangements of the same operators, I'm giving it 3 identical arguments (by conveniently multiplying my argument tuple by 3) then putting a * at the front to unpack the tuple. It expands as the following:

for c in itertools.product('+-*/', '+-*/', '+-*/'):

Cool. Now for the really cool line:

s = 7*'%s' % sum(zip(c, n[1:]), (n[0],))

If you haven't realised yet, what I'm doing is generating all possible expressions as strings then evaluating them. This is the line that formats the string. It's always going to be in the format 'number operator number operator number operator number': 7 different elements, explaining the 7*'%s' bit.


The sum() function can actually take in a second argument. To illustrate how this argument operates, here is my implementation of the sum function (assuming the first argument is always the iterable you're summing):

def sum(iterable, first=0):
    curSum = first
    for item in iterable:
        curSum += item
    return curSum

So if you want to use sum() to concatenate a list of tuples as I do and you don't supply an argument for the first parameter, the function will default it to 0 then throw an error when it tries to add a tuple to an int. Obviously this could be avoided if the Python implementation of the function was a bit smarter:

def sum(iterable):
    curSum = iterable[1]
    for item in iterable[1:]:
        curSum += item
    return curSum

I don't know why they don't do that. Anyway, what I'm doing is concatenating a bunch of tuples. The tuples I'm concatenating are generated by the zip() function. Zipping is simple: given two iterables, it makes a list of tuples containing respective pairs. For example, zip([1,2], [3,4]) = [(1,3), (2,4)]. The length of the zipped list is the minimum of the length of the two input lists.


Assume the train number is 3149. My code zips the operators with the tail of the train number as follows: zip(['+', '*', '*'], [1, 4, 9]), resulting in [('+', 1), ('*', 4), ('*', 9)].  It then concatenates these tuples using sum(), where the first sum argument is a single-item tuple containing the head of the train number. The result will be the 'sum' (concatenation) of [(3,), ('+', 1), ('*', 4), ('*', 9)]: (3, '+', 1, '*', 4, '*', 9). Conveniently, this tuple can be piped directly into our format string!


Now we just evaluate our expression using eval() (with some exception handling so div-by-zeros are caught) and output the expression if it evaluates to 10.

Nokia Composer Parser and Compiler (to MIDI)

Grammars (EBNF)

(* MELODY GRAMMAR *)

melody = { pitched_note , ' ' } ;
pitched_note = duration , pitch , octave ;
duration = digit , { digit } , [ '.' ] ;
pitch = '-' | ( [ '#' ] name ) ;
octave = digit ;
name = 'a' | 'b' | 'c' | 'd' | 'e' | 'f' | 'g' ;
digit = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' ;


(* RHYTHM GRAMMAR *)

rhythm = { rhythm_note , ' ' } ;
rhythm_note = duration , drum ;
duration = digit , { digit } , [ '.' ] ;
drum = '-' | drumOnKit ;
drumOnKit = 'sd' | 'bd' | 'ch' | 'oh' | 'ht' | 'mt' | 'lt' | 'cc' | 'rc' ;
digit = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' ;

Parser/Compiler

import re
from midiutil.MidiFile import MIDIFile


DURATION  = r'(\d+[.]?)'
PITCH     = r'(-|(?:#?[abcdefg]))'
OCTAVE    = r'(\d+)?'
DRUM_NOTE = r'(-|(?:sd|bd|ch|oh|ht|mt|lt|cc|rc))'

MELODIC_NOTE_PATTERN  = DURATION + PITCH + OCTAVE
RHYTHMIC_NOTE_PATTERN = DURATION + DRUM_NOTE

INTERVALS_BETWEEN_OCTAVE = 12
INTERVALS = [0, 2, 4, 5, 7, 9, 11]
FIRST_MIDI_KEYBOARD_NOTE = 24
NOTES = 'cdefgab'

PERCUSSION_TRACK = 0

DRUM_TO_MIDI_NUMBER = {'sd' : 38,
                       'bd' : 35,
                       'ch' : 42,
                       'oh' : 46,
                       'ht' : 50,
                       'mt' : 47,
                       'lt' : 41,
                       'cc' : 49,
                       'rc' : 51
                       }
                       

class Piece(object):
    def __init__(self, tempo):
        self.tempo = tempo
        self.melodicTracks = []
        self.drumTracks = []

    def addMelodyTrack(self, melody, volume=100, instrument=1):
        convertedMelody = [PitchedNote(s) for s in melody.split()]

        newTrack = MelodyTrack(melody=convertedMelody, 
                               volume=volume, 
                               instrument=instrument)
        self.melodicTracks.append(newTrack)

    def addDrumTrack(self, drumString, volume=100):
        convertedRhythm = [DrumNote(s) for s in drumString.split()]
        
        newDrumTrack= DrumTrack(melody=convertedRhythm,
                                volume=volume)
        self.drumTracks.append(newDrumTrack)

    def finish(self, outputFileName='output.mid'):
        assert len(self.melodicTracks) + len(self.drumTracks) <= 15

        midi = MIDIFile(len(self.melodicTracks) + 1) 

        midi.addTrackName(PERCUSSION_TRACK, 0.0, 'Drum Track')

        for i in xrange(len(self.drumTracks)):
            self._addTrackToMIDI(midi, 0, self.drumTracks[i])
        for i in xrange(len(self.melodicTracks)):
            print 'adding track', i+1
            self._addTrackToMIDI(midi, i+1, self.melodicTracks[i])

        outputFile = open(outputFileName, 'wb')
        midi.writeFile(outputFile)
        outputFile.close()

        print 'MIDI compiled as', outputFileName

    def _addTrackToMIDI(self, midi, trackNum, track):
        channel = 9 if isinstance(track, DrumTrack) else trackNum

        if not isinstance(track, DrumTrack):
            midi.addTrackName(trackNum, 0.0, 'Track %d' % trackNum)
            midi.addProgramChange(trackNum, channel, 0.0, track.instrument)

        midi.addTempo(trackNum, 0.0, self.tempo)
        
        curPos = 0.0

        for note in track.melody:
            if not note.isRest():
                midi.addNote(trackNum,
                             channel,
                             note.MIDINumber,
                             curPos,
                             note.duration,
                             track.volume)
            curPos += note.duration


class MelodyTrack:
    def __init__(self, **kwds):
        self.__dict__.update(kwds)


class DrumTrack:
    def __init__(self, **kwds):
        self.__dict__.update(kwds)


class Note(object):
    def __init__(self, noteString):
        self.matchSubstrings(noteString)
        self.getDuration()
        if not self.isRest():
            self.getMIDINumber()

    def getDuration(self):
        if self.strings['duration'].endswith('.'):
             self.duration = 4 / float(self.strings['duration'][:-1]) * 1.5
        else:
            self.duration = 4 / float(self.strings['duration'])

    def isRest(self):
        return self.strings['name'].endswith('-')

    def matchSubstrings(self, noteString):
        raise NotImplementedError

    def getMIDINumber(self):
        raise NotImplementedError

    def __str__(self):
        return '<%s %d>' % (str(self.duration), self.MIDINumber)


class PitchedNote(Note):
    def matchSubstrings(self, noteString):
        matchObj = re.match(MELODIC_NOTE_PATTERN, noteString.lower())
        if matchObj == None:
            raise ValueError, 'Not a valid melodic note: ' + repr(noteString)
        self.strings = dict(zip(['duration', 'name', 'octave'], matchObj.groups()))

    def getMIDINumber(self):
        self.MIDINumber = FIRST_MIDI_KEYBOARD_NOTE
        self.MIDINumber += (int(self.strings['octave']) * INTERVALS_BETWEEN_OCTAVE)
        self.MIDINumber += INTERVALS[NOTES.index(self.strings['name'].replace('#',''))]
        self.MIDINumber += self.strings['name'].startswith('#') # compensate for sharpness


class DrumNote(Note):
    def matchSubstrings(self, noteString):
        matchObj = re.match(RHYTHMIC_NOTE_PATTERN, noteString.lower())
        if matchObj == None:
            raise ValueError, 'Not a valid rhythmic note: ' + repr(noteString)
        self.strings = dict(zip(['duration', 'name'], matchObj.groups()))

    def getMIDINumber(self):
        self.MIDINumber = DRUM_TO_MIDI_NUMBER[self.strings['name']]


if __name__ == '__main__':
    print 'You should probably import this so it does something.'

More on this later. Uses the MIDIUtil Python library (I <3 it).


Sample Track

# The Heart Asks Pleasure First
# by Michael Nyman
# Arranged by Daniel Goldbach

import composer

rightHand = '''
8A4 8B3 8C4 8E4 8A4 8B3 
8A4 8B3 8C4 8E4 8B4 8B3
8A4 8B3 8C4 8E4 8G4 8B3
8E4 8B3 8C4 8E4 8B3 8C4

8C5 8E4 8F4 8A4 8C5 8E4
8C5 8E4 8F4 8A4 8E5 8E4
8D5 8E4 8F4 8A4 8C5 8E4
8B4 8E4 8F4 8A4 8C5 8B4

8A4 8B3 8C4 8E4 8A4 8E4
8E5 8E4 8G4 8A4 8C5 8G4
8A4 8B3 8C4 8E4 8G4 8B3
8E4 8A3 8C4 8A3 8D4 8C4

8C4 8A3 8C4 8A3 8D4 8C4
8D4 8A3 8B3 8A3 8D4 8A3
8E4 8B3 8C4 8D4 8#G4 8B3
8A4 8B3 8C4 8E4 8A4 8E4

8A4 8B3 8C4 8E4 8C4 6E4

8E5 8E4 8A4 8E5 8E4 8A4
8E5 8E4 8A4 8D5 8E4 8A4
8C5 8E4 8A4 8C5 8E4 8A4
8E5 8E4 8A4 8C5 8E4 8A4

8E5 8E4 8A4 8E5 8E4 8A4
8E5 8E4 8A4 8D5 8E4 8A4
8C5 8E4 8A4 8C5 8E4 8A4
8A4 8D4 8#F4 8A4 8D4 8#F4

8E5 8E4 8A4 8E5 8E4 8A4
8E5 8E4 8A4 8D5 8E4 8A4
8C5 8E4 8A4 8C5 8E4 8A4
8E5 8E4 8A4 8C5 8E4 8A4

8E5 8E4 8A4 8E5 8E4 8A4
8E5 8E4 8A4 8D5 8E4 8A4
8C5 8E4 8A4 8C5 8E4 8A4
8A4 8D4 8#F4 8A4 8D4 6#F4

''' * 2

leftHand = '''
8A1 8E2 8A2 8E2 8A2 8E2
8A1 8E2 8A2 8E2 8A2 8E2
8A1 8E2 8A3 8E2 8A3 8E2
8A1 8E2 8A3 8E2 8A3 8E2

8F1 8C2 8F2 8C2 8F2 8C2
8F1 8C2 8F2 8C2 8F2 8C2
8G1 8D2 8G2 8D2 8G2 8D2
8G1 8D2 8G2 8D2 8G2 8D2

8A1 8E2 8A2 8E2 8A2 8E2
8A1 8E2 8A2 8E2 8A1 8E2
8A1 8E2 8A2 8E2 8A2 8E2
8A1 8C2 8E2 8C2 8A1 8E2

8A1 8C2 8E2 8C2 8A1 8E2
8E1 8B1 8E2 8D2 8B1 8E1
8E1 8B1 8E2 8B1 8B1 8E1
8A1 8E2 8A2 8E2 8A2 8E2

8A1 8E2 8A2 8E2 8A2 6E2

8C3 8A2 8E2 8A2 8C3 8A2
8B2 8G2 8D2 8G2 8B2 8G2
8A2 8E2 8C2 8E2 8A2 8E2
8A2 8E2 8C2 8E2 8A2 8E2

8C3 8A2 8E2 8A2 8C3 8A2
8B2 8G2 8D2 8G2 8B2 8G2
8A2 8E2 8C2 8E2 8A2 8E2
8A2 8#F2 8D2 8#F2 8A2 8#F2

8C3 8A2 8E2 8A2 8C3 8A2
8B2 8G2 8D2 8G2 8B2 8G2
8A2 8E2 8C2 8E2 8A2 8E2
8A2 8E2 8C2 8E2 8A2 8E2

8C3 8A2 8E2 8A2 8C3 8A2
8B2 8G2 8D2 8G2 8B2 8G2
8A2 8E2 8C2 8E2 8A2 8E2
8A2 8#F2 8D2 8#F2 8A2 6#F2

''' * 2

piece = composer.Piece(170) # 170 is a good tempo for this piece

piece.addMelodyTrack(rightHand)
piece.addMelodyTrack(leftHand, volume=80)

piece.finish(outputFileName='the heart asks pleasure first - michael nyman.mid')

Drawing the Dragon Curve fractal in turtle

The Dragon Curve fractal is one of my favourite fractals. To generate it, imagine an ant given a sequence of instructions containing either "turn left" or "turn right". At every step the ant moves forward then turns either left or right as specified by the instruction.


The sequence in question can be generated with the algorithm described here. I'm not a big fan of this algorithm though, so I came up with my own after looking at the pattern for a bit.


sequence := "r"
FOR i=1 to n:
  sequence = sequence + "r" + reverse(mirror(sequence))


Where 'reverse' reverses the string and 'mirror' flips 'r' to 'l' and vice versa.


To generate the sequence in Python, express the sequence as a list of 1s ('r's) and 0s ('l's). The code follows on from that.

def makeSequence(size):
    seq = [1]
    for i in xrange(size):
        seq += [1] + map(lambda x: not x, seq[::-1])
    return seq

To create the 'mirror' we map the 'not' function onto the boolean list, then we reverse with [::-1] (I'll explain how that works at some point in the future, probably). I think this function would look nice as a list comprehension. If only Python could do lazy evaluation like Haskell can...


As it stands, we now have a sequence. Now to draw it!

def drawCurve(size):
    for instruction in makeSequence(size):
        (t.right if instruction else t.left)(90)
        t.forward(1)

What we're doing here is using a conditional expression to choose between two different functions (the 'turn right' function and 'turn left' function) depending on what the instruction says. The chosen function is then executed with the argument 90 (turn 90 degrees). Good luck finding a style guide which this code passes!


The full code is as follows:

import turtle
t = turtle.Pen()
t.tracer(5000)

def makeSequence(size):
    seq = [1]
    for i in xrange(size):
        seq += [1] + map(lambda x: not x, seq[::-1])
    return seq

def drawCurve(size):
    for instruction in makeSequence(size):
        (t.right if instruction else t.left)(90)
        t.forward(1)

drawCurve(16)

t.tracer(1)
raw_input()

The output image looks something like this:

Success!