Javascript Puzzlers

Here are a few javascript puzzlers. If you want to try them yourself, all of the statements below evaluate to true and you have to work out what values could make that happen…

Starting simply, name a value that is not === to itself:

    a !== a

And its dual – name two values that are different but do === each other. The second part of this puzzle is to provide a statement that can distinguish b and c. (clue – don’t look unless you’re stuck)

    b === c

What’s a value that seems to be the same as its complement (there are quite a few possibilities):

    !d == d

How about something that seems to give 42 more than you might expect (Can you find a second way of doing the same thing)?

    (e + 4 === 42) && ("4" + e.toString() === "42")

How did you do?

Dancing-links: The JS ecosystem

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.

Dancing-links: What Programming Is

Most people have no idea what ‘being a programmer’ is about. A common response when saying what you do is ‘oh, I couldn’t do that, staring at a screen all day’.

In the hope of communicating better, I’ve been trying out a few different responses. One I tried recently is “I solve abstract problems through the manipulation of symbols”. By itself it doesn’t actually help all that much but it does open up a whole realm of possible conversations that would normally be shut down by ‘oh I couldn’t do that, staring at a screen all day’.

What do I mean by abstract problem? Well, the sudoku in the paper on friday is a concrete problem. An abstract problem would be solving every sudoku. Solving the friday sudoku gives you the solution and some limited insight into how you got there. Solving the abstract sudoku problem gives you every solution for any sudoku you come across in the future, and an insight into what kind of thing sudoku actually is, what solutions are, and often what sorts of things are going on in the human brain, and what sorts of things would go on in the human brain if its ability to keep track of things without getting bored wasn’t hopelessly stunted.

Every time you tried to solve a sudoku and found yourself jotting little notes to help you keep track of more information than could reasonably be kept in your head you were reaching for solutions that were beyond what is practical in a normal human brain. If you ever started reading about ‘techniques’ or trying to work out all the different ways you can make progress on a sudoku, you were thinking about the abstract problem.

Solving the problem teaches you the solution. Solving the abstract problem teaches you about yourself and the nature of the world.

What does the solution to the abstract problem look like? The solution to the abstract problem has to be able to generate a solution to any of the concrete problems, so rather than a filled in grid, the solution to the abstract problem is a process that given a puzzle grid will generate the filled in grid. Both the concrete problem and the concrete solution can easily be printed in a newspaper but the abstract solution is a process which could be represented in many different ways none of which look anything like a sudoku grid, just as a recipe for cupcakes doesn’t look anything like an actual cupcake.

cat sleeping when it should be doing sudoku because this *is* the internet after all
A cat is not a good abstract solution to the problem of sudoku.

Still, while the abstract solution may be a process, we need a way to communicate it to other people, so we describe the process in words. As you come up with more and more abstract solutions, you discover that a lot of the parts of the process can be broken down into small steps that are used in all sorts of different abstract solutions. Amazingly, these steps are simple enough that they can all be done by machine, so you can build a machine that takes a description of an abstract solution and makes that process easily repeatable (which is in fact what a computer is).

One of the interesting things that comes out of finding the abstract solutions to problems instead of the concrete solution is that sometimes you find that the exact same abstract solution can be used to solve apparently different problems. Often this involves converting between different representations of the problem. For example, there’s no difference between a sudoku puzzle where the symbols you use are the numbers 1 to 9 or the same puzzle using the letters A to I. You can rotate a sudoku puzzle or flip it upside down, but it’s still essentially the same problem. Once you start thinking like this, you can make surprising discoveries, like the fact that tiling shapes into a chessboard can be solved with exactly the same abstract solution as sudoku.

For a time, it was hoped that perhaps all problems in the universe could ultimately be solved by one single master abstract solution, which would contain the answer to everything. Starting perhaps with logic and maths puzzles, and then ultimately, as we find better descriptions for the universe moving on to problems of physics, chemistry, biology and psychology. The german mathematician David Hilbert in the early nineteen hundreds was particularly associated with the first part of this task. The dream of being able to do this with everything looks pretty unlikely now that Gödel proved that any system that includes simple mathematics can represent problems for which it is unable to represent solutions, but there are many interesting stories in the history of logic puzzles, going back at least to Archimedes who proposed a maths puzzle about the ‘cattle of the sun’ which when solved gives an answer of more cows than could possibly fit in the visible universe.

In computing we call the process that is an abstract solution an algorithm after the Persian mathematician Muḥammad ibn Mūsā al-Khwārizmī from the 9th century House of Wisdom in Baghdad. One of the abstract solutions for solving sudoku (and n-queens, and shape tiling…..) is called Algorithm X, and an efficient way of keeping track of all the moving parts was named ‘dancing links’ by computing legend Donald Knuth (currently working for Google).

For fun, I’ve implemented dancing links here where you can see it solve sudoku and shape tiling (at the bottom of the page). It’s also a project that I created using particular tools and services; javascript, jasmine, node.js, heroku, jsdoc, cloud9, git, github and I will write a more technical blog about my experiences with those soon.

Game In A Day Challenge

Looking through my ‘project ideas’ page, I see that many of them rather ambitious – plans that would really require a minimum of a year of full time effort before seeing anything. They’re all really good ideas, but the chance of me actually doing any of them short of winning large amounts of money in a lottery is fairly slim.

I’ve been reading The Lean Startup recently, and one of the things that struck me is the importance of getting things in front of people quickly. It argues this from the importance of learning and appropriately acting in an uncertain environment, but perhaps even more important is in terms of your own motivation and focus.

So I set myself a challenge. Could I create a game and put it on the android market in less than a day?

You can see the answer here or if you don’t have an android phone here.

It’s designed to be played on a tablet, and you drag your green circle around while at the same time shooting at the yellow circles. It’s pretty simple, but reasonably fun.

I certainly learnt a lot, and one of the best things that came out of it was that it inspired me to spend a week learning and writing other things that came from it. I think that perhaps the biggest benefit setting myself a ‘1 day’ challenge is the effect it has on larger projects too.

The centre of the universe – 1665

The other opinion – followed by the Pythagoreans, Aristarchus of Samos and others long before Aristotle or Hipparchus or Ptolemy came into this world and returned to center stage by Nicolas Copernicus some one hundred years ago – is still approved by the most excellent mathematicians. It places the sun at the center of the universe as the soul of the world and governor of the universe, from which the earth and all the planets borrow their light. There they believe it to remain stationary, as we can see in the second figure…

Now it is not our intention here to specify which of these opinions is consistent with truth and best befits the natural order of the world. That is a question we must leave to those versed in the science of celestial matters. And for all that the earth, according to the Copernican hypothesis, moves annually around the sun in a circle whose diameter would be two million leagues from Germany, and that the sphere of the fixed stars would be of so vast an extent as to be utterly incommensurate with that of the sky around the earth, there is, nonetheless, no noticeable difference between this theory and the earlier one (according to which the earth is the center of the universe) in respect of the apparent rising and setting of the celestial bodies, the changing duration of days and nights and the other things that follow from this. But since the hypothesis of a fixed earth seems generally more probable and is, besides, easier to understand, this introduction will adhere to it, without for the present considering the other theories.

– Introduction to Geography, Joan Blaeu, Atlas Maior, 1665

(by the way, two million leagues is about the 1/75th of the true distance).

AV is not a good voting system. FPTP is worse.

The UK is currently running a referendum on whether to change the voting system from First-Past-The-Post (which is more naturally called ‘simple plurality’) to Alternative Vote (which is sensibly called Instant Runoff Voting in other parts of the world).

Having been interested in the technical details of voting systems (or ‘social choice theory’ as it’s also known), one of the big disappointments to me about the way the campaigns both for and against (as well as the media coverage) are being run is their lack of technical information. The Economist describes both campaigns as ‘insulting the publics intelligence’. There’s an awful lot of talk about things completely tangential to the voting system, such as whether soldiers have enough armour or not, lies being spread about supposed cost, and arguments in both directions about whether this moderate change for the better makes other changes more or less likely in the future, but so far I’ve seen nothing that tries to appeal to voters considered judgements rather than their emotions.

This is a shame because voting systems are essentially technical, and decisions about them should be made on an unemotional basis. In 1951 Kenneth Arrow published a book which expanded on his PhD theory that’s become known as Arrow’s Impossibility Theorem. In it, he takes a number of criteria that you would hope to be true of any voting system, and then proves that no voting system (with more than two options) can meet all of them. This doesn’t mean that all systems are equivalent of course, just that any voting system is going to be a trade off.

My personal favourite for a long time was a system called Ranked Pairs and some of its variants, although these days I do find myself swayed by the arguments of the range voting supporters. Wikipedia has an interesting table listing a number of voting systems by criteria that they meet.

Part of the difficulty is that it’s not clear whether the voting system should select winners who can most motivate one extreme of the political spectrum (commanding loyal support, and with a clear vision for moving forwards), or whether it should select winners with the most broadbased support (who will continuously have to hammer out compromises), or whether it should prioritise not selecting the most hated candidate (something that Plurality often does). Different systems strike that balance in different places and are good for different kinds of situations.

Plurality voting (FPTP) in the UK has led to a situation where your vote is either a vote for the government or a vote against the government (in which case you must vote with the nongovernment party most likely to win in your constituency). Other votes are interesting from a popularity contest point of view, but make no more difference to the make up of Parliament than those who stayed at home. Is it therefore any wonder that so many do stay at home.

Of course, the biggest injustice in our voting system is the lack of proportional representation. It is possible under the UK system for a party to win the majority of popular votes in the country and still not win a single seat in Parliament. While this is unlikely, as people’s political views become less associated with the area they live in, this becomes a bigger and bigger problem. It seems bizarre that the system rewards parties for having their supporters ghettoized, and this will become only more bizarre in the world of the internet. The Green Party already suffer from this kind of geographic diffusion disadvantage.

The Conservatives scuppered a referendum on anything that might address that issue, so the referendum is a choice between a poor system of choosing the single winner in a constituency (AV / IRV) and an even worse one (Plurality / FPTP). Neither of those systems support one of my favourite criterion – the Condorcet Criterion. The Condorcet Criterion is simply that if there is a candidate that is preferred to all of the other candidates then that candidate should win. Seems obvious, but neither IRV nor Plurality can guarantee it.

A related criterion that does separate IRV and Plurality is the Condorcet Loser Criterion. That is the idea that the most disliked candidate should never win. IRV satisfies that criteria while Plurality does not. It’s the interaction between this criterion and another known as ‘independence of clones’ that pushes our system towards two parties. Imagine that the Conservative candidate is preferred by 35% of the voters, and absolutely hated by the other 65% of the voters, however those 65% are split between 30% Labour, 25% Lib Dem and 10% Green. Every one of those other voters would prefer the Labour, Lib Dem or Green candidate to the Conservative candidate. The Conservative candidate is the most disliked candidate, however Plurality might still elect them despite the fact that 65% of the voters don’t want them. Because of this, under plurality, the opponents of the Conservative candidate need to concentrate their votes to Labour to ensure the Conservative doesn’t get in.

One problem with IRV is that the tactical voting that is so necessary in Plurality happens with IRV too, and when there is widespread tactical voting in IRV, the result is pretty much as bad as Plurality – two party domination etc. What often happens in countries that use IRV is that a party gives a suggested preference order to its supporters, and so even though tactical voting is more complex under IRV than Plurality, it becomes just as widespread. If IRV is the best system on offer to the population of the UK, I’d like to see rules that stop political parties from suggesting preference orders.

Something that is very interesting is that despite ambivalence or active campaigning against IRV from most of the political establishment, most opinion polls put the result fairly close. The people of the UK know that they need change, I hope that they also know that at best this is just a small step on what is probably quite a long road to a more sane voting system.

[This report brings out some of the technical issues. ]

Playing on the CouchDB

Let’s say you’re playing with CouchDB and javascript. It’s great fun, but you’re in development mode, you want to be able to change a file and then reload in your browser without having to mess around uploading and deploying stuff.

The ‘proper’ way of doing this is probably to set up a reverse proxy so that your couchdb is visible through your development webserver, and all is good, but that sounds like a lot of configuration for a playing around kind of setup.

What you’d like to do is run a normal couchdb install on your machine, and use whatever you normally do for webserving (for just playing around, I tend to use a jetty jar I’ve created as it’s very light and easy, but you could equally use tomcat or whatever), and edit the javascript and html files in place. If you have this set up, you can’t usually load the javascript couchdb api from the couchdb server, since it uses an XHR to communicate with the couchdb server, and these are restricted to using exactly the host that the page is loaded from. The fact that the couchdb server is on a different port to your webserver stops it from working.

You can get around this by saving a simple html document as an attachment in your couchdb (any database). This html document is then loaded in an iframe, sets the document.domain to the hostname (removing the port), and then it passes the api object up to the parent window.

https://gist.github.com/942047.js?file=couch-x.html

If you’ve attached that file to a document with id ‘document’ in a database called ‘webaccess’, you would then use it as below:

https://gist.github.com/942063.js?file=example.html

Tetravex

I’ve recently been playing a puzzle game called tetravex on Ubuntu, so I thought I’d write a version of it for HTML5. It’s designed to work on android phones and the iphone (only in vertical orientation at the moment), but if you’re using a modern browser you should see a working version of it below. The GUI still needs a lot of work, and I’m sure there are bugs, but pretty much all the functionality of the linux version is in there. On a phone, you can visit this direct link and then save it onto your homescreen to run it as an application. This should let it run offline too. It uses localStorage to store the high score table.

Update: Turns out it uses some features that Apple don’t support on iphone yet. I’ll try to make it more backwards compatible later. In the meantime, Chrome, Desktop Safari, Firefox and Android Browser should all work fine.

/tetravex