What’s That Chord: dusting off some old Python

Some old code

At the end of the summer following my first year at university, I was sitting in Paris Charles de Gaulle airport killing some time before my flight to Scotland to start the new year. I had my laptop out, but couldn’t seem to get wi-fi, so I thought I would put my freshly acquired programming skills to good use—my first year mathematics course had covered some Python—and whip up some code. (The fact that code can run offline never ceases to bring me joy).

As a ukuleleist having played with a band and learnt a lot of new songs over the 2017-2018 year, often painstakingly playing off chord sheets that I was unfamiliar with, my mind must have jumped back to the number of times I’d had to ask how to play a certain chord. (“What’s F#7 again?” was a commonly uttered question when rehearsing Hotel California). I decided to write up a script which would take in a string corresponding to a chord playable on a ukulele, like F#7; and would output a diagram indicating how to play that chord.

I’ll admit that part of the attractiveness of this idea was the recent discovery I’d made that monospace fonts, omnipresent in command line interfaces, lend themselves delightfully well to chord diagrams. Here’s how to play my favourite ukulele chord, Bbadd9:

=======
! ! O !
! O ! !
O ! ! O
! ! ! !
! ! ! !

Anyway, I wrote up a few functions which would contribute to taking in an input string and drawing the corresponding diagram. The approach was:

• Some functions convert the input string to a list of numbers. Ukulele chords don’t care about octaves too much, so it was enough to simply map each of the 12 notes to a number 0-11 and then loop back around mod 12. It seemed ridiculous at the time to choose anything other than C -> 0.
• Represent a chord diagram as a list of fret numbers, e.g. Bbadd9 as above is [3, 2, 1, 3]. Dedicated functions iterate through literally every possible list of length 4 with nonnegative integer entries below a certain cap, and knowing that a ukulele’s standard tuning is [7, 0, 4, 9], calculate the notes played by every possible fret arrangement. We store the ones that play all the notes from the requested chord, and no other notes, in one big list of options.
• We use some ranking functions to assess how easy the chord is to play, mostly based on how spread out one’s fingers would need to be to perform each option. The goal is, for example for C major:

[0,0,0,3]                           [5,4,3,3]
 =======                             =======
 ! ! ! !                             ! ! ! !
 ! ! ! !    is ranked better than    ! ! ! !
 ! ! ! O                             ! ! O O
 ! ! ! !                             ! O ! !
 ! ! ! !                             O ! ! !

• We use a printing function to print to the console the diagram corresponding to the best ranked option.

This approach contained enough brute force to worry almost anyone.

for i1 in range(frets):
    for i2 in range(frets):
        for i3 in range(frets):
            for i4 in range(frets):
                attempt = [(tuning[0]+i1)%12, (tuning[1]+i2)%12, (tuning[2]+i3)%12, (tuning[3]+i4)%12]

And looking back, I see that at the time, I was unaware of simple list manipulation.

def reach(cand):
    candcopy = cand[::]
    try:
        candcopy.remove(0)
        try:
            candcopy.remove(0)
            try:
                candcopy.remove(0)
                return 0
            except ValueError:
                pass
        except ValueError:
            pass
    except ValueError:
        pass
    return max(candcopy) - min(candcopy) + 1

But the beauty of a shoddy, brute-force method like this one is that brute-force still works remarkably well on small inputs. Though the algorithm’s time complexity was a whopping O(number of frets^number of strings), that doesn’t seem so bad when you’re working with an instrument that has 12 frets and 4 strings. I set up automation via keyboard shortcut and for a couple years, I could find any chord I wanted in less than a second.

Re-vamping the project: the danger of pre-emptive optimisation

This summer, I decided it would be about time to revisit my old script and see what changes could be made. I’d just finished a six-week research scholarship with the School of Mathematics and Statistics at the University of St Andrews which was rather software-based, so I was in my honeymoon phase with Git, Vim and the concept of linting. I decided on some goals I wanted my new algorithm to meet:

• It had to work for any stringed instrument with Western tuning and frets. No more nested for loops.
• It had to be easy to use, as much for entering your chord request as for customising your instrument. I wanted presets to be available for various common instruments.
• It had to understand more chords. The original script understood requests of the form XY where X is a note and Y is a chord quality (such as “sus”, “maj7”, “add9″…). An addition in 2019 extended that to XY(Z) where Z is an alteration such as b5. I wanted to add bass notes W as well, for the general form to be XY(Z)/W.
• It had to avoid at least some of the excessive iterations the first script performed when looking for chord solutions.
• Ideally, it would be able to output diagrams in a format different to plain text, such as SVG.
• It had to be better-commented and more easily extensible.
• It had to be tracked via Git so that I could expand on several branches at the same time, have a log of my changes, and share everything on GitHub.

What followed was a lot more work than I expected. Though I kept the general workflow of the original algorithm, not a line of code was re-used. Regular expressions became my friend:

structure = (r"([a-gA-G][b#]?)"
           + r"(\d*[ac-zA-Z\+]*\d*)"
           + r"(\(([b#]+\d+)+\))?"
           + r"(/([a-gA-G][b#]?))?$")

I dropped nested statements for custom iterators:

def increment(maxes, current):
    for i in range(len(maxes)):
        if not current[i] == maxes[i] - 1:
            current[i] += 1
            return
        current[i] = 0

And I ended up splitting the project into several small Python files, rather than one big one, to keep track of different elements of the workflow. Inspired by my canonical rehearsal question— “what’s that chord?”—I named the project ThatChord, surprisingly unused on the internet at that point.

What I didn’t initially realise was that making high-level decisions at the beginning of the project, though important in order to know where you’re going, can leave you spending a lot of time pre-emptively optimising small bits of the project. The first file I worked on was interpret.py, a file containing the sole function interpret.interpret(string), responsible for turning "Cmaj" into [0, 4, 7] and "F#m7" into [1, 4, 6, 9]. But every time I covered ground on my function, I seemed to create more ground yet to cover for myself. I wondered whether the output list should be ordered, and whether that could be of any use later on. As I was working on note alterations—the process through which "C7" returns [0, 4, 7, 10] but "C7(b5)" returns [0, 4, 6, 10], i.e. a flattened fifth—I ended up reconsidering my previous approach and tried to rebuild alteration handling from scratch. The more technical interactions between musical theory and Python in my project raise some interesting questions of this nature, but they’re perhaps a better fit for a later post. Anyway, the gist is that I tried several different things in my first function before even creating the body of the project.

Aside from running the risk of turning the first bit of work into a complete rabbit hole, working so linearly on a project like ThatChord seems to make very little use of the plethora of version control options Git offers. Instead, maybe the best tactic is to decide, early on, how your sub-processes will slot together: where will you store them? How will they take input and output? What parameters will they be given? That way, it takes little work to create a skeleton formed of modular bits, the contents of which you can easily edit later down the line.

Perhaps this is obvious to people who have more experience working on medium to large scale projects—but with no experience in that area, I learnt it the hard way.

The work ethic I converged to once I eventually finished with interpret.py was more breadth-first, and it took me a couple weeks of on-and-off work to get to a version which could actually spit out a result. Some of the files I made later in the timeline made it to the first working version even though they still needed some improvements, and I’m proud to say that I made the most of Git branches at that point to do things like:

• making the instrument configuration file more user-friendly;
• adding some command line options to let you punctually change what instrument you’re using;
• extending the input interpreter to understand not only the XY(Z)/W format mentioned above, but also the XY(Z)/W@V:T format where V and T represent more contextual parameters,
• after some discussion with some friends about tree searching, drastically improving the speed of the core algorithm that actually takes a list of notes and finds the best ways of putting your fingers on the fretboard to play those notes.

Some well-timed speed optimisation

This last point about speed improvement was a result of my exponential-complexity algorithm meeting its limits at the guitar, one of the new instruments that my extension could handle. With two additional strings and many more frets, finding chords on guitar the same way I had been on ukulele brought to light the inefficiency of the original code.

If asking to play C9 on a guitar, my original algorithm would have proceeded as follows. First, note that C9 is made up of 5 notes: C, E, G, Bb, D. Look at the guitar’s lowest string (E) and make a list of all the frets that will play a note from C9: 0, 3, 6, 8, 10, 12, 15, 18. Do the same for the five other strings; this finds more or less the same number of possibilities per string. Now look at every possible combination of fret choices from the created lists of valid frets. Since each list has length around 8, and there are 6 lists (for 6 strings), this is over 200000 combinations. For each one, check what notes are played by each string and store the option in memory if each note in C9 is played on at least one string.

The first issue was that on each of the 200000 iterations, Python was re-computing the list of played notes and re-checking it against the target chord C9 which was meant to be played. But secondly, and more importantly, it was iterating through lots of hopeless combinations. The inner loop was incrementing the lowest string each time (so the E string), and when it got to fret 18, it would start again at fret 0 and increment the next string over.

Imagine the point in the iteration where the current fret positions are (from the lowest to the highest string) 8, 3, 10, 5, 1, 8. In standard EADGBE guitar tuning, this corresponds to playing the notes C, C, C, C, C, C. Clearly this isn’t a C9 chord, which requires not only a C to be present in the list but also an E, a G, a Bb and a D. So the algorithm would discard this and move on, but “moving on” means incrementing the first string so that the configuration is now 10, 3, 10, 5, 1, 8. (The 8 has moved to a 10 since we saw above that on the left E string, frets 8 and 10 play notes from the target chord but 9 does not.) Anyway, the configuration now plays the notes D, C, C, C, C, C, which is still a long way away from containing the full set of notes in the C9 chord. And in fact, incrementing the first string will do nothing to offset the fact that all the other strings are playing only Cs, which won’t get us very far. Getting to the end of the cycle, the first string loops back to 0 and the second increments from 3 to 5. This gives 0, 5, 10, 5, 1, 8, i.e. notes E, D, C, C, C, C, still missing some notes.

In fact, it’s not until we’ve at least changed the fourth string that we may hope to have a set of notes with few enough Cs that the chord C9 will be played. A load of useless iteration happens before then, and so my speed improvement mainly consisted of giving the fret finder the ability to recognise and fast-forward these cases, which resulted in a 6x speedup for guitar chords—now down to about a second. This turned my fret finder from a depth-first tree search into a slightly less bad tree search.

Time spent, in retrospect

A few months after starting this project, I continue to commit changes from time to time but the software is ready to use—and I’ve completely stopped using online chord finders since I’ve had it, just because this version is much more versatile. Despite the discussion of speed improvement above, in retrospect the large majority of my time was spent ensuring that ThatChord was easy to use, rather than running efficiently. Creating an easily modifiable configuration file, a basic command line system with options, good documentation, and a good way of throwing back error messages on bad inputs was a solid 75% of my work, while actually developing the backend which had been so much of the original project was only about 25% of my efforts. Perhaps this is just another one of those things that developers know, and I’ve now learnt it the hard way.

Although I’d gone into this project thinking I’d be able to use some basic but interesting links between music and modular arithmetic, I came out the other end having learnt a lot more about the UI than anything else. Nevertheless, it’s been a great learning experience, and I hope it’ll also be helpful to people one day. If you’re a musician and/or a programmer, then your expertise would be welcome on my GitHub project: github.com/tomcontileslie/ThatChord.