A smart way to translate guitar chords into piano sheet music with Python
Tags: python, music, algorithms
Published: 2023-05-19 10:49:22

*&mdash; Hey, can you play song X?*

Just a seemingly innocent question from a random friend who came to a party you are hosting. But hearing it can be really painful if you learned to play the piano in your childhood and still occasionally play just for fun, like I do. Trouble is, I am absolutely useless when it comes to playing by ear, so my only chance of playing something is to get hold of music sheets. Hence my first step would be to go and google "*X* sheet music pdf" or "*X* vocal score pdf" depending on what *X* is. Unfortunately, you often bump into problems like:

1.   The piano score exists, but it only contains the melody itself + some very limited accompaniment. 
2.   The piano score exists, but it is paywalled.
3.   There is simply no version for a piano.

You report your findings to the friend who had asked you to play *X* and they go like:

*&mdash; Oh, what a pity I haven't brought my guitar, I know the chords, it's just that I don't play the piano...*

At this point you probably think to yourself: ah, I learned a bit of music theory long time ago, it would probably be not be too hard to play chords on the piano just by reading their names, or... would it?

It turns out that if you haven't done it before, it's actually much harder than sight-reading a proper music score. You need to think well ahead to mentally decode the chords (which gets even worse if you encounter some unfamiliar notation for the more complex ones), and find a reasonable way to play them with two hands. I can assure you that you are going to find yourself moving hands around the keyboard quite chaotically. Indeed, it's not immediately obvious that in the chord sequence {% katex inline %} \mathrm{D_m\,F\,A_m} {% endkatex %} you can just move one single finger by a tone or semitone instead of shifting the entire hand (or rather, two hands) to the right by a minor or major third. 

This is where I remembered I was a software engineer after all, not a musician. So, instead of practicing I decided to simply write a script that will make my life easier.

The rest of this article is broken into four parts:

1.   Working with guitar chords in Python
2.   Generating a piano score
3.   Optimizing piano chord representation
4.   Assembling everything together

I chose Python as a programming language here because, as you could probably guess, there are myriads of libraries in Python for working with music. I found [`mingus`](https://bspaans.github.io/python-mingus/) to be the simplest for working with guitar chords and [`music21`](https://web.mit.edu/music21/) for generating the piano score. It might be possible though to do everything with music21 only, because it's extremely powerful, but I found mixing the two libraries to be easier than implementing the functionality I needed from mingus with music21.

Anyway, most of the code you'll see below was written using Google Colaboratory as an IDE, you can find the link to it in the end of the article.

## Working with guitar chords

As people say, there's more than one way to skin a cat. Similarly, most chords have several representations for a guitar, even though most amateur guitarists would typically use a single representation of every chord. `mingus` has a nice function that can generate all reasonable ways to play a chord:

```python
from mingus.extra.tunings import get_tuning
from mingus.containers import NoteContainer, Note

guitar_tuning = get_tuning('guitar', 'standard')

guitar_tuning.find_chord_fingering(NoteContainer().from_chord('Dbm6'))
```

{% collapsible output: [[0, 1, 2, 1, 2, 0], ...] %}
```
[[0, 1, 2, 1, 2, 0],
 [0, 1, 2, 1, 2, 4],
 [6, 7, 6, 6, 9, 6],
 [6, 7, 8, 6, 9, 6],
 [6, 7, 6, 6, 9, 9],
 [9, 7, 6, 6, 9, 6],
 [9, 11, 11, 9, 11, 9],
 [12, 11, 11, 13, 11, 12],
 [0, 1, None, 1, 2, 0],
 [0, 1, 2, 1, 2, None],
 [0, 1, None, 1, 2, 4],
 [6, 7, 6, 6, None, 6],
 [6, 7, 6, 6, 9, None],
 [6, 7, 6, 6, None, 9],
 [6, 7, None, 6, 9, 6],
 [9, 7, 6, 6, None, 6],
 [None, 7, 6, 6, 9, 6],
 [9, 11, None, 9, 11, 9],
 [12, 11, 11, None, 11, 12],
 [12, 11, 11, 13, 11, None],
 [None, 11, 11, 13, 11, 12],
 [0, 1, None, 1, 2, None],
 [6, 7, 6, 6, None, None],
 [None, 7, 6, 6, None, 6],
 [12, 11, 11, None, 11, None],
 [None, 11, 11, None, 11, 12]]
```
{% endcollapsible %}

Here the numbers correspond to the positions along the guitar neck for every string. To get the actual pitches corresponding to every finger, we can use `guitar_tuning.get_Note`: 

```python
for fingering in guitar_tuning.find_chord_fingering(NoteContainer().from_chord('Dbm6')):
  chord_pitches = [ guitar_tuning.get_Note(string=i, fret=fingering[i]) if fingering[i] is not None else None for i in range(6) ]
  print(chord_pitches)
```

{% collapsible ['E-2', 'A#-2', 'E-3', 'G#-3', 'C#-4', 'E-4'] ... %}
```
['E-2', 'A#-2', 'E-3', 'G#-3', 'C#-4', 'E-4']
['E-2', 'A#-2', 'E-3', 'G#-3', 'C#-4', 'G#-4']
['A#-2', 'E-3', 'G#-3', 'C#-4', 'G#-4', 'A#-4']
['A#-2', 'E-3', 'A#-3', 'C#-4', 'G#-4', 'A#-4']
['A#-2', 'E-3', 'G#-3', 'C#-4', 'G#-4', 'C#-5']
['C#-3', 'E-3', 'G#-3', 'C#-4', 'G#-4', 'A#-4']
['C#-3', 'G#-3', 'C#-4', 'E-4', 'A#-4', 'C#-5']
['E-3', 'G#-3', 'C#-4', 'G#-4', 'A#-4', 'E-5']
['E-2', 'A#-2', None, 'G#-3', 'C#-4', 'E-4']
['E-2', 'A#-2', 'E-3', 'G#-3', 'C#-4', None]
['E-2', 'A#-2', None, 'G#-3', 'C#-4', 'G#-4']
['A#-2', 'E-3', 'G#-3', 'C#-4', None, 'A#-4']
['A#-2', 'E-3', 'G#-3', 'C#-4', 'G#-4', None]
['A#-2', 'E-3', 'G#-3', 'C#-4', None, 'C#-5']
['A#-2', 'E-3', None, 'C#-4', 'G#-4', 'A#-4']
['C#-3', 'E-3', 'G#-3', 'C#-4', None, 'A#-4']
[None, 'E-3', 'G#-3', 'C#-4', 'G#-4', 'A#-4']
['C#-3', 'G#-3', None, 'E-4', 'A#-4', 'C#-5']
['E-3', 'G#-3', 'C#-4', None, 'A#-4', 'E-5']
['E-3', 'G#-3', 'C#-4', 'G#-4', 'A#-4', None]
[None, 'G#-3', 'C#-4', 'G#-4', 'A#-4', 'E-5']
['E-2', 'A#-2', None, 'G#-3', 'C#-4', None]
['A#-2', 'E-3', 'G#-3', 'C#-4', None, None]
[None, 'E-3', 'G#-3', 'C#-4', None, 'A#-4']
['E-3', 'G#-3', 'C#-4', None, 'A#-4', None]
[None, 'G#-3', 'C#-4', None, 'A#-4', 'E-5']
```
{% endcollapsible %}

Note that the black notes (or, more precisely, notes corresponding to the black keys on the piano keyboard) now always come with a {% katex inline %}\sharp{% endkatex %}, never with a {% katex inline %}\flat{% endkatex %}. The notes for the {% katex inline %}\mathrm{D♭m6}{% endkatex %} chord should technically consist of {% katex inline %}\mathrm{D\flat, F\flat, A\flat, B\flat\kern-1.4pt\flat}{% endkatex %}, while {% katex inline %}\mathrm{C\sharp, E, G\sharp, A\sharp}{% endkatex %} would refer to {% katex inline %}\mathrm{C\sharp m6}{% endkatex %}. This doesn't matter much for a guitar &mdash; after all, the pitches are the same, however, it gets much more important for a piano score since the chords should match the current key signatures. I will show how to address this issue in the next section.

## Generating a piano score

For working with the piano score I am going to use library `music21`.

Here is the most basic way to generate a piano score manually:

```python
import music21 as m21
sc1 = m21.stream.Score()
right_hand = m21.stream.PartStaff()
left_hand = m21.stream.PartStaff()
right_hand.append(m21.key.Key('Ab', 'major'))
right_hand.append(m21.note.Note('D-4'))
right_hand.append(m21.note.Note('F-4'))
right_hand.append(m21.note.Note('A-4'))
right_hand.append(m21.note.Note('B--4'))
left_hand.append(m21.chord.Chord(
    [m21.note.Note('D-3'), m21.note.Note('A-3')],
    duration=m21.duration.Duration(4)))
sc1.insert(0, right_hand)
sc1.insert(0, left_hand)
sc1.insert(0, m21.layout.StaffGroup([right_hand, left_hand], symbol='brace'))

sc1.show()
```

![Output of the code above](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/18upft9wc2cte2fbe25l.png)

You can already notice some differences between `music21` and `mingus` in the way they represent notes:

1.   `music21` uses `#` or `-` for alteration marks;
2.   `mingus` uses `#` and `b`, while `-` is just a separator between a note and an octave.

This may create a funny effect if you try to simply map notes by name from one library to another:

```python
mingus_note = Note('A-6')
print(mingus_note.to_hertz())
print(m21.pitch.Pitch(str(mingus_note).strip("'")).freq440)  # BAD!
print(m21.pitch.Pitch(mingus_note.name, octave=mingus_note.octave).freq440) # GOOD
print()

# Music21 can parse flats at the input (bemols)
mingus_note = Note('Db-5')
print(mingus_note.to_hertz())
print(m21.pitch.Pitch(mingus_note.name, octave=mingus_note.octave).freq440)
print()

# ... but not double-flats.
mingus_note = Note('Dbb-5')
print(mingus_note.to_hertz())
try:
  print(m21.pitch.Pitch(mingus_note.name, octave=mingus_note.octave).freq440)
except Exception as e:
  print(e)
```

Output of the above block is:
```
1760.0
1661.218790319782
1760.000000000002

554.3652619537442
554.3652619537443

523.2511306011972
bb is not a supported accidental type
```

Now let's define some simple language to describe our sequence of chords: every chord will be specified as `duration:chord_symbol`, where `duration` is specified in crotchets (quarters) and `chord_symbol` is in guitar notation:

`4:Am 4:H7 2:E 2:E7 8:Am 4:H7 2:E 2:E7 4:Am`

You might be puzzled by the H note here - yes, this song apparently follows the German chord notation tradition. The only important difference between between German and English note names is about B and H:

|  English         |  German      |
|------------------|--------------|
|{% katex inline %}\mathrm{B}{% endkatex %}      | {% katex inline %}\mathrm{H}{% endkatex %} |
|{% katex inline %}\mathrm{B\flat}{% endkatex %} | {% katex inline %}\mathrm{B}{% endkatex %} | 

Converting from German to English is then pretty trivial:

```python
def de_germanize(chord_sym: str):
    if chord_sym.startswith('B'):
        return 'Bb' + chord_sym[1:]
    if chord_sym.startswith('H'):
        return 'B' + chord_sym[1:]
    return chord_sym
```

Here is what we will do &mdash; take the first fingering proposed by `mingus`, play the lower 3 strings with the left hand and the upper 3 strings with the right hand.

{% details code %}
```python
from typing import Tuple, Sequence, List, Optional, NamedTuple

def notes_from_fingering(fingering: Sequence[int]) -> Tuple[Optional[m21.pitch.Pitch]]:
  result = []
  for i, fret in enumerate(fingering):
    if fret is None:
      result.append(None)
      continue
    mingus_note = guitar_tuning.get_Note(string=i, fret=fret)
    # Here mingus_note.name be one of: C, C#, D, D#, E, F, F#, G, G#, A, A#, B.
    pitch = m21.pitch.Pitch(mingus_note.name, octave=mingus_note.octave)
    result.append(pitch)
  return tuple(result)


def chord_or_rest_from_notes(notes: Sequence[m21.pitch.Pitch], **kwargs) -> m21.note.GeneralNote:
  if notes:
    return m21.chord.Chord(notes=notes, **kwargs)
  else:
    return m21.note.Rest(**kwargs)


def get_harmony_symbol_from_name(chord_name):
  if chord_name[1:].startswith('b'):
      chord_name = chord_name[0:1] + '-' + chord_name[2:]
  return m21.harmony.ChordSymbol(figure=chord_name)


def init_score_and_hands() -> Tuple[m21.stream.Score, m21.stream.PartStaff, m21.stream.PartStaff]:
  score = m21.stream.Score()
  right_hand = m21.stream.PartStaff()
  left_hand = m21.stream.PartStaff()
  # Force treble clef in right hand and bass clef in left hand.
  right_hand.append(m21.clef.TrebleClef())
  left_hand.append(m21.clef.BassClef())
  score.insert(0, right_hand)
  score.insert(0, left_hand)
  score.insert(0, m21.layout.StaffGroup([right_hand, left_hand], symbol='brace'))
  return score, left_hand, right_hand


class ChordForTwoHands(NamedTuple):
  left_hand_notes: Tuple[m21.pitch.Pitch]
  right_hand_notes: Tuple[m21.pitch.Pitch]


def get_hands_from_notes(notes: Sequence[Optional[m21.pitch.Pitch]]) -> ChordForTwoHands:
  return ChordForTwoHands(
      left_hand_notes=tuple(n for n in notes[:3] if n is not None),
      right_hand_notes=tuple(n for n in notes[3:] if n is not None)
  )


def score_from_chords(chords_string):
  score, left_hand, right_hand = init_score_and_hands()
  for token in chords_string.split():
    dur, chord_symbol = token.split(':')
    duration = m21.duration.Duration(quarterLength=float(dur))
    chord_symbol = de_germanize(chord_symbol)
    mingus_chord = NoteContainer().from_chord(chord_symbol)
    fingerings = guitar_tuning.find_chord_fingering(mingus_chord)
    notes = notes_from_fingering(tuple(fingerings[0]))
    harmony = get_harmony_symbol_from_name(chord_symbol)
    right_hand.append(harmony)
    chord_2h = get_hands_from_notes(notes)
    right_hand.append(chord_or_rest_from_notes(chord_2h.right_hand_notes, duration=duration))
    left_hand.append(chord_or_rest_from_notes(chord_2h.left_hand_notes, duration=duration))
  return score

score_from_chords('2:Gm 2:A7 2:Dm 2:B 2:Gm 2:Gm6 2:A7 2:Dm').show()
```
{% enddetails %}

![Output of the code above](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/2lkypylmxlqb2brojv7s.png)

As expected, going through chord → fingering → pitches → chord sequence, we lost all  information about the chords' correct alteration marks. In the example above you can notice {% katex inline %}\mathrm{B\flat}{% endkatex %} is represented as {% katex inline %}\mathrm{A\sharp}{% endkatex %}. So let's try to get things right by altering the notes in the chord to valid enharmonics:

{% details code %}
```python
def find_enharmonic_from_list(pitch: m21.note.Pitch, allowed_note_names: Sequence[str]):
    if pitch.name in allowed_note_names:
        return pitch
    for enharmonic in pitch.getAllCommonEnharmonics():
        if enharmonic.name in allowed_note_names:
            return enharmonic
    assert(False)


def fix_enharmonisms(pitches: Sequence[Optional[m21.pitch.Pitch]], harmony: m21.harmony.ChordSymbol):
  allowed_note_names = [pitch.name for pitch in harmony.pitches]
  return tuple(
      pitch and find_enharmonic_from_list(pitch, allowed_note_names)
      for pitch in pitches
  )


def score_from_chords(chords_string):
  score, left_hand, right_hand = init_score_and_hands()
  for token in chords_string.split():
    dur, chord_symbol = token.split(':')
    duration = m21.duration.Duration(quarterLength=float(dur))
    chord_symbol = de_germanize(chord_symbol)
    mingus_chord = NoteContainer().from_chord(chord_symbol)
    fingerings = guitar_tuning.find_chord_fingering(mingus_chord)
    notes = notes_from_fingering(fingerings[0])    
    harmony = get_harmony_symbol_from_name(chord_symbol)
    right_hand.append(harmony)
    notes = fix_enharmonisms(notes, harmony)
    chord_2h = get_hands_from_notes(notes)
    right_hand.append(chord_or_rest_from_notes(chord_2h.right_hand_notes, duration=duration))
    left_hand.append(chord_or_rest_from_notes(chord_2h.left_hand_notes, duration=duration))
  return score

score_from_chords('2:Gm 2:A7 2:Dm 2:B 2:Gm 2:Gm6 2:A7 2:Dm').show()
```
{% enddetails %}


![Output of the code above](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/qgailhtvzdonny0bwh9v.png)

This is much better, but we still have no control over the time signature &mdash; it's {% katex inline %}\mathrm{\frac{4}{4}}{% endkatex %} by default, or the key signature &mdash; it's {% katex inline %}\mathrm{C}{% endkatex %} (or rather, {% katex inline %}\mathrm{Am}{% endkatex %}, like in the example above). To correct this we will allow adding arbitrary [TinyNotation](https://web.mit.edu/music21/doc/usersGuide/usersGuide_16_tinyNotation.html) elements to both staves. Since TinyNotation does not support key changes, we will extend its functionality.

The new parser will support score description like this:

`[kDm 3/4] 2:F 1:Gm 1:Am 2:AmM7 6:Dm`

Also, while we are at it, let's also separate parsing and rendering, because later we will have an optimization step between them:

{% details More code %}
```python
import re
import functools
import copy

class KeyToken(m21.tinyNotation.Token):
    def parse(self, parent):
        keyName = self.token
        return m21.key.Key(keyName)
 

class BaseElement:
  def add_to_score(self, score: m21.stream.Score): ...


@functools.cache
def get_harmony_and_implementations(chord_symbol: str):
  harmony = get_harmony_symbol_from_name(chord_symbol)
  mingus_chord = NoteContainer().from_chord(chord_symbol)
  return harmony, tuple(
      get_hands_from_notes(
          fix_enharmonisms(
              notes_from_fingering(fingering),
              harmony
          ),
      )
      for fingering in guitar_tuning.find_chord_fingering(mingus_chord)
  )


class ChordElement(BaseElement):

  def __init__(self, token: str):
    duration, chord_symbol = token.split(':')
    self.duration = m21.duration.Duration(quarterLength=float(duration))
    chord_symbol = de_germanize(chord_symbol)
    self.harmony, self.implementations = get_harmony_and_implementations(chord_symbol)
    self.best_implementation_index = 0

  def add_to_score(self, score: m21.stream.Score):
    chord_2h = self.implementations[self.best_implementation_index]
    right_hand, left_hand = score.parts
    right_hand.append(copy.deepcopy(self.harmony))  # Copy to prevent "object already added"
    right_hand.append(chord_or_rest_from_notes(chord_2h.right_hand_notes, duration=self.duration))
    left_hand.append(chord_or_rest_from_notes(chord_2h.left_hand_notes, duration=self.duration))


class MetadataElement(BaseElement):
  def __init__(self, title: str):
    self.metadata = m21.metadata.Metadata(title=title)
  
  def add_to_score(self, score: m21.stream.Score):
    score.insert(0, self.metadata)


class RemarkElement(BaseElement):
  def __init__(self, text: str):
    self.expression = m21.expressions.TextExpression(text)
    self.expression.placement = 'above'
  
  def add_to_score(self, score: m21.stream.Score):
    score.parts[0].append(self.expression)


class TinyNotationElement(BaseElement):
  def __init__(self, token: str):
    assert(token[0] == '[' and token[-1] == ']')
    tnc = m21.tinyNotation.Converter(makeNotation=False)
    tnc.tokenMap.append((r'k(.*)', KeyToken))
    tnc.load(token[1:-1])
    tnc.parse()
    self.stream = tnc.stream
    
  def add_to_score(self, score: m21.stream.Score):
    for sub_element in self.stream:
      for part in score.parts:
        part.append(sub_element)


def parse_chords(chords_string: str) -> List[BaseElement]:
  result = []
  PATTERNS = (
      ('TINY', r'\[[^\]]+\]'),
      ('TITLE', r'TITLE\[(?P<TITLE_TEXT>[^\]]+)\]'),
      ('REMARK', r'REMARK\[(?P<REMARK_TEXT>[^\]]+)\]'),
      ('CHORD', r'\d+(\.\d*)?:\S+'),
      ('SPACE', r'\s+'),
      ('ERROR', r'.')
  )
  full_regex = '|'.join(f'(?P<{kind}>{expression})' for kind, expression in PATTERNS)
  for mo in re.finditer(full_regex, chords_string):
    token = mo.group()
    kind = mo.lastgroup
    if kind == 'TINY':
      result.append(TinyNotationElement(token))
    elif kind == 'TITLE':
      result.append(MetadataElement(mo.group('TITLE_TEXT')))
    elif kind == 'REMARK':
      result.append(RemarkElement(mo.group('REMARK_TEXT')))
    elif kind == 'CHORD':
      result.append(ChordElement(token))
    elif kind == 'SPACE':
      pass
    else: # Error
      raise RuntimeError(f'Unexpected token at position {mo.start()}: "{chords_string[mo.start():]}"')
  return result
```
{% enddetails %}

```python
def score_from_chords(chords_string: str):
  elements = parse_chords(chords_string)

  score, _, _ = init_score_and_hands()
  for element in elements:
    element.add_to_score(score)
  return score

score_from_chords('TITLE[Song of a page] [kDm 3/4] 2:F 1:Gm 1:Am 2:AmM7 REMARK[Arpeggios] 6:Dm').show()
```

![Output of the code block above](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/jntyf5kdi5op7kqd1bkn.png)

## Optimizing piano chord representation

In order to select the optimal chord sequence we will use the following model:
1. Every chord implementation will have its associated computed difficulty.
2. Transition between two chord implementations following each other in the score will also have a computed difficulty.

We aim to minimize the total difficulty of all chords and transitions. This can be done using a dynamical programming approach or shortest path search in a graph.

Anyway, let's start with chord difficulty, because then the optimization becomes trivial - just select the best chord out of the list:

{% details code describing various components of chord difficulty %}
```python
def chord_length_penalty(chord_2h: ChordForTwoHands) -> int:
  num_notes = len(chord_2h.left_hand_notes) + len(chord_2h.right_hand_notes)
  # Prefer chords with 5 notes across both hands and but force at least 3.
  return [400, 300, 200, 15, 5, 0, 2][num_notes]

def clef_mismatch_penalty(chord_2h: ChordForTwoHands) -> int:
  middle_c = m21.pitch.Pitch('C4')
  req_bars = 0
  if chord_2h.left_hand_notes:
    req_bars += max(chord_2h.left_hand_notes[-1].diatonicNoteNum - middle_c.diatonicNoteNum, 0)
  if chord_2h.right_hand_notes:
    req_bars += max(middle_c.diatonicNoteNum - chord_2h.right_hand_notes[0].diatonicNoteNum, 0)
  return req_bars * 3


def duplicate_note_penalty(chord_2h: ChordForTwoHands) -> int:
  all_notes = chord_2h.left_hand_notes + chord_2h.right_hand_notes
  # Make sure we don't attempt to put the same 
  if len(all_notes) != len(set(x.diatonicNoteNum for x in all_notes)):
    return 100
  return 0


def is_white_key(p: m21.pitch.Pitch) -> bool:
  return p.pitchClass not in (1, 3, 6, 8, 10)


def rakhmaninoff_penalty(pitches: Sequence[m21.pitch.Pitch]) -> int:
  if not pitches:
    return 0
  # Slightly penalize chords above one octave in span.
  if pitches[0].ps - pitches[-1].ps > 12.0:
    return 1
  else:
    return 0


def black_thumb_penalty(pitches: Sequence[m21.pitch.Pitch]) -> int:
  if len(pitches) < 2 or is_white_key(pitches[0]):
    return 0
  if len(pitches) == 2 and pitches[0].ps - pitches[1].ps <= 7.0:
    # Assume that up to pure fifth we can play the interval with other fingers.
    return 0
  else:
    return 4


def black_pinkie_penalty(pitches: Sequence[m21.pitch.Pitch]) -> int:
  # Penalize 5th finger on black keys when the middle key is white
  if len(pitches) < 3:
    # No middle key means many good options to play it.
    return 0
  if is_white_key(pitches[-1]) or not is_white_key(pitches[-2]):
    return 0
  return 6


def hand_penalty(pitches: Sequence[m21.pitch.Pitch]) -> int:
  return rakhmaninoff_penalty(pitches) + black_thumb_penalty(pitches) + black_pinkie_penalty(pitches)
```
{% enddetails %}

```python 
# Since get_harmony_and_implementations is also cached,
# We will only compute difficulty per every chord implementation at most once.
@functools.cache
def chord_difficulty(chord_2h: ChordForTwoHands) -> float:
  return (
      hand_penalty(chord_2h.left_hand_notes) +
      hand_penalty(chord_2h.right_hand_notes[::-1]) +
      duplicate_note_penalty(chord_2h) +
      chord_length_penalty(chord_2h) +
      clef_mismatch_penalty(chord_2h)
  )


def optimize_chords(elements: Sequence[BaseElement]):
  for element in elements:
    if isinstance(element, ChordElement):
      difficulties = list(map(chord_difficulty, element.implementations))
      element.best_implementation_index = min(range(len(difficulties)), key=difficulties.__getitem__)


def score_from_chords(chords_string: str):
  elements = parse_chords(chords_string)
  optimize_chords(elements)

  score, _, _ = init_score_and_hands()
  for element in elements:
    element.add_to_score(score)
  return score

score_from_chords('2:Gm 2:A7 2:Dm 2:B 2:Gm 2:Gm6 2:A7 2:Dm').show()
```


![Output of the code block above](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ojucy3m7k13y7704jlja.png)

Let's now model the difficulty of moving the hands between two chords. We will assume that the distance between the chords is the same as the sum of distances between their corresponding notes. This obviously wouldn't work if the chords have different lengths, so we will try to match notes from one chord to another using dynamic programming:

```python
import numpy as np

def pitch_distance(first: m21.pitch.Pitch, second: m21.pitch.Pitch):
  return abs(int(first.ps) - int(second.ps))

def hand_distance(first: Sequence[m21.pitch.Pitch], second: Sequence[m21.pitch.Pitch]):
  if len(first) < len(second):
    first, second = second, first
  n = len(first)
  m = len(second)
  # m <= n
  ADD_REMOVE_PENALTY = 1
  d = np.ones((n + 1, m + 1), dtype=int) * 100000
  d[:, 0] = np.arange(n + 1) * ADD_REMOVE_PENALTY
  for i in range(1, n + 1):
    for j in range(1, m + 1):
      d[i, j] = min(
          d[i - 1, j] + ADD_REMOVE_PENALTY,
          d[i-1, j-1] + pitch_distance(first[i - 1], second[j - 1])
      )
  return d[n, m]

@functools.cache
def chord_distance(previous_chord_2h: ChordForTwoHands, current_chord_2h: ChordForTwoHands) -> int:
  return (
      hand_distance(previous_chord_2h.left_hand_notes, current_chord_2h.left_hand_notes) +
      hand_distance(previous_chord_2h.right_hand_notes, current_chord_2h.right_hand_notes)
  )
```

Let's denote complexity of an individual chord implementation (`chord_difficulty`) as {% katex inline %}c(X){% endkatex %} and complexity of the transition between two chords (`chord_distance`) as {% katex inline %}d(X, Y){% endkatex %}. Let {% katex inline %}w(X, Y){% endkatex %} be {% katex inline %}c(Y) + d(X, Y){% endkatex %}. Then the graph used for optimization of the chord sequence will look like this:

![Graph for chord optimization using shortest paths](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/cpq1by90qgaofkd2u25d.png)

Our optimization problem now becomes equivalent to finding a shortest path in this graph. I am using an implementation of Dijkstra algorithm from module `networkx` here, but due to the nature of the graph (it has not cycles and has an apparent topological order) I would not be surprised if you found a more efficient approach.

{% details code %}
```python
import networkx as nx

def optimize_chords(elements: Sequence[BaseElement]):
  graph = nx.DiGraph()
  graph.add_node('source')
  last_layer = ['source']

  for index, element in enumerate(elements):
    if isinstance(element, ChordElement):
      new_last_layer = []
      for impl_idx, impl in enumerate(element.implementations):
        n = f'{index}-{impl_idx}'
        graph.add_node(n, element=element, implementation_index=impl_idx, implementation=impl)
        for prev_node in last_layer:
          graph.add_edge(prev_node, n)
        new_last_layer.append(n)
      last_layer = new_last_layer

  graph.add_node('target')
  for n in last_layer:
    graph.add_edge(n, 'target')
  # Use weight function instead of explicit vertex/edge weights because
  # this will allow to perform difficulty/distance computation lazily.
  def weight_func(u, v, e):
    u_attr = graph.nodes[u]
    v_attr = graph.nodes[v]
    KEY = 'implementation'
    if KEY in v_attr:
      w = chord_difficulty(v_attr[KEY])
      if KEY in u_attr:
        w += chord_distance(u_attr[KEY], v_attr[KEY])
      return w
    else:
      return 0 
  path = nx.algorithms.dijkstra_path(graph, 'source', 'target', weight=weight_func)
  for node in path:
    attrs = graph.nodes[node]
    if 'element' in attrs:
      attrs['element'].best_implementation_index = attrs['implementation_index']

score_from_chords('2:Gm 2:A7 2:Dm 2:B 2:Gm 2:Gm6 2:A7 2:Dm').show()
```
{% enddetails %}


![Output of the code block above](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/r2ymmysigfyz41v0a9su.png)

## Assembling everything together

We are finally ready to give this a test on a complete song:

```python
score = score_from_chords("""
TITLE[Song of a page]
REMARK[transpose up by one tone (+2),
if the instrument supports it]

[kAm]

4:Am 4:H7 2:E 2:E7 8:Am
4:H7 2:E 2:E7 4:Am
2:Dm 2:G7 2:C 2:F 2:Dm 2:E7 4:Am
2:Gm 2:A7 2:Dm 2:B 2:Gm 2:Gm6 2:A7 2:Dm REMARK[(da capo)] [2/4] 2:Dm6
REMARK[(ending)] [4/4] 4:Gm 4:H7 4:E7 1:Am 1:E 2:Am
""").show()
```


![Full score](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ugzsa0m4wmenn7g9vqhj.png)

The complete code can be found [here](https://gist.github.com/Dlougach/cc0e18ed1ec09263f4a174e4abeb9e28), feel free to copy and play with it.

This article is meant to show a proof of concept. Therefore it is entirely expected that this code won't cater for every song. Here are some of the important lacking features in this prototype:


1.   Chords with a bass notation (like {% katex inline %}\mathrm{E/A}{% endkatex %})
1.   Rests
1.   Lyrics
1.   Repeats (then the whole optimization problem becomes harder)
1.   Adjusting the length of the chord to its duration

Some of those are relatively trivial to implement, while  others (such as bass notation and repeats) require much deeper changes and potentially even a complete redesign of the whole approach.

Nevertheless, thank you very much for reading until the very end and I would be very glad if I managed to inspire you to write some code for music generation or even just to clean some dust off whatever music instrument you can play.