# actionshrimp.com

fun and geekery

19  11 2012

## Shortest Knight Moves from a to b in Haskell

Posted by Dave | Tags: , ,

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!

``````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:

``````*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.

17  06 2012

## jasmine-node –autotest with vim on OSX

Posted by Dave | Tags: , , , , , , , ,

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.

06 2012

## Setting up a client side JS development environment with node.js – Part 2

Posted by Dave | Tags: , , , , ,

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:

## 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",
}
}
``````

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:

``````{
...
"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.

## 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.

06 2012

## Setting up a client side JS development environment with node.js – Part 1

Posted by Dave | Tags: , , ,

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

``````#!/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

``````var express = require('express');
var assets= require('connect-assets');

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

app.configure(function() {
app.set('views', __dirname + '/views');
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

``````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:

``````!!!
html
title= title
!= css('master')
body!= body
``````

``````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.

19  05 2012

## Getting underway

Posted by Dave

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.

12  05 2011

## Speech Bubble Popups containing a View for Android MapView

Posted by Dave | Tags: , , , , , ,

Update May 2012: There have been lots of requests in the comments for the source. Sorry for the delay on this one – I finally put the whole app that I’d been working on up on github. The part from this tutorial specifically is here if you want to take a look.

I’ve recently been playing around with Android, and have been building a small app that uses MapView to display various locations on the map. I succeeded in drawing markers on the MapView using ItemizedOverlay, but was having a fair bit of difficulty drawing little bubble popups that appeared when you tapped on the OverlayItems (which unfortunately isn’t available in the API as a ‘standard’ feature).

My main problem was I wanted to be able to draw a full View on top of the map at the right location. I had a good old search on Google for a while, and couldn’t seem to find any easy way to do this, so I thought I’d write up how I ended up with the bubble in the screenshot. (Now I know how it’s done however, the Google results seem a lot more knowledgeable on the subject – I was probably searching for the wrong things ).

My first approach was to build a subclass of Overlay and override its draw() method, where I converted the View to a Drawable to draw it directly onto the MapView canvas (passed to draw() ). This worked, but naturally events would no longer work properly in the View if it contained things like buttons, so it was back to the drawing board.

Next, I tried subclassing Dialog, and used a custom Dialog theme with my bubble background. The View I wanted was just injected into the Dialog through its setContentView method. This worked again, but I found myself fighting with the Dialog class a fair bit, and positioning it turned out to be a bit fiddly – there had to be a better way.

Finally I noticed that MapView inherits from the Android ViewGroup, which means it can contain other Views. After a bit more probing, and a peek at the implementation of android-mapviewballoons (which is excellent, but didn’t quite fit my purposes due to lack of custom balloon layouts) found a way to do it which should probably have been obvious from the outset!

The general approach is to add a new child View to the MapView, and then use the MapView.LayoutParams to position it. Here’s a quick outline example if you’re unfamiliar (the View I’m displaying has a NinePatch as the background attribute of a top level LinearLayout, which makes the bubble wrap the content):

This is in the initial activity setup – my balloon is re-used for all OverlayItems drawn on my map:

``````//Reference to our MapView
MapView mapView = (MapView) activity.findViewById(R.id.mapview);

//Get a LayoutInflater and load up the view we want to display.
//The false in inflater.inflate prevents the bubble View being added to the MapView straight away
LayoutInflater inflater = activity.getLayoutInflater();
LinearLayout bubble = (LinearLayout) inflater.inflate(R.layout.bubble, mapView, false);

//Set up the bubble's close button
ImageButton bubbleClose = (ImageButton) bubble.findViewById(R.id.bubbleclose);

bubbleClose.setOnClickListener(new View.OnClickListener() {
public void onClick(View v) {
bubble.setVisibility(View.GONE);
}
});
``````

This next part is the important bit, and actually positions the bubble on the MapView using MapView.LayoutParams. It’s called by the onTap method of the ItemizedOverlay that contains my map markers:

``````private void displaySearchResultBubble(final SearchResult result) {

map.removeView(bubble);
bubble.setVisibility(View.GONE);

TextView venueName = (TextView) bubble.findViewById(R.id.venuename);
venueName.setText(result.getName());

TextView venueTime = (TextView) bubble.findViewById(R.id.venueopenfor);
venueTime.setText("Open for " + result.getOpenFor() + "h");

TextView venueFee = (TextView) bubble.findViewById(R.id.venuefee);
venueFee.setText("Entry fee " + result.getPrice());

MapView.LayoutParams params = new MapView.LayoutParams(
LayoutParams.WRAP_CONTENT, LayoutParams.WRAP_CONTENT,
result.getPoint(), MapView.LayoutParams.BOTTOM_CENTER);

bubble.setLayoutParams(params);

map.measure(MeasureSpec.makeMeasureSpec(0, MeasureSpec.UNSPECIFIED), MeasureSpec.makeMeasureSpec(0, MeasureSpec.UNSPECIFIED));

Runnable r = new Runnable() {
public void run() {
bubble.setVisibility(View.VISIBLE);
}
};

Projection projection = map.getProjection();

Point p = new Point();
projection.toPixels(result.getPoint(), p);

p.offset(0, -(bubble.getMeasuredHeight() / 2));
GeoPoint target = projection.fromPixels(p.x, p.y);

mapController.animateTo(target, r);

}
``````

That’s it! It’s a fairly quick example but feel free to let me know in the comments if you want any more detail.

04 2011

## Vim XPath Plugin

Posted by Dave | Tags: , , ,

I’ve built a plugin that adds XPath search functionality to Vim. Check out the demo video below.

Features:

• Quick XPath search input with smart, context-sensitive tab completion
• Results shown in a pop-up results window. Jump to the line of a matching result easily.
• Debug invalid XML – jump to the the line number of an XML error from the results window

Requirements:

• Python support enabled in Vim
• lxml library installed for Python (ideally 2.7 or higher).

https://github.com/actionshrimp/vim-xpath

Let me know what you think / any improvement suggestions in the comments below.

15  08 2010

## Streaming Spotify to a PS3 from Ubuntu

Posted by Dave | Tags: , , , , , ,

A post came up a couple of days ago on the Spotify “What’s new” feed: how to stream spotify wirelessly to your stereo, which got me thinking about something I’ve been after for a while – the ability to stream spotify audio to PS3. This is mentioned in the link, but the main method they talk about is for Windows, and a solution for mac is touched upon. I figured I’d have a go at doing this on Ubuntu.

Before you have a go at this, I should mention a slight drawback – there’s a fair delay on the audio steam that reaches the PS3, around 20 or 30 seconds. This makes it good for playing a playlist as background music, but if you’re wanting to be able to flick around loads of different songs then you might get a bit frustrated. Read on if you’re still keen…

04 2009

## CakePHP: PagesController with Admin Routing

Posted by Dave | Tags: , , , , ,

Note this page was first published in April 2009, so is likely to be quite out of date now.

For small Cake websites with admin routing enabled, I like to use the Auth component to require a login for all admin routes, and allow access to everything else using the following beforeFilter in the AppController superclass:

``````function beforeFilter(){
} else {
\$this->Auth->allow();
}
}
``````

The problem with this however is static pages handled by the pages controller cannot be password protected. To resolve this problem, I had to overload the PagesController class that Cake comes with, and add in the required functionality. Part of the reason for doing this for me was to allow a setup where there was a password protected admin welcome page or control panel located at my_app_URL/admin, so I’ll show you the necessary routing to achieve that too.