// title: demo: backtracking constraint solver
// author: jamshark70
// description:
// A quick and dirty recursive approach to finding valid solutions for a set of constraints by backtracking.
// 
// The 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.
// 
// That'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.
// code:
(
~phrases = [
	Pbind(
		\degree, Pseq([0, -2, 1, 2, 1, 6, 4]),
		\dur, Pseq([0.75, 0.25, 0.25, 0.5, 0.25, 0.75, 0.75])
	),
	Pbind(
		\degree, Pseq([7, 4, 3, 1, -2, 0, 1]),
		\dur, Pseq([0.5, 0.75, 0.25, 0.5, 0.25, 0.25, 0.75])
	),
	Pbind(
		\degree, Pseq([2, 1, 0, 1, 2, 4, 5, 1]),
		\dur, Pseq([0.25, 0.25, 0.25, 0.25, 0.25, 0.25, 0.25, 0.75])
	),
	Pbind(
		\degree, Pseq([4, 5, 4, 5, 7, 8, 7, 9, 6]),
		\dur, Pseq([0.5, 0.5, 0.25, 0.25, 0.25, 0.5, 0.25, 0.75, 0.75])
	)
];

~addNotesToBar = { |list, pattern, beatInBar, beatsPerBar = 4|
	var stream = Pbindf(pattern, \amp, Pseq([0.3, Pn(0.1, inf)])).asStream,
		beatsToAdd = (beatInBar + 0.01).roundUp(beatsPerBar) - beatInBar,
		event;
	while { beatsToAdd > 0 and: {
		event = stream.next(Event.new);
		event.notNil
	} } {
		list.add(event);
		beatsToAdd = beatsToAdd - event[\dur];
	};
	beatsToAdd  // return value; 0 if exactly the bar line, negative otherwise
};
)

(
~backtracking = { |list, beatInBar = 0, beatsPerBar = 4|
	var tryPhraseOrder = ~phrases.scramble,
		remaining, localList, saveBacktrackList;
	remaining = block { |break|
		tryPhraseOrder.do { |phr|
			localList = list.copy;
			remaining = ~addNotesToBar.value(localList, phr, beatInBar, beatsPerBar);
			case
				{ remaining == 0 } { break.value(remaining) }  // success! early exit
					// bar is not full; recursion to add another phrase
				{ remaining > 0 } {
					beatInBar = (beatInBar + 0.01).roundUp(beatsPerBar) - remaining;
					saveBacktrackList = localList.copy;
					remaining = ~backtracking.value(localList, beatInBar, beatsPerBar);
					if(remaining == 0) {
						break.value(0) // success
					} {
						// return to previous state before trying the next phrase
						localList = saveBacktrackList;
					};
				};
				// remaining < 0: failed, try the next phrase
		};
		-1  // we are using a negative result for "failed"
	};
	// update parent's list with new contents from localList
	if(remaining == 0) {
		list.clear;
		list.addAll(localList);
	} {
		remaining = -1;  // bar is not complete is also a failure
	};
	remaining
};
)

// test
~backtracking.value(l = List.new, beatInBar: 0, beatsPerBar: 8);

Pseq(l).play;

l.sum(_.dur);  // test resulting duration


// play many bars
// Penvir stuff was for debugging, don't worry about it
(
p = Ppar([
	// metronome
	Pbind(
		\degree, Pseq([21, Pn(14, 8)], inf),
		\dur, 1,
		\legato, 0.2,
		\amp, Pseq([0.1, 0.05, 0.05], inf)
	),
	Pn(Plazy({
		var	list = List.new, remain;
		if(~time.isNil) { ~time = thisThread.beats };
		(thisThread.beats - ~time).debug("elapsed");
		remain = ~backtracking.value(list, beatInBar: 0, beatsPerBar: 9);
		[remain, list.sum(_.dur)].debug("remain, total");
		if(remain == 0) { Pseq(list) } { "failed".debug; nil };
	}), inf)
]).play;
)

p.stop;

// too slow...
TempoClock.default.tempo = 1.5;


// 2nd version: no 1/16-notes at the end of the bar
(
~backtracking = { |list, beatInBar = 0, beatsPerBar = 4|
	var tryPhraseOrder = ~phrases.scramble,
		remaining, localList, saveBacktrackList, localBeatInBar;
	remaining = block { |break|
		tryPhraseOrder.do { |phr|
			localList = list.copy;
			localBeatInBar = beatInBar;
			remaining = ~addNotesToBar.value(localList, phr, beatInBar, beatsPerBar);
			case
				// "fail" (loop around to try the next phrase) if last note is 1/16
				{ localList.last.dur <= 0.25 } { nil }
				{ remaining == 0 } { break.value(remaining) }  // success! early exit
					// bar is not full; recursion to add another phrase
				{ remaining > 0 } {
					localBeatInBar = (localBeatInBar + 0.01).roundUp(beatsPerBar) - remaining;
					saveBacktrackList = localList.copy;
					remaining = ~backtracking.value(localList, localBeatInBar, beatsPerBar);
					if(remaining == 0) {
						break.value(0) // success
					} {
						// return to previous state before trying the next phrase
						localList = saveBacktrackList;
					};
				};
				// remaining < 0: failed, try the next phrase
		};
		-1  // we are using a negative result for "failed"
	};
	// update parent's list with new contents from localList
	if(remaining == 0) {
		list.clear;
		list.addAll(localList);
	} {
		remaining = -1;  // bar is not complete is also a failure
	};
	remaining
};
)

(
p = Ppar([
	// metronome
	Pbind(
		\degree, Pseq([21, Pn(14, 8)], inf),
		\dur, 1,
		\legato, 0.2,
		\amp, Pseq([0.1, 0.05, 0.05], inf)
	),
	Pn(Plazy({
		var	list = List.new, remain;
		if(~time.isNil) { ~time = thisThread.beats };
		(thisThread.beats - ~time).debug("elapsed");
		remain = ~backtracking.value(list, beatInBar: 0, beatsPerBar: 9);
		[remain, list.sum(_.dur)].debug("remain, total");
		if(remain == 0) { Pseq(list) } { "failed".debug; nil };
	}), inf)
]).play;
)

p.stop;