Markov Chain Beatbox Generator

Question

Just an idea I had the other day: Making beats following a Markov Chain of predefined sounds.

I remember someone did a beatbox with Google Translate and the German language (follow the link and press listen).

So, the challenge is to build a text input to Google Translate from a given chain. Or you can use musical notes and play it yourself :).

You can make a program reading a line with the number of beats, another with their names and a matrix representation of the probabilities (you can choose the representation).

You may also make a function with those three arguments.

E.g.

[input]

20
pv zk bschk kkkk
[[.1, .4, .5, 0.],
 [.3, .2, .3, .2],
 [0., .3, .2, .5],
 [.1, .8, .1, 0.]]

[output] something like:

pv zk bschk zk pv bschk zk pv zk bschk kkkk pv bschk zk bschk bschk bschk zk kkkk bschk

The starting probability is the same for each beat.

That's not a code-golf challenge because I would like to see some nice solutions (be creative).

Extra points if you invent new beats and/or choose a table of probabilities that gives nice beats most of the time.

If you want, you can use real beats (In many languages it's easy to open .wav files, like the wave module in Python) and generate music! Here are some free sample beats.

I may post a reference implementation if needed.

Answer 1

I made these tracks:

http://soundcloud.com/belisarius/sets/golf-music

Using the following transition matrix:

{{10,  1,  3/2, 2},  
 {1/2, 10, 3/2, 2},  
 {1/2, 1,  10,  2},  
 {1/2, 1,  3/2, 10}} 

And the following program in Mathematica:

musicGen[n_, notes_, transMatrix_] :=
 Module[{
          im := IdentityMatrix[Length@notes],
          a  := Array[2^(# - 1) &, Length@notes],
          soundLength = .1  n,
          which
          },
  which[x_] := Position[x, 1][[1, 1]];
  Sound[Join[
    (SoundNote /@ notes[[
        which[#] & /@
         NestList[
          RandomChoice[transMatrix[[which@#]] -> im] &,
          RandomChoice@im,
          n - 1]
        ]]
     )
    ],
   soundLength]
  ]
tm = {{10, 1, 3/2, 2}, {1/2, 10, 3/2, 2}, {1/2, 1, 10, 2}, {1/2, 1, 3/2, 10}}
notesSet = {"Snare", {"Slap", "Shaker"}, {"OpenTriangle", "Maracas"}, "RideBell"};
m = Array[If[#2 == 5 || #2 == #1, 10, #2/2] &, {Length@notesSet,Length@notesSet}];
mg = musicGen[100, notesSet, tm]

Answer 2

Being German, I was almost falling off my chair laughing at this creative abuse of our language. :-)

Here is some Scala. I am encoding the probabilities in a map that maps the beat to a list of successor beats in which the beats occure with a frequency proportional to their probability. An infinite lazy evaluated stream of beats is created, whose first 10 beats are skipped to get the appropriate randomness of the first output beat. We return the appropriate number of beats from the beginning of that stream. I use the type parameter T to be shorter and generic.

def markovChain[T](length : Int, nodes : Seq[T], probabilities : Map[T, Seq[T]]) : Seq[T] = {
  def randomElement(seq : Seq[T]) = seq(Random.nextInt(seq.length))
  def chain(node: T): Stream[T] =
    Stream.cons(node, chain(randomElement(probabilities(node))))
  return chain(randomElement(nodes)) drop(10) take(length)
}

which can be called like this:

val nodes = List("pv", "zk", "bschk", "kkkk")

val probabilities = Map(
  "pv" -> List("pv", "zk", "zk", "zk", "zk", "bschk", "bschk", "bschk", "bschk", "bschk"),
  "zk" -> List("pv", "pv", "pv", "zk", "zk", "bschk", "bschk", "bschk", "kkkk", "kkkk") ,
  "bschk" -> List("zk", "zk", "zk", "bschk", "bschk", "kkkk", "kkkk", "kkkk", "kkkk", "kkkk"),
  "kkkk" -> List("pv", "zk", "zk", "zk", "zk", "zk", "zk", "zk", "zk", "bschk"))

markovChain(20, nodes, probabilities) foreach (s => print (s + " "))

Answer 3

I wrote a Javascript function. However, it have begun beatboxing itself...

function bschk(jk,pv,kkkk){jkjk='pv jk bschk kkkk'.split(' ');boom='indexOf';eval(
function(jkpv){for(pvpv=0,bschkpv='';pvpv<jkpv.length;jkpvpv=jkpv[pvpv++].split(' '),
bschkpv+=String.fromCharCode(jkjk[boom](jkpvpv[0])+jkjk[boom](jkpvpv[1])*4+jkjk[
boom](jkpvpv[2])*16+jkjk[boom](jkpvpv[3])*64));return bschkpv}((
'bschk jk bschk jk  kkkk kkkk bschk jk  bschk pv kkkk jk  pv bschk bschk pv  bschk '
+'jk kkkk jk  jk pv bschk jk  bschk pv kkkk jk  pv pv bschk pv  jk jk bschk jk  jk '
+'kkkk kkkk pv  bschk kkkk kkkk jk  bschk kkkk kkkk jk  pv bschk bschk pv  jk kkkk '
+'pv jk  jk pv bschk jk  pv jk kkkk jk  pv bschk bschk jk  bschk kkkk bschk pv  bsc'
+'hk pv kkkk jk  jk pv bschk jk  bschk kkkk bschk jk  pv jk bschk jk  kkkk kkkk bsc'
+'hk jk  jk kkkk bschk jk  pv bschk bschk pv  jk bschk bschk pv  bschk bschk bschk '
+'pv  pv pv kkkk jk  bschk jk kkkk jk  bschk kkkk bschk pv  pv kkkk bschk jk  jk jk'
+' bschk jk  bschk kkkk bschk jk  kkkk jk bschk jk  pv jk kkkk jk  pv bschk bschk j'
+'k  jk bschk bschk pv  pv kkkk bschk pv  jk bschk bschk jk  jk kkkk kkkk pv  pv pv'
+' kkkk pv  pv kkkk bschk pv  bschk jk bschk jk  pv kkkk bschk pv  kkkk jk bschk jk'
+'  pv kkkk bschk pv  kkkk pv bschk jk  kkkk bschk bschk jk  kkkk pv bschk jk  kkkk'
+' bschk bschk jk  bschk pv bschk jk  kkkk kkkk bschk jk  kkkk kkkk bschk jk  jk kk'
+'kk bschk jk  jk kkkk kkkk pv  kkkk jk bschk pv  kkkk jk bschk pv  kkkk bschk kkkk'
+' pv  jk bschk bschk jk  pv kkkk kkkk pv  bschk bschk bschk jk  kkkk bschk bschk j'
+'k  kkkk bschk kkkk pv  jk bschk bschk jk  kkkk bschk bschk pv  kkkk bschk bschk p'
+'v  jk bschk bschk pv  kkkk bschk kkkk jk  kkkk pv bschk jk  kkkk bschk bschk jk  '
+'kkkk pv bschk jk  kkkk bschk bschk jk  bschk pv bschk jk  kkkk kkkk bschk jk  kkk'
+'k kkkk bschk jk  jk kkkk bschk jk  kkkk bschk bschk pv  jk kkkk kkkk pv  pv pv kk'
+'kk jk  bschk jk kkkk jk  kkkk bschk jk jk  jk jk bschk jk  jk kkkk jk jk  kkkk bs'
+'chk bschk pv  kkkk jk bschk pv  pv pv bschk pv  kkkk jk bschk pv  kkkk bschk kkkk'
+' pv  kkkk jk bschk jk  jk kkkk kkkk pv  jk kkkk pv jk  jk pv bschk jk  pv jk kkkk'
+' jk  pv bschk bschk jk  bschk kkkk bschk pv  bschk pv kkkk jk  jk pv bschk jk  bs'
+'chk kkkk bschk jk  pv jk bschk jk  kkkk kkkk bschk jk  jk kkkk bschk jk  pv bschk'
+' bschk pv  jk bschk bschk pv  kkkk bschk kkkk pv  bschk jk bschk jk  jk kkkk kkkk'
+' pv  jk kkkk bschk pv  jk pv kkkk pv  kkkk bschk kkkk pv  kkkk jk kkkk jk  pv bsc'
+'hk bschk jk  jk bschk bschk jk  pv kkkk bschk jk  jk jk bschk jk  pv bschk bschk '
+'pv  kkkk jk bschk jk  bschk kkkk kkkk pv  jk kkkk kkkk pv  pv pv kkkk pv  jk bsch'
+'k bschk pv  kkkk jk bschk jk  jk kkkk bschk pv  jk kkkk kkkk pv  kkkk bschk bschk'
+' jk  kkkk bschk bschk jk  kkkk bschk bschk jk  kkkk bschk bschk jk  kkkk bschk jk'
+' jk  jk jk bschk jk  jk kkkk jk jk  kkkk bschk jk jk  kkkk bschk bschk pv  kkkk b'
+'schk bschk pv  bschk jk bschk jk  jk kkkk jk jk  kkkk bschk kkkk pv  jk jk bschk '
+'jk  jk kkkk kkkk pv  bschk jk bschk jk  kkkk bschk kkkk pv  jk kkkk kkkk jk').split
('  ')));return ckckboom;}

Usage example : bschk(20,'pv jk bschk kkkk'.split(' '),[[.1,.4,.5,0],[.3,.2,.3,.2],[0,.3,.2,.5],[.1,.8,.1,0]])

Answer 4

Just a reference implementation in Python:

from random import random

def find(num, pdf):
    ''' Find position of number in CDF from PDF (must sum 100%) '''
    cdf = (sum(pdf[:i+1]) for i in range(len(pdf)))
    for i,j in enumerate(cdf):
        if num < j:
            return i

def build(t, beats, table):
    node = int(random()*len(table))
    nodes = [node]
    for i in range(t-1):
        node = find(random(), table[node])
        nodes.append(node)
    return ' '.join(beats[i] for i in nodes)

And a test program:

table = [[.1, .4, .5, 0.],
         [.3, .2, .3, .2],
         [0., .3, .2, .5],
         [.1, .8, .1, 0.]]

print(build(20, 'pv zk bschk kkkk'.split(), table))

And some outputs:

pv zk bschk zk kkkk zk bschk kkkk zk zk zk bschk kkkk zk bschk zk pv bschk kkkk zk
zk bschk kkkk zk zk kkkk zk bschk kkkk zk bschk zk pv zk pv zk zk bschk kkkk bschk
kkkk zk zk pv bschk bschk zk zk kkkk zk kkkk zk zk kkkk zk pv zk bschk kkkk zk

But none of them makes a really good beatbox because there's too much kkkk :).