Shortest Knight Moves From a to B in Haskell

I’ve got back onto the excellent ’Learn you a Haskell for Great Good’ recently, which I would highly recommend.

Near the end of chapter 12 (about Monads), there is a section on the list monad, which has an example ‘a knight’s quest’ at the end. Modification of the example code to print out possible routes from one position to another is left as an exercise to the reader. I decided to give it a go in attempt to solidify my knowledge about monads a bit, and below is the result.

I’m sure there are far more efficient ways of doing this, and potentially more monad-y ways of implementing shortestMovesFor, so if any other beginners come across this, I’d be interested to see what you came up with!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import qualified Control.Monad as M
import Data.List

type KnightPos = (Int, Int)

--As given in learn you a haskell
moveKnight :: KnightPos -> [KnightPos]
moveKnight (c, r) = do
    (c', r') <- [(c+2, r-1), (c+2, r+1), (c-2, r-1), (c-2, r+1)
                ,(c+1, r-2), (c+1, r+2), (c-1, r-2), (c-1, r+2)
                ]
    M.guard (c' `elem` [1..8] && r' `elem` [1..8])
    return (c', r')

--moveKnight, but modified to apply move n times
moveNWithHistory :: Int -> [KnightPos] -> [[KnightPos]]
moveNWithHistory n (current:history) = do
    if (n > 0) then do
        nextMove <- (return current) >>= moveKnight
        moveNWithHistory (n-1) =<< return (nextMove : current : history)
    else return (current:history)

shortestMovesFor :: KnightPos -> KnightPos -> [[KnightPos]]
shortestMovesFor start end = map reverse (filter (endsOn end) historiesForMinN) where
    endsOn target (current:history) = (target == current)
    Just historiesForMinN = find (any (endsOn end)) (map (\n -> moveNWithHistory n [start]) [0..])

And here’s some example output:

1
2
*Main> shortestMovesFor (1,1) (3,4)
[[(1,1),(3,2),(5,3),(3,4)],[(1,1),(3,2),(1,3),(3,4)],[(1,1),(2,3),(4,2),(3,4)],[(1,1),(2,3),(1,5),(3,4)]]

As you can see it returns a list of the shortest chains of moves from the start square to the target square.

Changes I made to the code from the book:

  • moveNWithHistory is a new function to apply moveKnight n times. It also generates a list of chains of moves for a given n, rather than just the final positions (by passing nextMove : current : history to the next iteration, rather than just the next move).

  • shortestMovesFor is not monadic, and returns the final list of moves. We first generate all move chains from our starting position for increasing n, until we find the smallest n which creates a set of chains that contains a chain ending on the target square. We then filter down the set we found to return only chains that do end on the target square. Finally we map reverse over the chains to make them more readable.

Jasmine-node –autotest With Vim on OSX

My last post was about setting up jasmine-node. I had this all in place, and was getting ready to dive into some development, hoping to use the --autotest feature to help with TDD. I fired up jasmine-node with

jasmine-node --autotest --coffee spec

At first glance it looked like everything was working correctly. All specs ran the first time, and when I made a change to a file the specs in just that single file were run. However, any subsequent changes to the file then no longer caused the test runner to trigger automatically.

At first I assumed this was an issue with node.js’ implementation of fs.watch, which at the time of writing appears to have quite a few issues open against it. After looking at the changelog for some recent node releases, it looked like there were some fs.watch fixes, so I updated to the latest version at the time (v0.6.19). Still no joy - I was having the same problem.

Next I decided to have a poke around in the jasmine-node code itself and see if I could find any problems. The area of code in question is the file jasmine-node/lib/jasmine-node/autotest.js. There is the call to fs.watch, which takes a callback that takes the event as its first parameter:

var watcher = fs.watch(file, function(ev) {
    ...

According to the node documentation for fs.watch:

The listener callback gets two arguments (event, filename). event is either ‘rename’ or ‘change’, and filename is the name of the file which triggered the event.

I found that when saving a file in vim, the ‘rename’ event was being triggered, rather than the ‘change’ event, which gave me a clue to what was happening. I then tracked down this post on stackoverflow which seems to describe a similar problem, only with the python library watchdog. Watchdog uses kqueue to implement FS monitoring on OSX - the same implementation as node.

What’s happening is vim’s use of .swp files is triggering rename. I assume after swapping, kqueue continues to monitor the swapped file rather than the actual filename we’re interested in. The workaround that watchdog suggests is to set noswapfile in your .vimrc, which is a solution that some people might be happy with. However as much as I love vim it does occasionally crash on me, and losing changes that would be stored in a swp file during a crash isn’t too appealing.

I fiddled around with the autotest.js file to try and get kqueue to set up a new watch on the swapped file briefly, without much success (often the file being swapped in hadn’t been moved yet, so node would throw errors saying the file wasn’t found). My solution was to instead change the call to fs.watch to use fs.watchFile instead, which slots in exactly in place with the same arguments:

var watcher = fs.watchFile(file, function(ev) {
    ...

The documentation recommends using fs.watch instead of fs.watchFile where possible, but in this case it doesn’t look like it cuts the mustard. fs.watchFile is a little less snappy that fs.watch (it polls the file’s last modified date to see if there are changes, rather than using an event driven system like kqueue), but it definitely does the trick for now and allows a nice TDD workflow. As it’s for testing and won’t be in live code I can’t see it causing too much harm.

If anyone knows of a better way of getting this working then please let me know below in the comments! I’ll update if I find a nicer workaround too.

Setting Up a Client Side JS Dev Environment With node.js - Part 2

This is another post in my puzzli series.

I’ve already set up node in part 1, to serve up a simple page to use as a JS development environment. Next I’ll be setting up jasmine so I can do TDD on the client side code for puzz.li. This commits for this post are from where we left off on the previous post, up to this commit.

First a quick diversion about dependency management. Up until now I’d just been doing:

npm install <modulename>

However unless I check all the node_modules I’ve added into git, as more and more dependencies are added deploying the app elsewhere will become a bit tricky. The solution to this problem is to create a package.json file, where you can define dependencies. This is what mine looks like so far:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
## package.json
{
    "name":         "puzz.li",
    "version":      "0.0.1",
    "description":  "A puzzle website",
    "homepage":     "http://puzz.li",
    "repository":   {
                        "type": "git",
                        "url":  "https://github.com/actionshrimp/puzz.li"
                    },
    "author":       "Dave Aitken <dave.aitken@gmail.com>",
    "licences":     ["MIT"],
    "dependencies": {
                        "express": "2.5.9",
                        "connect-assets": "2.2.0",
                        "jade": "0.26.0"
                     }
}

As you can see it gives a bit of info about the package itself, as well as defining the dependencies to get it up and running. Now when checking the app out from the github repo, it just requires a single command:

npm install

and all the dependencies of the right version will be grabbed automatically as you’d expect.

Back to setting up jasmine now. We kick off by install jasmine-node, a module that sets up jasmine nicely in a node environment, and supports specs written in coffeescript as well. As we (hopefully) won’t need jasmine-node to actually deploy the app to production, we can add it into package.json as a devDependency like so:

1
2
3
4
5
6
7
{
    ...
    "devDependencies": {
        "jasmine-node": ">= 1.0.26"
    }
    ...
}

and again

npm install

Finally, we just need to set up a simple link to jasmine’s script runner so it’s nice and accessible:

$ ln -s node_modules/jasmine-node/bin/jasmine-node run_specs
$ chmod u+x run_specs

Let’s see if everything’s working by trying to get a simple always-true spec running.

1
2
3
4
5
## spec/jasmine_spec.coffee

describe 'Jasmine', ->
    it 'should be set up correctly', ->
        expect(true).toBeTruthy()

and now we run it with our new command:

$ ./run_specs --coffee spec

.

Finished in 0.008 seconds
1 test, 1 assertion, 0 failures

We’re finally in a position to get underway with actually building something, and that will be the subject of the next post.

Setting Up a Client Side JS Dev Environment With node.js - Part 1

This is another post in my puzzli series. This post documents getting node set up to create a simple environment to work on the client side JS code in. I could potentially just use a static web page to begin with and start the basics of the client side in there, but I may as well set up a simple server side so I can stub in any server side endpoints as they arise. I’ll also get good ease of install and use of coffeescript and other JS ecosystem stuff. If you want to see the final code, this post runs from the start of my puzz.li repo up until this commit.

I already had node installed through the download from the node website - the installer is a cinch on OSX. I’m going to use the express web framework for node:

npm install express

I’ll also use the rails-style asset pipeline middleware for the node connect layer (which express uses), connect-assets:

npm install connect-assets

This should take care of auto-compiling my CoffeeScript when it gets sent down to the client side. Finally I’ll be starting off with the jade template engine which seems to have good support by default with express, although I may well swap this out for something else down the line:

npm install jade

Next, getting underway with a bit of boilerplate (always happy to know if any of my code looks a bit off or there is a better way of doing anything, please let me know :-)):

boot.js

1
2
3
4
5
#!/usr/bin/env node 

var server = require('./');
server.listen(3000);
console.log("Express server listening on port %d in %s mode", server.address().port, server.settings.env);

index.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
var express = require('express');
var assets= require('connect-assets');

var app = module.exports = express.createServer();

app.configure(function() {
    app.set('views', __dirname + '/views');
    app.set('view engine', 'jade');
    app.use(express.bodyParser());
    app.use(express.methodOverride());
    app.use(app.router);
    app.use(assets());
    app.use(express.static(__dirname + '/public'));
});

app.configure('development', function(){
    app.use(express.errorHandler({ dumpExceptions: true, showStack: true }));
});

app.configure('production', function(){
    app.use(express.errorHandler());
});

//Set up basic routing
require('./routes.js')(app);

routes.js

1
2
3
4
5
6
7
module.exports = function(app) {

    app.get('/', function(req, res) {
        res.render('index', {title: 'Puzzli'});
    });

}

This should be enough to get a server up and running, and serve up the first couple of pages:

layout.jade

1
2
3
4
5
6
!!!
html
  head
    title= title
    != css('master')
  body!= body

index.jade

1
2
h1= title
p Welcome to #{title}

Looks like it’s working so far. Up next I’ll be setting up jasmine for TDD on the client side, and then getting underway with building something.

Getting Underway

I need to write more code. I also need to write more blog posts. As a result, I’m combining my efforts for my latest mini-project.

The idea: a small website with a few standard puzzle “templates”. People who tackle daily newspaper puzzles (codewords, sudoku, crosswords) can fire it up, quickly enter that days puzzle for their own personal use, then solve it more easily than with a pencil and paper using auto-complete, easy undo, and possibly some kind of hint system. I admit the idea is perhaps slightly flawed due to lack of overlap between daily newspaper puzzle tacklers and the kind of people who’d use a website to make daily puzzle solving more efficient. It should be fun to make anyway.

I want the interface to be nice and slick and efficient which will involve a lot of javascript (I have some experience with backbone.js, which I intend to use again). I’ve also scratched the surface of server-side javascript with node.js in the past, and would like to delve into it properly. To start with I think the server will just be used mostly to serve up some static content, which I’ve heard is not really node’s strongest point, but it has nice support for javascript tech in general (in particular coffeescript), and should be a nice easy way to get something up and running quickly. If it then expands out into something slightly more complicated, then having all the components in JS should save quite a few integration headaches. I doubt the backend will ever be particularly wild though, but if goes that way I’ll worry about that problem and potentially switching when the need arises. The posts will all be added under the ‘Puzzli’ category.