{
   "description" : "A quick and dirty recursive approach to finding valid solutions for a set of constraints by backtracking.\r\n\r\nThe constraints are: Given a set of phrases (defined as Pbinds), randomly string them together so that the total duration is one \"bar\" (where the bar could have any number of beats, of course -- here it's 9). A phrase can be truncated, but it's not valid to change the duration of a note.\r\n\r\nThat's for the first version of the ~backtracking function. The second version adds one more constraint: the bar must not end with a 16th note. The only difference between the two versions is an additional condition in the 'case' statement, which causes the solution to be rejected if the last duration is 0.25.",
   "ancestor_list" : [],
   "author" : "jamshark70",
   "name" : "demo: backtracking constraint solver",
   "id" : "1-1i",
   "is_private" : null,
   "code" : "(\r\n~phrases = [\r\n\tPbind(\r\n\t\t\\degree, Pseq([0, -2, 1, 2, 1, 6, 4]),\r\n\t\t\\dur, Pseq([0.75, 0.25, 0.25, 0.5, 0.25, 0.75, 0.75])\r\n\t),\r\n\tPbind(\r\n\t\t\\degree, Pseq([7, 4, 3, 1, -2, 0, 1]),\r\n\t\t\\dur, Pseq([0.5, 0.75, 0.25, 0.5, 0.25, 0.25, 0.75])\r\n\t),\r\n\tPbind(\r\n\t\t\\degree, Pseq([2, 1, 0, 1, 2, 4, 5, 1]),\r\n\t\t\\dur, Pseq([0.25, 0.25, 0.25, 0.25, 0.25, 0.25, 0.25, 0.75])\r\n\t),\r\n\tPbind(\r\n\t\t\\degree, Pseq([4, 5, 4, 5, 7, 8, 7, 9, 6]),\r\n\t\t\\dur, Pseq([0.5, 0.5, 0.25, 0.25, 0.25, 0.5, 0.25, 0.75, 0.75])\r\n\t)\r\n];\r\n\r\n~addNotesToBar = { |list, pattern, beatInBar, beatsPerBar = 4|\r\n\tvar stream = Pbindf(pattern, \\amp, Pseq([0.3, Pn(0.1, inf)])).asStream,\r\n\t\tbeatsToAdd = (beatInBar + 0.01).roundUp(beatsPerBar) - beatInBar,\r\n\t\tevent;\r\n\twhile { beatsToAdd > 0 and: {\r\n\t\tevent = stream.next(Event.new);\r\n\t\tevent.notNil\r\n\t} } {\r\n\t\tlist.add(event);\r\n\t\tbeatsToAdd = beatsToAdd - event[\\dur];\r\n\t};\r\n\tbeatsToAdd  // return value; 0 if exactly the bar line, negative otherwise\r\n};\r\n)\r\n\r\n(\r\n~backtracking = { |list, beatInBar = 0, beatsPerBar = 4|\r\n\tvar tryPhraseOrder = ~phrases.scramble,\r\n\t\tremaining, localList, saveBacktrackList;\r\n\tremaining = block { |break|\r\n\t\ttryPhraseOrder.do { |phr|\r\n\t\t\tlocalList = list.copy;\r\n\t\t\tremaining = ~addNotesToBar.value(localList, phr, beatInBar, beatsPerBar);\r\n\t\t\tcase\r\n\t\t\t\t{ remaining == 0 } { break.value(remaining) }  // success! early exit\r\n\t\t\t\t\t// bar is not full; recursion to add another phrase\r\n\t\t\t\t{ remaining > 0 } {\r\n\t\t\t\t\tbeatInBar = (beatInBar + 0.01).roundUp(beatsPerBar) - remaining;\r\n\t\t\t\t\tsaveBacktrackList = localList.copy;\r\n\t\t\t\t\tremaining = ~backtracking.value(localList, beatInBar, beatsPerBar);\r\n\t\t\t\t\tif(remaining == 0) {\r\n\t\t\t\t\t\tbreak.value(0) // success\r\n\t\t\t\t\t} {\r\n\t\t\t\t\t\t// return to previous state before trying the next phrase\r\n\t\t\t\t\t\tlocalList = saveBacktrackList;\r\n\t\t\t\t\t};\r\n\t\t\t\t};\r\n\t\t\t\t// remaining < 0: failed, try the next phrase\r\n\t\t};\r\n\t\t-1  // we are using a negative result for \"failed\"\r\n\t};\r\n\t// update parent's list with new contents from localList\r\n\tif(remaining == 0) {\r\n\t\tlist.clear;\r\n\t\tlist.addAll(localList);\r\n\t} {\r\n\t\tremaining = -1;  // bar is not complete is also a failure\r\n\t};\r\n\tremaining\r\n};\r\n)\r\n\r\n// test\r\n~backtracking.value(l = List.new, beatInBar: 0, beatsPerBar: 8);\r\n\r\nPseq(l).play;\r\n\r\nl.sum(_.dur);  // test resulting duration\r\n\r\n\r\n// play many bars\r\n// Penvir stuff was for debugging, don't worry about it\r\n(\r\np = Ppar([\r\n\t// metronome\r\n\tPbind(\r\n\t\t\\degree, Pseq([21, Pn(14, 8)], inf),\r\n\t\t\\dur, 1,\r\n\t\t\\legato, 0.2,\r\n\t\t\\amp, Pseq([0.1, 0.05, 0.05], inf)\r\n\t),\r\n\tPn(Plazy({\r\n\t\tvar\tlist = List.new, remain;\r\n\t\tif(~time.isNil) { ~time = thisThread.beats };\r\n\t\t(thisThread.beats - ~time).debug(\"elapsed\");\r\n\t\tremain = ~backtracking.value(list, beatInBar: 0, beatsPerBar: 9);\r\n\t\t[remain, list.sum(_.dur)].debug(\"remain, total\");\r\n\t\tif(remain == 0) { Pseq(list) } { \"failed\".debug; nil };\r\n\t}), inf)\r\n]).play;\r\n)\r\n\r\np.stop;\r\n\r\n// too slow...\r\nTempoClock.default.tempo = 1.5;\r\n\r\n\r\n// 2nd version: no 1/16-notes at the end of the bar\r\n(\r\n~backtracking = { |list, beatInBar = 0, beatsPerBar = 4|\r\n\tvar tryPhraseOrder = ~phrases.scramble,\r\n\t\tremaining, localList, saveBacktrackList, localBeatInBar;\r\n\tremaining = block { |break|\r\n\t\ttryPhraseOrder.do { |phr|\r\n\t\t\tlocalList = list.copy;\r\n\t\t\tlocalBeatInBar = beatInBar;\r\n\t\t\tremaining = ~addNotesToBar.value(localList, phr, beatInBar, beatsPerBar);\r\n\t\t\tcase\r\n\t\t\t\t// \"fail\" (loop around to try the next phrase) if last note is 1/16\r\n\t\t\t\t{ localList.last.dur <= 0.25 } { nil }\r\n\t\t\t\t{ remaining == 0 } { break.value(remaining) }  // success! early exit\r\n\t\t\t\t\t// bar is not full; recursion to add another phrase\r\n\t\t\t\t{ remaining > 0 } {\r\n\t\t\t\t\tlocalBeatInBar = (localBeatInBar + 0.01).roundUp(beatsPerBar) - remaining;\r\n\t\t\t\t\tsaveBacktrackList = localList.copy;\r\n\t\t\t\t\tremaining = ~backtracking.value(localList, localBeatInBar, beatsPerBar);\r\n\t\t\t\t\tif(remaining == 0) {\r\n\t\t\t\t\t\tbreak.value(0) // success\r\n\t\t\t\t\t} {\r\n\t\t\t\t\t\t// return to previous state before trying the next phrase\r\n\t\t\t\t\t\tlocalList = saveBacktrackList;\r\n\t\t\t\t\t};\r\n\t\t\t\t};\r\n\t\t\t\t// remaining < 0: failed, try the next phrase\r\n\t\t};\r\n\t\t-1  // we are using a negative result for \"failed\"\r\n\t};\r\n\t// update parent's list with new contents from localList\r\n\tif(remaining == 0) {\r\n\t\tlist.clear;\r\n\t\tlist.addAll(localList);\r\n\t} {\r\n\t\tremaining = -1;  // bar is not complete is also a failure\r\n\t};\r\n\tremaining\r\n};\r\n)\r\n\r\n(\r\np = Ppar([\r\n\t// metronome\r\n\tPbind(\r\n\t\t\\degree, Pseq([21, Pn(14, 8)], inf),\r\n\t\t\\dur, 1,\r\n\t\t\\legato, 0.2,\r\n\t\t\\amp, Pseq([0.1, 0.05, 0.05], inf)\r\n\t),\r\n\tPn(Plazy({\r\n\t\tvar\tlist = List.new, remain;\r\n\t\tif(~time.isNil) { ~time = thisThread.beats };\r\n\t\t(thisThread.beats - ~time).debug(\"elapsed\");\r\n\t\tremain = ~backtracking.value(list, beatInBar: 0, beatsPerBar: 9);\r\n\t\t[remain, list.sum(_.dur)].debug(\"remain, total\");\r\n\t\tif(remain == 0) { Pseq(list) } { \"failed\".debug; nil };\r\n\t}), inf)\r\n]).play;\r\n)\r\n\r\np.stop;",
   "labels" : [
      "recursion",
      "contraints",
      "backtracking",
      "algorithm"
   ]
}