Mams sine smykker

Min kjære mor har endelig begynt å eksponere sine smykker på nett!

Søk på google: Berits Smykker, der kommer den som nr. 1 eller 2, eller gå rett inn på Berits Smykker.

Flott, ikke sant!

Dijkstra's shortest path algorithm in Groovy

Groovy is really great for trying out algorithms without having to write tons of code.

The other day we were elaborating over how to make a route planner for public transport.
In its simplest form, this can be solved by using Dijkstra's shortest path algorithm.

But I couldn't find any groovy versions of this algorithm. I found a decent java version (I've copied parts from it, see see Renaud Waldura's blog), but the amount of code is still measured in pages, not lines of code.

With groovy, I think, we're approaching the simplicity of the algorithm.

class DijkstrasShortestPathAlgoritm {
    def graph, start, destination    
    // PriorityQueue performs much better than List - O(log(n)) for poll.    
    def unsettledNodes = new PriorityQueue<String>(100, new Comparator<String>() {
       public int compare(String node1, String node2) {
            shortestDistance(node1).compareTo(shortestDistance(node2))
        }
    });
    def shortestDistances = [:]
    def predecessors = [:]
    def settledNodes = [] as Set

    DijkstrasShortestPathAlgoritm(graph, start, destination) {
        this.graph = graph
        this.start = start
        this.destination = destination

        unsettledNodes.add(start)
        shortestDistances[(start)] = 0
    }

    int shortestDistance(node) {
        shortestDistances.containsKey(node) ? shortestDistances[node] : Integer.MAX_VALUE
    }

    def extractMin() {
        unsettledNodes.poll()
    }

    def unsettledNeighbours(node) {
        graph.findAll { edge ->
            edge.node1 == node && !settledNodes.contains(edge.node2)
        }
    }

    def relaxNeighbours(node) {
        unsettledNeighbours(node).each { edge ->
            if (shortestDistance(edge.node2) > shortestDistance(edge.node1) + edge.distance) {
                shortestDistances[edge.node2] = shortestDistance(edge.node1) + edge.distance
                predecessors[edge.node2] = edge.node1
                if (!unsettledNodes.contains(edge.node2)) {
                    unsettledNodes.add(edge.node2)
                }
            }
        }
    }

    def calculateShortestPath() {
        while (!unsettledNodes.isEmpty()) {
            String node = extractMin()
            if (node == destination) {
                break
            }
            settledNodes += node
            relaxNeighbours(node)
        }
        shortestDistances[destination]
    }

    private def getShortestPath(node, path) {
        node == start ? [node]+path : getShortestPath(predecessors[node], [node]+path)
    }
    
    def getShortestPath() {
        getShortestPath(destination, []) 
    }
}

And then, to find the shortest path of a graph, you do like this:

class Edge {
    String node1, node2
    int distance
}
graph = [
    new Edge(node1:'a', node2:'b', distance:4),
    new Edge(node1:'a', node2:'c', distance:2),
    new Edge(node1:'b', node2:'c', distance:3),
    new Edge(node1:'c', node2:'b', distance:1),
    new Edge(node1:'c', node2:'d', distance:5),
    new Edge(node1:'b', node2:'d', distance:1),
    new Edge(node1:'a', node2:'e', distance:1),
    new Edge(node1:'e', node2:'d', distance:4)
]
def dijkstra = new DijkstrasShortestPathAlgoritm(graph, 'a', 'd')
d = dijkstra.calculateShortestPath();
assert d == 4
assert dijkstra.shortestPath == ['a','c','b','d']

Of course, the public transport domain have a lot of special rules, such as favouring routes with few connections, indirect connections made by walking between stops, buses that dont stop a specific place every second friday, etc. etc. Each and every rule may not be so difficult to solve, but the sum of the rules makes the route planner domain really complex.

Also, there are other, possibly better, algorithms for route planning, one of them being the A* algorithm.

Grails autotest

A year ago I stumbled upon ZenTest / autotest, a simple, but great tool for test-driven development with Ruby or Rails. It runs a subset of your tests whenever you change some source, and keeps you notified whenever something fails.

There was only one problem. It works on ruby and rails only, not on groovy or grails. I assume you could set up Hudson or whatever to do something similar, but for small projects I need something much simpler than that.

So I wrote a tiny bash script that does kind of the same as autotest, but on a grails project. It runs all tests whenever some source change, and keeps nagging you with this message if it fails:

This notification will stick as long as the tests fails, and change into this when tests succeededs:

This notifiction will fade away.

Growl is used for notification. Here´s the script:

#!/bin/bash

#
# Run grails tests continously.
#
# Author trygve.amundsen@gmail.com
#
logfile=.grailsAutoTest.log
last_filestatus=""
imagesDir=`dirname $0`/images
curdir=`pwd`
project=`basename $curdir`
echo "Starting autotest for $project"

while true; do
    current_filestatus=`ls -lR grails-app lib scripts src test web-app/js web-app/css \
                       *GrailsPlugin.groovy | md5`

    if [ "$current_filestatus" != "$last_filestatus" ]
    then
        last_filestatus=$current_filestatus
        echo -n "Running tests..."
        grails test-app > $logfile 
        tail -3 $logfile | grep -q 'Tests PASSED'
        if [ $? -eq 0 ]
        then
            echo "Tests PASSED - waiting for changes..."
            growlnotify -m "Grails AutoTests succeeded" -t "Test $project" \ 
                        -d "$project" --image $imagesDir/succeed.jpg
        else
            last_filestatus="failed"
            tail -3 $logfile | head -1 
            growlnotify -s -m "Grails AutoTests failed" -t "Test $project" \
                        -d "$project" --image $imagesDir/fail-icon.png
        fi
    fi
    sleep 2
done

Maybe I'll come back with at groovy version of the script later on.

Bootstrap

Dette er mitt første blogg-innlegg.

Alle tidligere forsøk på å skrive blogger har strandet med at ambisjonene har vært større enn evnene. Jeg velger å gjøre et nytt forsøk, men øker samtidig maskevidden på selv-sensur-filteret en tanke. Jeg antar at noe søppel vil finne veien igjennom, men har bestemt meg for ikke å være så nøye på det.

Hvis ting går som jeg har tenkt så vil jeg skrive mest om programmering og relaterte greier. Emner som interesserer en ekte KodeMaker®.

Jeg kommer nok til å eksperimentere med både form og innhold, og vil sikkert prøve meg både på norsk og engelsk, for å se hva som funker best.

Jeg har ingen anelse om hvor hvor det bærer. Men det er jo spennende i seg selv.
Nok prat. Disse linjene har allerede tatt alt for lang tid å skrive, og har ingenting med kode å gjøre :)