Saxophone is a solo instrument. Unless you are into the sounds of Saxophone multiphonics, harmony requires playing with some other instrument. For Jazz, this tends to be a rhythms section of Piano, Bass, and Drums. As a kid, my practicing (without a live Rhythm section) required playing along with pre-recordings of tunes. I had my share of Jamie Aebersold records.
Nowadays, the tool of choice for most Jazz muscians, myself included is iReal Pro. A lovely little app for the phone. All of the Real Book tunes have their chord progressions been posted and generated. The format is simple enough.
But it is a proprietary app. While I continue to support and use it, I am also looking for alternatives that let me get more involved. One such tool is Musical MIDI Accompaniment. I’m just getting started with it, and I want to keep my notes here.
Look back at our Pushing Keystone over the Edge presentation from the OpenStack Summit. Many of the points we make are problems faced by any application trying to scale across multiple datacenters. Cassandra is a database designed to deal with this level of scale. So Cassandra may well be a better choice than MySQL or other RDBMS as a datastore to Keystone. What would it take to enable Cassandra support for Keystone?
You might be thinking that this is a long solved problem. I think I have something a little bit different.
This is very similar to the C++ based one that I wrote long ago.
If you are going to write a Sudoku solver, write a brute force, depth first search. You can get it running fast enough.
But what if you couldn’t? What if the puzzles were so big that solving them by brute force was not computationally feasible? A Sudoku puzzle is build on a basis of 3: The Blocks are 3X3, there are 3X 3 of them in the puzzle, and the rows and columns are are 9 cells (3 * 3) long. This approach scales up. If you were to do a basis of 4, you could use the Hexadecimal digits, and have 16 X 16 puzzles.
A Basis of K leads to a puzzle size of (K^4). The basis can be any integer. A Basis of 10 would lead to a puzzle size of 1000.
The Sudoku puzzle shows exponential growth. https://en.wikipedia.org/wiki/Combinatorial_explosion#Sudoku
What could you do for a complex puzzle? Use heuristics to reduce the problem set to the point where a the brute force algorithm can complete.
Now that the algorithm does not need a new test_board every time, we no longer need to treat the Node object as a Flyweight. We can move the board into the Node object and remove it from the parameter list of all the functions that operate on it.
The code in tree_to_solution_string mixes the logic of solving the puzzle with the management of a linked list. Splitting your attention between these two levels can make it hard to track down errors. To continue teasing these two aspects apart, we need to make heavier use of the iterator. We’re in the middle of it now, and the code might actually feel like it is more of a mess than when we started. That is common, natural, and nothing to be afraid of.
Well, unless we get directed on to a different task tomorrow. Lets finish this up tonight.
In a previous article, I had to shorten a bunch of lines that had a row and column value used as indexes to the board array. This repeated pattern is a call-to-action.
We want to encapsulate the logic for referring to a particular place on the board, and for advancing through the board. This is the responsibility of the Iterator pattern.
Spoiler Alert: we don’t get all the way there in this article.
This refactoring is my bread and butter. Functions tend to grow. Eventually, you need to split them. Find a section of the method that has its own self-containerd reason- for existence, and make that its own function.
I have in the back of my head that I want to extract a class that abstracts the boards from this code. I’ve been resisting the urge thus far, as keeping the board as a 2D array of cells is really conducive to sharing with other implementations of this code. However, the following refactoring should work to support either direction: pull out the code that constructs a board from the string. This has the added benefit of making it possible to write a unit test that calls tree_to_solution_string without having to parse all of the strings.
As the refactoring process continues, we will continue to decompose the large central class and functions. Right now, the SudokuSolver class is performing two functions. It is holding and managing the list of the puzzles, and it is solving them.
The heart of this code is the function tree_to_solution_string. Right now, I can’t call that by itself, as the SudokuSolver creates a bunch of helper objects before running through the whole set of tests. how can we tease this apart?
While writing the last article, I noticed that I had made a bunch of little changes to the files without explicitly meaning to. I didn’t include them in the diffs. However, on my screen, I have a bunch of changes that appear to be…not changes: