Euclidean rhythm

Euclidean rhythm
You are encouraged to solve this task according to the task description, using any language you may know.

The Euclidean rhythm was proposed by Godfried Toussaint in 2004 and is described in a 2005 paper "The Euclidean Algorithm Generates Traditional Musical Rhythms". It generates many forms of rhythm in music around the world. The program takes 2 integers (m, n) and outputs a binary string with m ones and (n-m) zeros.

As an example, here is how it runs on (5, 13):

• Write 5 ones followed by (13-5) zeros, into 13 groups of 1-digit each:
  • 1 1 1 1 1 | 0 0 0 0 0 0 0 0
• Repeatedly append substitute the second group into the first group:
  • 1 1 1 1 1 | 0 0 0 0 0 0 0 0
  • 10 10 10 10 10 | 0 0 0
  • 100 100 100 10 10 |
• If the first group consists of elements of the same form, then output. Otherwise, divide the first group into two groups of the two forms, and repeat the process:
  • 100 100 100 10 10 |
  • 100 100 100 | 10 10
  • 10010 10010 100 |
• At this point, we can continue the algorithm until only one form remains, but notice that one of the groups has only one element [100], so the algorithm can actually terminate right here and output the concatenation 1001010010100.

EasyLang

Translation of: JavaScript

func$ euclrhythm k n .
   for i to n
      h = if i <= k
      s[][] &= [ h ]
   .
   d = n - k
   n = higher k d
   k = lower k d
   z = d
   while z > 0 or k > 1
      for i to k
         for c in s[len s[][] + 1 - i][]
            s[i][] &= c
         .
      .
      len s[][] -k
      z = z - k
      d = n - k
      n = higher k d
      k = lower k d
   .
   for i to len s[][]
      for v in s[i][]
         r$ &= v
      .
   .
   return r$
.
print euclrhythm 3 8

Output:

10010010

Java

Translation of: Python

import java.util.ArrayList;
import java.util.List;

public class SequenceGenerator {
    
    public static void main(String[] args) {
        String result = generateSequence(5, 13);
        System.out.println(result); // Should print 1001010010100
    }

    public static String generateSequence(int k, int n) {
        List<List<Integer>> s = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            List<Integer> innerList = new ArrayList<>();
            if (i < k) {
                innerList.add(1);
            } else {
                innerList.add(0);
            }
            s.add(innerList);
        }

        int d = n - k;
        n = Math.max(k, d);
        k = Math.min(k, d);
        int z = d;

        while (z > 0 || k > 1) {
            for (int i = 0; i < k; i++) {
                s.get(i).addAll(s.get(s.size() - 1 - i));
            }
            s = s.subList(0, s.size() - k);
            z -= k;
            d = n - k;
            n = Math.max(k, d);
            k = Math.min(k, d);
        }

        StringBuilder result = new StringBuilder();
        for (List<Integer> sublist : s) {
            for (int item : sublist) {
                result.append(item);
            }
        }
        return result.toString();
    }
}

Output:

1001010010100

JavaScript

Copied from here and here, under MIT license.

const E = (k, n) => {
    let s = Array(n).fill(0)
        .map((_, i) => (i < k ? [1] : [0]))

    let d = n - k
    n = Math.max(k, d)
    k = Math.min(k, d)
    let z = d

    while (z > 0 || k > 1) {
        for (let i = 0; i < k; i++)
            s[i].push(...s[s.length - 1 - i])
        s.splice(-k)
        z = z - k
        d = n - k
        n = Math.max(k, d)
        k = Math.min(k, d)
    }

    return s.flat()
}

Output:

> E(3,8)
[1, 0, 0, 1, 0, 0, 1, 0]

Python

Translation of: JavaScript

def E(k, n):
    s = [[1] if i < k else [0] for i in range(n)]

    d = n - k
    n = max(k, d)
    k = min(k, d)
    z = d

    while z > 0 or k > 1:
        for i in range(k):
            s[i].extend(s[len(s) - 1 - i])
        s = s[:-k]
        z = z - k
        d = n - k
        n = max(k, d)
        k = min(k, d)

    return [item for sublist in s for item in sublist]

print(''.join(map(str, E(5, 13))))
# 1001010010100

Swift

Translation of: Java

import Foundation

class SequenceGenerator {

    static func generateSequence(k: Int, n: Int) -> String {
        var s = Array(repeating: [Int](), count: n)

        for i in 0..<n {
            if i < k {
                s[i].append(1)
            } else {
                s[i].append(0)
            }
        }

        var d = n - k
        var nVar = max(k, d)
        var kVar = min(k, d)
        var z = d

        while z > 0 || kVar > 1 {
            for i in 0..<kVar {
                s[i].append(contentsOf: s[s.count - 1 - i])
            }
            s = Array(s[0..<(s.count - kVar)])
            z -= kVar
            d = nVar - kVar
            nVar = max(kVar, d)
            kVar = min(kVar, d)
        }

        let result = s.flatMap { $0 }.map { String($0) }.joined()
        return result
    }
}

// Example usage
let result = SequenceGenerator.generateSequence(k: 5, n: 13)
print(result) // Should print 1001010010100

Output:

1001010010100

Wren

Translation of: Python

Library: Wren-seq

import "./seq" for Lst

var E = Fn.new { |k, n|
    var s = (0...n).map { |i| i < k ? [1] : [0] }.toList
    var d = n - k
    n = k.max(d)
    k = k.min(d)
    var z = d
    while (z > 0 || k > 1) {
        for (i in 0...k) s[i].addAll(s[-1 - i])
        s = s[0...-k]
        z = z - k
        d = n - k
        n = k.max(d)
        k = k.min(d)
    }
    return Lst.flatten(s)
}

System.print(E.call(5, 13).join())

Output:

1001010010100

Zig

Translation of: Python

const std = @import("std");
const allocator = std.heap.page_allocator;

pub fn main() !void {
    const result = try generateSequence(5, 13);
    for (result) |item| {
        std.debug.print("{}", .{item});
    }
    std.debug.print("\n", .{});
}

fn generateSequence(_k: i32, _n: i32) ![]i32 {
    var k=_k; var n=_n;

    var s = std.ArrayList(std.ArrayList(i32)).init(allocator);

    for (0..@as(usize, @intCast(n))) |i| {
        var innerList = std.ArrayList(i32).init(allocator);
        if (i < k) {
            try innerList.append(1);
        } else {
            try innerList.append(0);
        }
        try s.append(innerList);
    }

    var d:i32 = n-k;  
    n = @max(k, d);
    k = @min(k, d);
    var z = d;

    while (z > 0 or k > 1) {
        for (0..@as(usize, @intCast(k))) |i| {
            var lastList = s.items[s.items.len - 1 - i];
            for (lastList.items) |item| {
                try s.items[i].append(item);
            }
        }
        s.shrinkRetainingCapacity(s.items.len - @as(usize, @intCast(k)));
        z -= k;
        d = n - k;
        n = @max(k, d);
        k = @min(k, d);
    }

    var result = std.ArrayList(i32).init(allocator);

    for (s.items) |sublist| {
        for (sublist.items) |item| {
            try result.append(item);
        }
    }
    return result.toOwnedSlice();
}

Output:

1001010010100