#backtracking algorithms

6 Algorithms Every Developer Should Know As a developer, it is essential to understand algorithms to create efficient and scalable software applications. Algorithms are sets of instructions that perform a specific task, such as sorting data or searching for information. By learning about these six essential algorithms, you can improve your coding skills and create better applications. By…

The last week of not posting has been spent down in the weeds of backtracking algorithms.  At the suggestion of my mentor, I spent all of yesterday converting my already-functioning algorithm into a pair of classes (MoveObj and DanceObj).  He was right: object-oriented is totally the way to go here.

Right now the algorithm produces dances that are the right length where each move can legally flow to the next.  Still to be done are heuristics to ensure actual danceability.  The algorithm doesn’t yet know how dancers are positioned going into a right hand star, so it doesn’t know not to assume that they can transition out of it to a move that follows the star in one of its seed dances.

As another example, the algorithm knows that a 4-beat swing can follow another 4-beat swing and it knows that moves should not cross between 16-count phrases of music, but it doesn’t know that two consecutive 4-beat swings should be treated instead as an 8-beat swing and are not allowed to cross the phrase.

Only about one in eight moves has a strange rule like the above.  This is where object orientation really becomes advantageous - instead of clogging the algorithm with endless exceptions for specific moves, the exceptions can be stored within the individual objects’ data.

As an extra bonus, switching to object orientation is the simplest way to cut down on database queries available to me.  My old approach was to query the database every time the algorithm needed to know the length of a move in the dance (and not store the answer, so that it had to redo the same query several times).  This meant potentially thousands of queries per dance built.  As I added more heuristics, the runtime got longer and longer.

Now with OO, the algorithm just makes two queries - once to pick a progression (the first and last moves of the dance), and one to build out MoveObj objects that contain all the information about the move (beats, possible next moves, maximum repeats, etc.).  The same outcome is achieved as before, but orders of magnitude faster.  This approach wouldn’t work for an enormous set of data (building the objects when the program runs takes memory), but for this problem, it’s perfect.

I’ve got to run back to lecture, but here’s a picture of where the output in the browser is at now:

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.