Consider the following problem. You want to create a binary sequence of \(n\) bits, out of which \(k\) are one (and the rest are of course zero). You also want the ones to be as evenly spread as possible among the zeroes. If \(k\) divides \(n\), then the solution is straightforward; we just divide the ones among the zeros. For example, for \(n = 16\) and \(k = 4\) we get the sequence:

```
[ 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 ]
```

The problem gets more interesting when \(n\) and \(k\) are relatively prime, that is, when the only common divisor of \(n\) and \(k\) is the number 1.

So suppose that we have \(n = 13\) and \(k = 5\). As we have \(13 - 5 = 8\), we start by creating a sequence with 5 ones and 8 zeroes:

```
[ 1 1 1 1 1 0 0 0 0 0 0 0 0 ]
```

We can treat this sequence as 13 sequences of one bit each:

```
[ [1] [1] [1] [1] [1] [0] [0] [0] [0] [0] [0] [0] [0] ]
```

We distribute the zeroes so that we get five sequences of two bits each, and three sequences of one bit:

```
[ [1 0] [1 0] [1 0] [1 0] [1 0] [0] [0] [0] ]
```

Then we distribute the remaining zeroes in the same way, so that we get:

```
[ [1 0 0] [1 0 0] [1 0 0] [1 0] [1 0] ]
```

Now we distribute the `[1 0]`

sequences, which leads to:

```
[ [1 0 0 1 0] [1 0 0 1 0] [1 0 0] ]
```

The process ends when the remainder (that is, the sequences with the smallest number of bits) is exactly one, or we do not have any more zeroes to distribute. Then we concatenate the result. In our example, we get:

```
[ 1 0 0 1 0 1 0 0 1 0 1 0 0 ]
```

We can interpret the above sequence as a rhythm, where each digit is a
unit of time and each `0`

shows a silence (or unaccented note), while
each `1`

shows an attack, or an onset of a note. Then, for different
relatively prime \(n\) and \(k\) we get a wealth of rhythms that are used
in world music. Two examples:

- The rhythm with \(k = 3\) and \(n = 7\), \([\ 1\ 0\ 1\ 0\ 1\ 0\ 0\ ]\), is the Ruchenitza (Rachenitsa, Ръченица, Rŭchenitsa, Râčenica) rhythm that is used in Bulgarian folk musing and in the Pink Floyd song Money.
- The rhythm with \(k = 5\) and \(n = 9\), \([\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ ]\), is a popular Arabic rhythm called Agsag Samai. If started on the second onset, it is drum pattern used by the Venda people in South Africa, as well as a Romanian folk dance. It is also the rhythm pattern of the Greek Sigaktistos. [ This is according to the bibliography. The author, being Greek, does not know any rhythm by that name. A student, Marios Pitsalidis, suggested that perhaps the correct name is Sigkathistos, Συγκαθιστός, meaning "sitting together," which probably makes sense. If somebody knows more, please contact the author. ] The Turkish Samai Aktsak follows the same pattern as well. If started on the third onset, it is the rhythmical pattern of the Turkish Nawahiid rhythm.

### Euclidean Rhythms and Euclidean Strings

The way we outlined for constructing these rhythmical sequences for
different \(k\) and \(n\) follows Euclid's algorithm for finding the
greatest common divisor of two numbers. Indeed, if `euclid(n, k)`

is a
function implementing the algorithm, we would have ```
euclid(8,5) =
euclid(5,3) = euclid(3,2) = euclid(2,1) = euclid(1,0) = 1
```

, which
corresponds to the steps we made. For that reason, these rhythms are
called
Euclidean rhythms.

To describe a Euclidean rhythm we use the \(E(k, n)\) notation, where
\(k\) is the number of onsets and \(n\) is the length of the rhythm, for
example \(E(5, 9)\). We can also use another notation, in which we count
the intervals until the next onset, so we have \(E(5, 9) = (22221)\),
because there are two between the first and the second onset in
\([\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ ]\), and so on. Another rhythm is \(E(5, 12)\),
which corresponds to \([\ 1\ 0\ 0\ 1\ 0\ 1\ 0\ 0\ 1\ 0\ 1\ 0\ ]\) and
can also be written \((32322)\), as you may check. The second notation
is called *adjacent-inter-onset-interval vector*, or *interval vector*
for short. In essence, an interval vector is a sequence of positive
integers.

If we have a rhythm written in interval vector notation, say, ```
P =
(p[0], p[1] , ... , p[n−1])
```

, then if we increase `p[0]`

by one and
decrease `p[n-1]`

by one, we will get a new interval vector. If this
new interval vector can also result by rotating the first one, then we
say that we have a *Euclidean string*. For example, \(E(4, 9)\) is
\([\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 0\ ]\) and \((2223)\). If we increase the first
digit by one and we decrease the last digit by one, we get \((3222)\),
which we can get by rotating the first string, so the rhythm is also a
Euclidean string.

If we take the reverse string from an interval vector, that is, if we
read it from the end to the start, and we the reverse string is also a
Euclidean string, then we say that we have a *reverse Euclidean
string*. For example, \(E(4, 11)\) is
\([\ 1\ 0\ 0\ 1\ 0\ 0\ 1\ 0\ 0\ 1\ 0\ ]\) and \((3332)\). The reverse
string of the interval vector is \((2333)\), which is a Euclidean
string, so \((3332)\) is a reverse Euclidean string.

For more information on Euclidean rhythms check [4]; Godfried Toussaint was the one that introduced the concept and has written a whole book on the geometry of musical rhythm [6]. See also [2] for a well-developed overview. For more information on Euclidean strings, see [3].

### Distance between Rhythms

How different are two rhythms? If we take two rhythms are binary
sequences, then one metric that we can use to gauge the distance
between two strings of equal length is the number of positions in
which the corresponding elements of the sequences are different. This
is called
Hamming distance. If
`s1`

and `s2`

are two sequences, the following function (adapted for
Python 3 from
the Wikipedia article), calculates the Hamming distance:

```
def hamming_distance(s1, s2):
if len(s1) != len(s2):
raise ValueError("Undefined for sequences of unequal length")
return sum(bool(ord(ch1) - ord(ch2)) for ch1, ch2 in zip(s1, s2))
```

For example, the rhythm \(E(4, 9) = [\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 0\ ]\) has a Hamming distance of one from the rhythm \(E(5, 9) = [\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ ]\) and a Hamming distance of three from the rhythm \(E(7, 9) = [\ 1\ 0\ 1\ 1\ 1\ 0\ 1\ 1\ 1\ ]\).

That said, the Hamming distance is not the best way to measure the similarity of rhythms. There are better metrics for that purpose [5] [6], but we'll stick to the Hamming distance for now.

In this assignment you will develop a program that handles and manipulates Euclidean rhythms.

### Requirements

- You will write a program called
`musical_rhythms.py`

, which will work with Euclidean rhythms. - The program will read, upon start, the dictionary of rhythms that
is stored in the file
musical_rhythms.json. The file
should be stored in the same directory as the program itself. The
contents of the file are in
JSON (JavaScript Object Notation), so you
should use the
Python
`json`

library. - Your program must be called as follows:

```
python musical_rhythms.py [-s SLOTS] [-p PULSES] [-r RECOGNIZE] [-l LIST_RHYTHMS]
```

### Output

#### Create a Rhythm

If the user gives the parameters `-s SLOTS`

and `-p PULSES`

, then
`SLOTS`

and `PULSES`

will be positive integers. The program will then
return information on the rhythm that corresponds to these parameters, where
`PULSES`

is the number of onsets and `SLOTS`

is the length of the
rhythm. To do that, the program will look up the rhythm in the rhythm
dictionary. If it finds it there, it will display the information
stored for that rhythm; otherwise, it will just display the rhythm. In
the next line, if the rhythm corresponds to a Euclidean string or to a
reverse Euclidean string, it will display an appropriate message.

Examples:

```
python musical_rhythms.py -s 12 -p 6
E(6,12) = [101010101010] = (222222)
```

```
python musical_rhythms.py -s 12 -p 7
E(7,12) = [101101011010] = (2122122) It is a common West African bell pattern. For example, it is used in the Mpre rhythm of the Ashanti people of Ghana. Started on the seventh (last) onset, it is a Yoruba bell pattern of Nigeria, a Babenzele pattern of Central Africa, and a Mende pattern of Sierra Leone.
```

```
python musical_rhythms.py -s 16 -p 5
E(5,16) = [1001001001001000] = (33334) It is the Bossa-Nova rhythm necklace of Brazil. The actual Bossa-Nova rhythm usually starts on the third onset as follows: [1001001000100100]. However, other starting places are also documented in world music practices, such as [1001001001000100].
It is a Euclidean string.
```

```
python musical_rhythms.py -s 9 -p 5
E(5,9) = [101010101] = (22221) It is a popular Arabic rhythm called Agsag-Samai. Started on the second onset, it is a drum pattern used by the Venda in South Africa, as well as a Rumanian folk-dance rhythm. It is also the rhythmic pattern of the Sigaktistos rhythm of Greece, and the Samai aktsak rhythm of Turkey. Started on the third onset, it is the rhythmic pattern of the Nawahiid rhythm of Turkey.
It is a reverse Euclidean string.
```

As you can see, the first thing to appear will be rhythm in the form \(E(k, n)\); then as a binary string inside square brackets; then as interval vector inside parentheses; and then any description found in the rhythms dictionary. The final line will contain a message if it is a Euclidean or a reverse Euclidean string.

#### Rhythm Recognition

If the user gives the parameter `-r RECOGNIZE`

, then `RECOGNIZE`

will
be a rhythm represented as a binary string and the program should
identify it, if it is a Euclidean rhythm, and print out any
information available. If it is not a Euclidean rhythm, it should
print an appropriate message.

Examples:

```
python musical_rhythms.py -r 101101011010
E(7,12) = [101101011010] = (2122122) It is a common West African bell pattern. For example, it is used in the Mpre rhythm of the Ashanti people of Ghana. Started on the seventh (last) onset, it is a Yoruba bell pattern of Nigeria, a Babenzele pattern of Central Africa, and a Mende pattern of Sierra Leone.
```

```
python musical_rhythms.py -r 10010010010
E(4,11) = [10010010010] = (3332) It is the metric pattern used by Frank Zappa in his piece titled Outside Now.
It is a reverse Euclidean string.
```

```
python musical_rhythms.py -r 10010010011
Not a Euclidean rhythm.
```

#### Show Similar Rhythms

If the user gives the parameter `-l LIST_RHYTHMS`

, then `LIST_RHYTHMS`

will be a rhythm given as a binary string and the program will display
all rhythms of the same length, ordered in increasing Hamming distance
and number of onsets.

Examples:

```
python musical_rythms.py -l 101010100
Distance = 0
E(4,9) = [101010100] = (2223) It is the Aksak rhythm of Turkey. It is also the metric pattern used by Dave Brubeck in his piece Rondo a la Turk.
It is a Euclidean string.
Distance = 1
E(5,9) = [101010101] = (22221) It is a popular Arabic rhythm called Agsag-Samai. Started on the second onset, it is a drum pattern used by the Venda in South Africa, as well as a Rumanian folk-dance rhythm. It is also the rhythmic pattern of the Sigaktistos rhythm of Greece, and the Samai aktsak rhythm of Turkey. Started on the third onset, it is the rhythmic pattern of the Nawahiid rhythm of Turkey.
It is a reverse Euclidean string.
Distance = 2
E(2,9) = [100010000] = (45)
It is a Euclidean string.
Distance = 3
E(1,9) = [100000000] = (9)
Distance = 3
E(3,9) = [100100100] = (333)
Distance = 3
E(7,9) = [101110111] = (2112111) It is the Bazaragana rhythmic pattern of Greece.
It is a reverse Euclidean string.
Distance = 4
E(6,9) = [101101101] = (212121)
Distance = 4
E(8,9) = [101111111] = (21111111)
It is a reverse Euclidean string.
```

```
python musical_rythms.py -l 1001001001000
Distance = 0
E(4,13) = [1001001001000] = (3334)
It is a Euclidean string.
Distance = 2
E(2,13) = [1000001000000] = (67)
It is a Euclidean string.
Distance = 3
E(1,13) = [1000000000000] = (13)
Distance = 5
E(3,13) = [1000100010000] = (445)
It is a Euclidean string.
Distance = 5
E(5,13) = [1001010010100] = (32323) It is a rhythm from the FYROM which is also played by starting it on the fourth onset as follows: [1010010010100].
Distance = 5
E(9,13) = [1011011011011] = (212121211)
It is a reverse Euclidean string.
Distance = 6
E(6,13) = [1010101010100] = (222223) It is the rhythm of the dance Mama Cone pita from the FYROM. Started on the third onset, it is the rhythm of the dance Postupano Oro from the FYROM, as well as the Krivo Plovdivsko Horo of Bulgaria.
It is a Euclidean string.
Distance = 7
E(7,13) = [1010101010101] = (2222221)
It is a reverse Euclidean string.
Distance = 7
E(11,13) = [1011111011111] = (21111211111)
It is a reverse Euclidean string.
Distance = 8
E(8,13) = [1011010110101] = (21221221)
Distance = 8
E(10,13) = [1011101110111] = (2112112111)
It is a reverse Euclidean string.
Distance = 8
E(12,13) = [1011111111111] = (211111111111)
It is a reverse Euclidean string.
```

### Notes on Implementation

The rhythms can be constructed using an algorithm with repeated division, following the logic of Euclid's algorithm. That algorithm is called the Bjorklund algorithm, after the name of the researcher that noticed such patterns in neutron experiments in the Spallation Neutron Source [1].

*Do not use the Bjorklund algorithm to solve the assignment. Develop
your solutions manipulating lists, as is described here.*

If you want to verify your results, you may wish to check the Euclidean rhythms in [4] and [2].

### Bibliography

- E. Bjorklund. The theory of rep-rate pattern generation in the SNS timing system. Technical Report SNS-NOTE-CNTRL-99, Spallation Neutron Source, 1999. URL: https://ics-web.sns.ornl.gov/timing/Rep-Rate%20Tech%20Note.pdf. ↩
- Erik D. Demaine, Francisco Gomez-Martin, Henk Meijer, David Rappaport, Perouz Taslakian, Godfried T. Toussaint, Terry Winograd, and David R. Wood.
The distance geometry of music.
*Computational Geometry: Theory and Applications*, 42(5):429–454, July 2009. URL: http://erikdemaine.org/papers/DeepRhythms_CGTA/paper.pdf.^{1}^{2} - John Ellis, Frank Ruskey, Joe Sawada, and Jamie Simpson.
Euclidean strings.
*Theoretical Computer Science*, 301(1):321–340, 2003. URL: http://www.socs.uoguelph.ca/~sawada/papers/euclid.pdf, doi:http://dx.doi.org/10.1016/S0304-3975(02)00589-3. ↩ - Godfried Toussaint.
The Euclidean algorithm generates traditional musical rhythms.
In
*BRIDGES: Mathematical Connections in Art, Music, and Science*, 47–56. July 31 to August 3 20015. URL: http://cgm.cs.mcgill.ca/~godfried/publications/banff.pdf.^{1}^{2} - Godfried Toussaint.
The geometry of musical rhythm.
In
*Proceedings of the 2004 Japanese Conference on Discrete and Computational Geometry*, JCDCG'04, 198–212. Berlin, Heidelberg, 2005. Springer-Verlag. URL: http://cgm.cs.mcgill.ca/~godfried/publications/geometry-of-rhythm.pdf, doi:10.1007/11589440_20. ↩ - Godfried T. Toussaint.
*The Geometry of Musical Rhythm: What Makes a "Good" Rhythm Good?*CRC Press, Taylor & Francis Group, Boca Raton, FL, 2013.^{1}^{2}