«demo: backtracking constraint solver» by jamshark70

on 24 Sep'11 09:30 in recursioncontraintsbacktrackingalgorithm

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
(
~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;
raw 4855 chars (focus & ctrl+a+c to copy)
comments