Jumping off after our previous two articles on Voice Leading with Elixir, and Algorithmically Fingering Guitar Chords with Elixir, we’re left with a series of chord voicings ranked according to how well they voice lead from our starting chord, and the set of all possible fingerings for each of these voicings.

Given that our starting chord has a known fingering, which fingering of each of these “best” voicings is the “easiest” to play after our starting chord?

This is an interesting question, and gives us the opportunity to flex our algorithmic muscles again. This time we’ll be basing our solution on a modified version of the Levenshtein distance algorithm for finding the “edit distance” between two strings.

What is “Fingering Distance”?

The term “fingering distance” is my way of referring to how difficult it is to transition from playing one chord on the guitar to another. For example, going from playing a Dm chord on the middle four strings to an Em chord is easy. We just have to slide the shape up two frets.

However, starting on that same Dm chord and playing an Em chord on the top four strings is a more difficult transition. We need to change positions on the fretboard, and every finger in the chord needs to be moved.

---

The family of “edit distance” algorithms tackles a similar problem. How difficult is it to transform one string into another, given a set of operations with fixed costs?

The Levenshtein distance algorithm is an example of an “edit distance” algorithm with three operations: insertion, deletion, and substitution. The Levenshtein distance between kitten and sitting is 3, where the k is substituted for an s, and e is substituted for i, and the g is inserted at the end of the word.

In the classic Levenshtein distance algorithm each of the three basic operations has a unit cost (a cost of 1). This doesn’t always have to be the case. We can modify the algorithm to use our own set of operations, like “place finger”, “lift finger”, “move finger”, and “slide finger” to model how we transition from one chord to another. These operations might have a variable weight, depending on the operation and how far each finger has to move:

• Placing and lifting a finger both seem similarly difficult. Let’s give both of these operations a constant unit cost.

• Moving from the fifth fret, fifth string to the fifth fret, fourth string seems fairly simple, but moving from the fifth fret, fifth string to the second fret, third string would be more difficult. We’ll give the “move finger” operation a weight dependent on the distance we have to move.

• Sliding a finger up or down a string seems to be special sub-case of the “move finger” operation. I would argue that sliding a finger from any fret to any other fret on a string is roughly the same difficult. We’ll give the “slide finger” operation a constant unit cost.

Let’s use this as a jumping off point for building our “fingering distance” calculator.

Calculating Fingering Distance

Let’s start by defining a new module that will hold our new distance/2 function:

defmodule Chord.Distance.Fingering do
  def distance(chord, chord),
    do: 0
end

Obviously, if we pass in two identical chords, the distance between them is 0.

A more interesting case occurs when we’re comparing a chord with one or more notes to an empty list. The total distance between these two “chords” is our “place finger” cost applied to each of the remaining notes in our chord:

def distance(chord, []),
  do:
    chord
    |> Enum.reject(&(&1 == nil))
    |> length

We’ll need to handle the inverse case as well:

def distance([], chord),
  do:
    chord
    |> Enum.reject(&(&1 == nil))
    |> length

The real meat of the algorithm comes into play when it’s time to determine the distance between two non-empty chords:

def distance([note_a | rest_a] = chord_a, [note_b | rest_b] = chord_b),
  do:
    Enum.min([
      distance(rest_a, chord_b) + 1,
      distance(chord_a, rest_b) + 1,
      distance(rest_a, rest_b) + note_distance(note_a, note_b)
    ])

As you can see, our distance/2 function is recursive. At every level of recursion, we calculate the distance required to transform chord_a into chord_b by first:

• Lifting a finger from chord_a.
• Lifting a finger from chord_b.
• Moving note_a to note_b.

The initial choice with the lowest final cost is the choice we pick. Our decision ripples up through our stack until we’re left with the final, minimal cost of transitioning from chord_a to chord_b.

Thank you, Dr. Levenshtein!

Calculating Note Distance

As we’ve seen, both placing and lifting a finger have constant unit costs. The real magic of our fingering distance algorithm happens in the note_distance/2 helper function, where we calculating the cost of moving fingers between frets ands strings.

I find myself producing lots of ranging content from books and articles, like the one you're reading now, to open source software projects. If you like what I'm doing, nothing shows your support more than signing up for my mailing list.

We’ll start with some trivial base cases. If the two notes we’re comparing are the same, the distance between them is 0:

def note_distance(note, note),
  do: 0

If the first “note” is nil, we’re actually being asked for the cost of placing a finger:

def note_distance(nil, _),
  do: 1

Similarly, if the second “note” is nil, we’re being asked how much it costs to lift a finger:

def note_distance(_, nil),
  do: 1

Now things are getting interesting. If we’re asked for the distance between two notes that live on the same string, we’ll report back the unit cost, as we discussed earlier:

def note_distance({_, _, string}, {_, _, string}),
  do: 1

However, if the two notes live on different strings, we’ll treat out guitar’s fretboard like a grid, or city block, and return the “manhattan distance” between the two notes:

def note_distance({fret_a, _, string_a}, {fret_b, _, string_b}),
  do: abs(fret_a - fret_b) + abs(string_a - string_b)

And that’s really all there is to it.

A Few Examples

Going back to our previous examples, going from our Dm on the middle four string set to an Em on the same string should have a cost of 4. We’re just sliding each finger up two frets:

Chord.Distance.Fingering.distance(
  [nil, {5, 1}, {7, 3}, {7, 4}, {6, 2}, nil],
  [nil, {7, 1}, {9, 3}, {9, 4}, {8, 2}, nil]
)

And we do get 4!

The cost of transitioning from that same Dm chord to an Em on the upper four string set should be higher than 4:

Chord.Distance.Fingering.distance(
  [nil, {5, 1}, {7, 3}, {7, 4}, {6, 2}, nil],
  [nil, nil, {2, 1}, {4, 3}, {5, 4}, {3, 2}]
)

And it is! We get a distance of 6.

The Next Best Chord

And now for the grand finale. Let’s say we want to find the set of Cmaj7 voicings that have the best voice leading between our starting G7 chord. This is old hat from our previous articles:

[0, 4, 7, 11]
|> Chord.voicings(4)
|> Enum.map(&{Chord.Distance.Semitone.distance(&1, [nil, 10, 12, 10, 12, nil]), &1})
|> Enum.uniq()
|> Enum.sort()
|> Enum.chunk_by(&elem(&1, 0))
|> List.first()
|> Enum.map(&elem(&1, 1))

But now let’s take each of those voicings and find the best fingering for each with regards to how we’re fingering our G7 chord:

|> Enum.map(fn chord ->
  chord
  |> Chord.fingerings()
  |> Enum.uniq()
  |> Enum.map(
    &{Chord.Distance.Fingering.distance(&1, [nil, {10, 1}, {12, 3}, {10, 1}, {12, 4}, nil]), &1}
  )
  |> Enum.sort()
  |> Enum.map(&elem(&1, 1))
  |> List.first()
end)

Finally, we’ll take each fingered chord and render it to the console:

Our final chords.

Awesome!

Final Thoughts

If you can’t tell, I’m in love with this project. I’ve been playing with it quite a bit in my free time, and I’ve managed to coax it into generating entire progressions for me that sound and play beautifully.

If you’re interested in seeing me put more work into this, and potentially develop it into a fully-functional web application, let me know on Twitter.

If you want to check out the full source code, be sure to check out the Chord project on Github.