Euclidean rhythm

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.

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

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

Go

Translation of: Java

package main

import (
	"fmt"
	"math"
)

func main() {
	result := generateSequence(5, 13)
	fmt.Println(result) // Should print 1001010010100
}

func generateSequence(k int, n int) string {
	var s [][]int

	for i := 0; i < n; i++ {
		var innerList []int
		if i < k {
			innerList = append(innerList, 1)
		} else {
			innerList = append(innerList, 0)
		}
		s = append(s, innerList)
	}

	d := n - k
	n = int(math.Max(float64(k), float64(d)))
	k = int(math.Min(float64(k), float64(d)))
	z := d

	for z > 0 || k > 1 {
		for i := 0; i < k; i++ {
			s[i] = append(s[i], s[len(s)-1-i]...)
		}
		s = s[:len(s)-k]
		z -= k
		d = n - k
		n = int(math.Max(float64(k), float64(d)))
		k = int(math.Min(float64(k), float64(d)))
	}

	var result string
	for _, sublist := range s {
		for _, item := range sublist {
			result += fmt.Sprintf("%d", item)
		}
	}
	return result
}

Output:

1001010010100

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]

Kotlin

Translation of: Swift

class SequenceGenerator {

    companion object {
        fun generateSequence(k: Int, n: Int): String {
            var s = Array(n) { mutableListOf<Int>() }

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

            var d = n - k
            var nVar = maxOf(k, d)
            var kVar = minOf(k, d)
            var z = d

            while (z > 0 || kVar > 1) {
                for (i in 0 until kVar) {
                    s[i].addAll(s[s.size - 1 - i])
                }
                s = s.copyOfRange(0, s.size - kVar)
                z -= kVar
                d = nVar - kVar
                nVar = maxOf(kVar, d)
                kVar = minOf(kVar, d)
            }

            val result = s.flatMap { it }.joinToString(separator = "") { it.toString() }
            return result
        }
    }
}

// Example usage
fun main() {
    val result = SequenceGenerator.generateSequence(k = 5, n = 13)
    println(result) // Should print 1001010010100
}

Output:

1001010010100

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

R

Translation of: Python

E <- function(k, n) {
  s <- lapply(1:n, function(i) if (i <= k) 1 else 0)

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

  while (z > 0 || k > 1) {
    for (i in 1:k) {
      s[[i]] <- c(s[[i]], s[[length(s) - i + 1]])
    }
    s <- s[1:(length(s) - k)]
    z <- z - k
    d <- n - k
    n <- max(k, d)
    k <- min(k, d)
  }

  unlist(s)
}

# Test the function
cat(E(5, 13), sep = "")
# Output should be 1001010010100

Output:

1001010010100

Ruby

Translation of: Python

def e(k, n)
    s = (0...n).map { |i| i < k ? [1] : [0] }

    d = n - k
    n = [k, d].max
    k = [k, d].min
    z = d

    while z > 0 or k > 1
        k.times do |i|
            s[i].concat(s[-1 - i])
        end
        s = s[0...-k]
        z -= k
        d = n - k
        n = [k, d].max
        k = [k, d].min
    end

    s.flatten.join
end

puts e(5, 13)
# Should output: 1001010010100

Output:

1001010010100

Rust

Translation of: Python

fn e(k: i32, n: i32) -> Vec<u8> {
    let mut s: Vec<Vec<u8>> = (0..n)
        .map(|i| if i < k { vec![1] } else { vec![0] })
        .collect();

    let mut d = n - k;
    let mut n = std::cmp::max(k, d);
    let mut k = std::cmp::min(k, d);
    let mut z = d;

    while z > 0 || k > 1 {
        for i in 0..(k as usize) {
            let mut extension = s[s.len() - 1 - i].clone();
            s[i].append(&mut extension);
        }
        s.truncate(s.len() - (k as usize));
        z -= k;
        d = n - k;
        n = std::cmp::max(k, d);
        k = std::cmp::min(k, d);
    }

    s.into_iter().flatten().collect()
}

fn main() {
    let result = e(5, 13);
    let result_string: String = result.into_iter().map(|digit| digit.to_string()).collect();
    println!("{}", result_string);
}

Output:

1001010010100

Scala

Translation of: Java

object SequenceGenerator {

  def main(args: Array[String]): Unit = {
    val result = generateSequence(5, 13)
    println(result) // Should print 1001010010100
  }

  def generateSequence(k: Int, n: Int): String = {
    var s = List.fill(n)(List(0)).zipWithIndex.map { case (list, index) =>
      if (index < k) List(1) else List(0)
    }

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

    while (z > 0 || kVar > 1) {
      for (i <- 0 until kVar) {
        s = s.updated(i, s(i) ++ s(s.size - 1 - i))
      }
      s = s.take(s.size - kVar)
      z -= kVar
      d = nVar - kVar
      nVar = math.max(kVar, d)
      kVar = math.min(kVar, d)
    }

    s.flatten.mkString
  }
}

Output:

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