Category: code

I’ve been writing a little recently about a program I wrote to solve sudoku and other problems using the dancing links algorithm.

This was how I explained it when someone asked for information about how it worked:

Firstly you have to understand Exact Cover. An exact cover problem is a problem where you’re given a bunch of choices, and a set of constraints and your challenge is to select a bunch of the choices that will fill every constraint exactly once.

For example, consider the case of someone creating their ice dance routine. They have a number of tricks that they need to show the judges, and don’t want to perform any trick more than once. They have a number of sequences which are groups of tricks that can be put together and they want to choose the ideal selection of sequences to cover all the tricks once. In this example, the constraints are that they must perform every trick. The choices are the possible sequences they could incorporate into their routine.

A nice way to represent problems of this sort is to draw out a table where the constraints are columns and the choices are rows, and you have a big X in cells where a particular choice fulfills that constraint.

As it turns out, given the right constraints and choices, sudoku can be described as an Exact Cover problem. It does involve 729 rows and 324 columns, which is perhaps why people tend not to use this technique when solving sudoku by hand.

Ok, assuming you’ve got that, now you need to understand Algorithm X. Knuth said of it “Algorithm X is simply a statement of the obvious trial-and-error approach. (Indeed, I can’t think of any other reasonable way to do the job, in general.)”. You can actually work through this by hand if you have pencil and eraser and the table drawn out in pen as I described in the previous section. Here’s my description of algorithm X:

1. If your table has no columns, stop – you’ve solved it. If you’ve got a partial solution stored, then it’s actually a real solution, return it.
2. Select a column (representing a constraint).
3. Find a row with a cross in that column (representing a choice that fulfills that constraint). Add it to some kind of structure where you’re storing potential solutions. If you can’t find a row, give up – there are no solutions.
4. Assume that the row you found in 3 is in the solution, so remove all columns that it have an X in that row. While removing all those columns, also remove all rows that have an X in the columns you’re removing (because you’ve already satisfied the constraint, so you’re barred from choosing something that would satisfy it again).
5. Now recursively try to solve the reduced table. If you can’t, remove the row you tried from the potential solution structure, restore all the rows and columns you removed in steps 3 and 4 and try a different row. If you run out of rows, then give up – there are no solutions.

Now that you understand that, you can understand dancing links. Dancing Links is a way of implementing that algorithm efficiently. The key point of dancing links is that in a linked list, when you remove a node (which can be done efficently by modifying the pointers of its neighbours), the node that you’ve removed has all the information you need to add it back to the linked list (in the case that it turns out you were wrong when you guessed it was part of the solution). That plus the fact that if you make all your linked lists circular then suddenly you lose a lot of special cases is pretty much all dancing-links is.

I recently created a sudoku and polyonimo solver using javascript, node.js, jasmine, jsdoc, git & github, cloud9 and heroku.

These programs and services are not perfect, but the fact that you can slot them together to provide a complete, production-ready, web-based development infrastructure for free is amazing.

Javascript

When you’re working on javascript code, there are a number of environments you might want to be able to deploy to. For Dancing-links, I wanted the code I wrote to work in the browser, in node.js and, to allow me to click ‘debug’ in eclipse, I wanted it to work in Rhino too.

As far as I’m concerned Javascript is the only real write-once-run-anywhere language.

Having said that there are also a number of ways in which it is deficient and perhaps the worst is in terms of loading code you depend on. Each of those three environments I mentioned requires a different solution. I approached this by creating a piece of library code that faked up the way that node.js does it on the browser and in Rhino, a sort of fake ‘require’ function. In node.js the order doesn’t matter, because everything is cached and if the required module isn’t already there, it goes away and gets it.

Unfortunately, the way most people write javascript, the order does matter in the browser, which means you can’t just concatenate files together without understanding what they mean. To reduce this complexity, and make it easier to use the result in more places, I’ve made a concerted effort to remove ordering requirements. This means never actually constructing anything during ‘definition time’. This means removing patterns that look like statics and singletons. Where you can’t help it, using lazy instantiation can get round some problems.

The other problem that crops up is inheritance. I allow myself the luxury of having a single ordering requirement: Utils.js will be included before anything else. In Utils.js I fake up require where it doesn’t exist and also provide an inheritance mechanism that sets up the inheritance prototype chain immediately or sets a trigger to set up the inheritance mechanism when the super class is included. This is a first cut at this, so I’m not completely happy with it yet, but I think something like this approach is the right one.

node.js

Node.js makes writing servers extremely easy. It has a large library of modules publicly available and easily accessed through the node package management tool.

It can be a bit of a shock for people used to the Java ecosystem though. Firstly in terms of cross platform, as things stand at the moment windows is definitely a second class citizen. Many important APIs don’t work correctly on windows – for example requesting the inode of a file will always return 0, which breaks code that uses that to check to make sure it doesn’t process files more than once. Jasmine used to fail on windows because of this, but they have graciously accepted my patch to use a library that doesn’t fall for this problem. Another nasty issue I hit was that the API for watching a filesystem for changes that is best specified and should be most compatible (because it uses a fallback behaviour where it is not available) is completely unsupported on windows – it just throws an exception telling you to use a much less specified API:

Providing filename argument in the callback is not supported on every platform (currently it’s only supported on Linux and Windows). Even on supported platforms filename is not always guaranteed to be provided. Therefore, don’t assume that filename argument is always provided in the callback, and have some fallback logic if it is null.

Like what? If you aren’t passed a filename how are you supposed to deal with a rename? The documentation is silent on this matter.

The fs.watch API is not 100% consistent across platforms, and is unavailable in some situations….. If the underlying functionality is not available for some reason, then fs.watch will not be able to function. You can still use fs.watchFile, which uses stat polling, but it is slower and less reliable.

…except of course you can’t, because on windows it just throws an error. Maybe if you were writing the code yourself this wouldn’t be quite so big an issue, but some of that large library of thirdparty modules I mentioned require this functionality to work.

My solution was to monkey patch it:

var os = require('os');

if (os.platform() == 'win32') {
	// change fs.watchFile so that it doesn't throw an error on windows.
	
	fs.watchFile = function(filepath, callbackfunc) {
		var old = fs.statSync(filepath);
		fs.watch(filepath, function() {
			fs.stat(filepath, function(err, newStat) {
				callbackfunc(old, newStat);
			});
		});
	};
}

which is of course far from ideal, but works well enough for my usecase. Another issue – the document talks about filenames and paths, but the code actually expects stat objects.

All this highlights another difference between the node community and other communities you may be familiar with. You will need to look at the source code of some of the modules you use. That’s just the way it is. Fortunately most of them are pretty reasonably coded. A common complaint of mine is that modules that expect you to use them from the command line tend not to provide a reasonable programmatic way of invoking them, and many tool-like modules don’t expect to be run more than once in the same VM and don’t provide the necessary API to clean up.

Node.js is amazing for writing servers very easily (and for integrating with some of the other tools I’m going to mention later), but I used it in dancing-links for two main reasons – the speed (much faster than rhino in eclipse) and as a build language.

When you are writing javascript you typically want to see it in a browser. You want the manual part of the build process to be at most control-s in the js file you’re editing and F5 in the browser you’re viewing your page in. However, you generally want a bunch of other stuff done in between the two, potentially like concatenation of separate js files, building the jsdoc, running the tests, obfuscation, perhaps building the .css files from some other format like less/sass/stylus. Then you need to serve all this to the browser. Setting up a node server to do all this is relatively easy (less than 70 lines) using mature libraries like express and connect-assetmanager.

For less webby builds, you might prefer to use travis.ci.

Node provides the node package manager, npm which makes it easy to declare and grab your dependencies as well as publish your own code to the public repository.

Jasmine

I’m not a great believer in making test code read like English. It seems that everyone is trying to do that these days with various contortions of the host language. I particularly hate fluent interfaces where the normal semantics of what functions and objects mean are broken. Code is code and should read like code. What I do like unequivocally though is test code that generates an English description of the code under test.

A CircularList,
  when newly created without any data,
    is empty.
    and a data item is pushed after it,
      toArray returns an array with only the new item.
      is not empty.
  when newly created with some data,
    has a next and a previous of itself.
    toArray returns an array with only itself.
    is not empty.
    and a data item is pushed after it,
      toArray returns an array with itself and the new item.
      returning a node that contains the data item
  when created with an (empty) header node and 5 data items,
    forEach calls its callback for all items (and their nodes) until false is returned.
    and the third node is hidden,
      toArray returns only the non hidden items.
      calls the onNodeHidden function once on the listener
      then restored,
        toArray returns all the data items.
        calls the onNodeRestored function on the listener
      and hidden is called a second time, it makes no difference;
        toArray returns only the non hidden items.
        calls the onNodeHidden function once on the listener
        then restored,
          toArray returns all the data items.
          calls the onNodeRestored function on the listener
    and a two item chain is spliced into it after the third node,
      inserts the new chain into the right place.

One place that jasmine is a bit of a pain is that really you would like everything at higher nesting levels to be recreated for every test (as Junit does for instance variables), however the lower nesting levels share things defined higher up. This means that to be safe, at most you declare the variables in the outer scope and all actual instantiations need to be done in a beforeEach().

What I’d like to do is generate HTML from the tests and serve the generated ‘spec’ with the documentation.

I did look at a number of other test frameworks, like Buster.js. My ideal requirements are

• Can be run entirely in node.
• Can be run entirely in the browser (but not capture mode) which means it can’t rely on node.js require behaviour.
• Can be run by my webserver every time a file changes.
• Creates a nice, readable spec document.
• Works on windows as well as other platforms.

jsdoc

It’s lovely to have jsdoc automatically built from your code and served from the build web server. My experience is that if you aren’t doing something like this it’s very difficult for developers to take jsdoc seriously. Jsdoc implementations for node tend to be a bit fragmented, and none of them seem to have a nice programmatic API. I ended up copying a lot of code from the cli runner of one implementation and writing my own.

If you’ve already got a js project on github, you may already have a jsdoc site without realising it. Have a look at jsdoc.info.

git & github

I’ve mainly been using git for personal projects rather than for large distributed projects, so I haven’t had to get into it properly. I’m disappointed with the very flaky integration into eclipse and the apparent lack of decent visual merging tools. Hopefully these things will improve given time.

Github on the other hand is an amazing service, I’ve heard it called ‘facebook for nerds’. Providing public repositories for free, you can use it as a central point to share your code, easily clone and submit patches to other projects, serve the project website from it, use the wiki and issue tracker, view diffs, make smaller changes directly through the site…. The list goes on. Partly because it’s so useful, ecosystems have grown around it. The django guys said it best: Github is Rome.

I should mention too that bitbucket is also a good service, which might be worth checking out, particularly if you have a small group of friends working on a private project.

cloud9

Cloud9 is a web based IDE. What is most impressive is its excellent integration with node and git. I’d go so far as to say that for developing a project with node and git, you might well be better off developing it in your web browser on cloud9 than in eclipse on a windows machine. You can do all your normal git commands in it, and also run node servers and npm commands. You can edit the code then run the unit tests through the built in console. It also gives you a single click deployment (assuming you’ve got all the files set up correctly) to cloud production level servers like heroku.

heroku

If you have your files set up right, heroku will take your node server and run it on a single instance. You can scale up by configuring heroku to give you more processes, but that costs money. Still, you get a single node.js process for free, and that is plenty for even a moderate load. I don’t expect it to survive getting posted to reddit (although you could also easily set up cloudflare for free….), but for almost anything else it’s going to be fine.

the ecosystem

What amazes me is that you can develop the whole thing in cloud9, using github as your source repository, running your tests and dev server on cloud9 too, then deploy with a single click to a production grade server all for free and without installing a single piece of software on the machine you develop from (except possibly Chrome). You could run major projects from a netbook, or an internet cafe from anywhere in the world. The cost now for setting up and running experimental services is probably as near to free as it can be made, and I look forward to seeing what happens as people discover how empowering that is.