Backtracking algorithms, counting beats, and data modeling
I am much more solid on how to translate backtracking concepts to code than I was four hours ago, thanks mostly to this handy page from UPenn/Dave Matuszek. The language is really clear, and it includes answers to questions that I wasn’t seeing on other pages (ex. “What’s the best way to track which options have not yet been explored for a particular node?”).
Earlier in the day, I saw my backtracking challenge like this: backtracking will be useful to ensure that the final move added to a new dance can flow into the first move used*, but it will also be useful to ensure that moves don’t cross from one quarter of a dance to the next. I couldn’t find a way to properly nest these functions so that they could both send an attempt back down the same path if a solution failed either one of the constraints.
Finally, my adviser stepped in with a suggestions that led me to what I believe will be the solution. Instead of measuring the dance in quarters (or, as I was calling them, “buckets”) represented by instances of a class with an attribute of 16 beats, I’ll instead measure the dance in moves (with their assigned numbers of beats), with some checkpoints to ensure that moves don’t cross the 16-beat, 32-beat, and 48-beat times. Basically, instead of this:
Bucket 1 (16 beats): [neighbors balance and swing]
Bucket 2 (16 beats): [right and left through, chain to partner]
etc.
it will look (conceptually) like this:
(0 beats) neighbors balance and swing (16 beats) right and left through (24 beats) chain to partner (32 beats) etc.
This data map has, over the past two days, held as many as 6 and as few as 2 tables. This iteration feels right for right now, but I may need to add some new fields/tables if I add any extra features or if the worst case scenario happens (more on that tomorrow).
Move type refers to the family that a move belongs to; for example, neighbor and partner swings both belong in the “swing” family. Parameters in parenthesis may or may not make it into round 2 of this model.
I’ve made an effort to keep this map (and the algorithm it will feed) scalable. I’ll be working with a limited data set for this project initially, but I’d like to see it work with trickier dances, moves, and progressions** in the long run.
* The choreography will be built using Markov chains derived from pre-existing tried-and-true dances, so the only place where there’s a danger of no flow is between the last move chosen and the first move chosen.
** Because of the trickiness that is progressions, a randomly selected progression chain will be the first pair of moves chosen and the rest of the dance will be built around them. This is part of why progressions will have their own table even though they are technically also chains.