Skip to main content
Code Golf

Return to Question

Tweeted twitter.com/#!/StackCodeGolf/status/593028936596074496
deleted 1 character in body
Source Link
unclemeat
unclemeat
  • 2.3k
  • 1
  • 16
  • 23

Did you know that the Euclidean algorithm is capable of generating traditional musical rhythms?.? We'll see how this works by describing a similar, but slightly different algorithm to that in the paper.

Did you know that the Euclidean algorithm is capable of generating traditional musical rhythms?. We'll see how this works by describing a similar, but slightly different algorithm to that in the paper.

Did you know that the Euclidean algorithm is capable of generating traditional musical rhythms? We'll see how this works by describing a similar, but slightly different algorithm to that in the paper.

Source Link
Sp3000
Sp3000
  • 61.9k
  • 13
  • 115
  • 287

Generating Euclidean rhythms

Did you know that the Euclidean algorithm is capable of generating traditional musical rhythms?. We'll see how this works by describing a similar, but slightly different algorithm to that in the paper.

Pick a positive integer n, the total number of beats, and a positive integer k, the number of beats which are sounded (notes). We can think of the rhythm as a sequence of n bits, k of which are 1s. The idea of the algorithm is to distribute the 1s as evenly as possible amongst the 0s.

For example, with n = 8 and k = 5, we start with 5 ones and 3 zeroes, each in its own sequence:

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

At any point we will have two types of sequences — the ones at the start are the "core" sequences and the ones at the end are the "remainder" sequences. Here the cores are [1]s and the remainders are [0]s. As long as we have more than one remainder sequence, we distribute them amongst the cores:

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

Now the core is [1 0] and the remainder is [1], and we distribute again:

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

Now the core is [1 0 1] and the remainder is [1 0]. Since we only have one remainder sequence, we stop and get the string

10110110

This is what it sounds like, repeated 4 times:

https://soundcloud.com/sp3000/8-5-euclidean-rhythm-1

Here's another example, with n = 16 and k = 6:

[1] [1] [1] [1] [1] [1] [0] [0] [0] [0] [0] [0] [0] [0] [0] [0]
[1 0] [1 0] [1 0] [1 0] [1 0] [1 0] [0] [0] [0] [0]
[1 0 0] [1 0 0] [1 0 0] [1 0 0] [1 0] [1 0]
[1 0 0 1 0] [1 0 0 1 0] [1 0 0] [1 0 0]
[1 0 0 1 0 1 0 0] [1 0 0 1 0 1 0 0]
1001010010010100

Note how we terminated on the last step with two core sequences and no remainder sequences. Here it is, repeated twice:

https://soundcloud.com/sp3000/16-6-euclidean-rhythm

Input

You may write a function or a full program reading from STDIN, command line or similar. Input will be two positive integers n and k <= n, which you may assume is in either order.

Output

Your task is to output the generated rhythm as an n character long string. You may pick any two distinct printable ASCII characters (0x20 to 0x7E) to represent notes and rests.

Test cases

The following test cases use x to represent notes and .s to represent rests. Input is given in the order n, then k.

1 1    ->  x
3 2    ->  xx.
5 5    ->  xxxxx
8 2    ->  x...x...
8 5    ->  x.xx.xx.
8 7    ->  xxxxxxx.
10 1   ->  x.........
11 5   ->  x.x.x.x.x..
12 7   ->  x.xx.x.xx.x.
16 6   ->  x..x.x..x..x.x..
34 21  ->  x.xx.x.xx.xx.x.xx.x.xx.xx.x.xx.x.x
42 13  ->  x...x..x..x..x...x..x..x..x...x..x..x..x..
42 18  ->  x..x.x.x..x.x.x..x.x.x..x.x.x..x.x.x..x.x.

Scoring

This is code-golf, so the code in the fewest bytes wins.