Archive for the 'Programming' Category

I’ve been meaning to write this for a while. It started when I camed across this page of the shortest sudoku solvers. They all follow the basic algorithm, which is described here. I orginally thought it was a brute force algorithm, so I wanted a more elegant solution, but on closer examination it in fact uses constraints and backtracking, like a Prolog program would. Still I wanted to write one in Prolog. It turns out it’s quite simple, and here is my program:

% Sudoku Solver
%
% Author: Miles Barr
% Version: 1.0
%
% Example Usage:
%
% Board = [ [_,_,3,_,4,9,_,_,8],
%           [_,1,_,5,_,_,_,3,_],
%           [8,_,7,3,_,_,_,_,_],
%           [_,6,8,9,_,_,_,_,5],
%           [2,_,_,_,_,_,_,_,6],
%           [4,_,_,_,_,6,7,1,_],
%           [_,_,_,_,_,5,9,_,3],
%           [_,8,_,_,_,1,_,6,_],
%           [9,_,_,2,3,_,1,_,_]
%         ],
% sudoku(Board),
% print_board(Board).

:- use_module(library('clp/bounds')).
:- use_module(library('lists')).

% Our general constraint is that each set of 9 (row, column or 3x3 grid) is made
% up from the numbers 1-9, and each number is not repeated.
valid(L) :- L in 1..9, all_different(L).

% Transpose function from Worksheet 16 of 'Clause and Effect'
transpose([[]|_],[]).
transpose(R,[H|C]) :- chopcol(R,H,T), transpose(T,C).
chopcol([],[],[]).
chopcol([[H|T]|R],[H|Hs],[T|Ts]) :- chopcol(R,Hs,Ts).

% Describe 3 grids in terms of 3 rows
% TODO: There must be a better way to do this.
grids([E11,E12,E13,E14,E15,E16,E17,E18,E19],
      [E21,E22,E23,E24,E25,E26,E27,E28,E29],
      [E31,E32,E33,E34,E35,E36,E37,E38,E39],
      [E11,E12,E13,E21,E22,E23,E31,E32,E33],
      [E14,E15,E16,E24,E25,E26,E34,E35,E36],
      [E17,E18,E19,E27,E28,E29,E37,E38,E39]).

% Print a board
print_board([]).
print_board([H|T]) :- write(H), nl, print_board(T).

% Sudoku solving function. 
%
% Input is nine lists of nine integers
sudoku(Board) :-
  % Break the board down into rows
  Board = [R1, R2, R3, R4, R5, R6, R7, R8, R9],
  % Transpose the board to get the columns
  transpose(Board, [C1, C2, C3, C4, C5, C6, C7, C8, C9]),
  % Cut up the rows into 3x3 grids
  grids(R1,R2,R3,G1,G2,G3),
  grids(R4,R5,R6,G4,G5,G6),
  grids(R7,R8,R9,G7,G8,G9),
  % Each row contains unique entries
  valid(R1), valid(R2), valid(R3),
  valid(R4), valid(R5), valid(R6),
  valid(R7), valid(R8), valid(R9),
  % Each column contains unique entries
  valid(C1), valid(C2), valid(C3),
  valid(C4), valid(C5), valid(C6),
  valid(C7), valid(C8), valid(C9),
  % Each grid contains unique entries
  valid(G1), valid(G2), valid(G3),
  valid(G4), valid(G5), valid(G6),
  valid(G7), valid(G8), valid(G9),

  % Turn the board into a list of 81 variables
  flatten(Board, Elements),
  %sign a value to each variable
  label(Elements).

I used SWI Prolog, but it should be trivial to port to other versions.

The general constraint is described by the valid clause, each list must contain all the numbers 1 through 9 exactly once. The list can represent a row, column or 3×3 grid. The next bit is breaking up the board into rows, columns and 3×3 grids, and then making sure each one is valid, which is what the sudoku clause does. That’s it really, and that’s what my first version looked like. In fact my original valid clause was:

valid(L) :- permutation([1,2,3,4,5,6,7,8,9], L).

and I didn’t constraint the values and do a labelling. That didn’t work, or it might work, but it takes a very long time. I came across this Prolog solver, which reminded me of labelling, so I removed the use of permutation, the result, a near instantaneous solver. I also borrowed his printing function.

It’s much longer than the other versions, but it has the nice property that you describe the constraints, and that’s your program, you don’t need to implement backtracking. There are still improvements to be made here, the most important one would be to add in some sort of heuristic to guide the backtracking, at the moment it’s naive and problem does more work than it needs to.

But is this the best way to solve a Sudoku puzzle? One other idea I’ve started thinking about is representing the board as a graph. We have 81 squares, each with 9 values, so we start off with 729 nodes. Each node represents a possible value for that square. Each value node for that square is connected to all the other value nodes of the squares next to it. As we discover the value of certain squares we can mark arcs to other values as illegal, and not use them in our path. Once we have a legal path through one value node for each square, we’re done. Ultimately this method requires the use of the same constraints, so it probably won’t be much better than the list based solution, but it could allow multiple walkers to discover legal row, column or grid paths in parallel, eventually joining them up. This parallelisation might lead to a faster solution. But I’ll leave the implementation and analysis to another time.

I just came across this post. It looks like there’s talk to introduce special operators for getters and setters in Java 7! The following two lines might be equivalent:

a.setFoo(b.getFoo());
a->Foo = b->Foo;

See page 27 of this PDF.

It’s just so wrong to me. The problem only exists because field access is done by static type, if they did the same lookup as they do for methods, we could just use ‘.’. If you wanted to do something different in a setter or a getter, then you could explicitly write a method.

The suggestions on page 28 make more sense, e.g. String support in switch blocks, and comparison operators for enums. But why not just give us generic support? Why can’t I use any object in a switch statement? Surely it could just invoke equals()? Similarly give me the chance to define what -> means, or add comparison operator support to any class I want. Then I wouldn’t mind stupid things like ->, but this whole, some objects are more equal than others thing when it comes to operators, and stupid operator definitions, that I can’t abide!

Here’s the first post, in hopefully what will be a relatively infrequent series. It’s going to cover stupid things I’ve done in Java, so you won’t make the same mistakes.

In this first post I’m covering a scenario where I was getting a NullPointerException on a field that is initialised on construction, i.e. it should never be null. Below is a set of classes that recreates the situation (I don’t know if it compiles or runs), see if you can spot the mistake:

public class X {
    private String someVar;

    public X(String someVar) {
        this.someVar = someVar;
    }

    public void doSomething() {
        // Does something with someVar
        this.someVar.length();
    }
}   

public class Y extends X {
    private static final Y INSTANCE = new Y();

    private static String SOME_CONSTANT = "blah";

    private Y() {
        super(SOME_CONSTANT);
    }

    public static Y getInstance() { 
        return INSTANCE;
    }
}

public class Main {
    public static void main(String[] args) {
        Y y = Y.getInstance();
        y.doSomething();    // NullPointerException happens here
    }
}

Did you spot it? In this example X.someVar will always be null because Y.INSTANCE is created before Y.SOME_CONSTANT, meaning doSomething() will throw a NullPointerException. It’s an odd bug because it makes you think about class initialisation and mixing static and non-static fields in your class. My mistake was thinking that constants (i.e. static final fields) are always set before you can instantiate a class, but in this example you can use it before it is set. I don’t think the compiler catches it because the first use of SOME_CONSTANT appears after it’s definition, but the declaration of INSTANCE jumps ahead of it causing the problem. So if you have a singleton, make sure you create it after the rest of your static fields.

Update 1: Dmitry spotted a couple of bugs in my code, and one that in fact shows the above case cannot happen. A variable declared as static final always gets initialised first, so the code I was working on must have omitted the final declaration hence causing the NullPointerException.

Update 2: I’ve modified the code above to now break as I described since some people are running it. See the comments for explanations on the full set of conditions for this bug to occur.

I came across this thread that simplifies the ical controller from my previous example. It correctly sets the content type header and removes the need for a template. The new version is:

class IcalController < ApplicationController

caches_page :competitions

def competitions headers[’Content-Type’] = “text/calendar”

cal = Icalendar::Calendar.new

Competition.find_all.each do |comp|
  event = Icalendar::Event.new
  event.start = comp.date
  event.end = comp.date
  event.summary = comp.name

  cal.add event
end

render_without_layout :text => cal.to_ical

end

I hadn’t used the render_without_layout command before, but it’s very handy for situations like this.

I was chatting to Simon the other day and the question of, should you have getters and setters in your Ruby classes, or should you just let other classes access the attributes directly, came up. We were talking about ActiveRecord, which dynamically creates them for any columns in the table the class is representing.

The short answer is, if you want other classes to access that data, yes, you need getters and/or setters, but for different reasons that you might think if you come from a Java world. Getters and setters are one of my pet peeves in Java. I hate it when I see them thrown in by default for every field in the class, reducing it to nothing more than a C struct.

The good reason for not allowing direct access to a field in Java is data encapsulation. By making it private you can decide if it’s read-only or read/write (or neither). But I think this is a poor reason, in so much that other objects shouldn’t be pulling data out, but asking it to do things. Rather than starting from a view point of what data does this class provide, you should think of what are its responsibilities.

But that is tangential to what I want to talk about, why are getters and setters so prevalent in Java? I think the first reason is the early OR mapping frameworks. They typically required you to inherit from a class, or broke OO (no inheritance in EJBs?!?), so you treated the domain object as struct, just to ferry data from Java to the database. Then you’d put logic in other objects and you’re just doing procedural programming. I think the situation is better now that you can work with POJOs (e.g. Hibernate) but you still see tutorials following the old pattern.

The second reason is the madness that is field access in Java. Getters and setters can protect you from this. Java binds field access at compile time, i.e. to a variable’s static type, e.g.:

public class A {
    int num = 0;
}

public class B extends A {
    int num = 2;
}

public class Test {
    public static void main(String[] args) throws Exception {
        A a = new B();
        System.out.println(a.num);

        B b = new B();
        System.out.println(b.num);
    }
}

Would output:

0
2

when you’d hope it would do something sensible like:

2
2

i.e. you shadow fields rather than override them, so you can get weird bugs if the static type is different from the runtime type. The variables can even be different types! Methods are determined by your runtime type so we can make sure we’re always accessing the right variable, e.g.:

public class A {
    int num = 0;

    public int getNum() { return this.num; }
}

public class B extends A {
    int num = 2;

    public int getNum() { return this.num; }
}

public class Test {
    public static void main(String[] args) throws Exception {
        A a = new B();
        System.out.println(a.getNum());

        B b = new B();
        System.out.println(b.getNum());
    }
}

Does output:

2
2

so unless the field is defined in your class, you really shouldn’t access it directly. This means to be safe, all fields should be private and we need protected scope getters and setters if we want that field available for subclasses, what a pain, but helps explain why they are so prevalent.

Back to Ruby, how does it deal with this? If you look back at the top I said if you want to access the data you need getters and setters. This is because attributes (Ruby’s name for fields) are private to an object, and everything you ask from an object has to be a method, basically you couldn’t get to that attribute directly if you wanted to! Ruby also doesn’t have the problem of field shadowing because you don’t declare variables, so when you reference it, you’re referencing the only variable with that name.

So what do the getters and setters look like?

class Test 
    def someField
        @someField
    end

    def someField=(newValue)
        @someField = newValue
    end
end

aObject  = Test.new
test.someField = "blah"
test.someField >> "blah"

i.e. our getters and setters look like we’re accessing a field directly but they are actually method calls. Without these, if we tried to access a field, Ruby would complain that no such method exists.

Since this is such a common pattern Ruby has some shortcuts:

read-only:

class Test
    attr_reader :someField
end

write only:

class Test
    attr_writer :someField
end

read/write:

class Test
    attr_accessor :someField
end

All these methods can take multiple arguments if you’re defining multiple fields.

A good summary of all this can be found here:

http://www.rubycentral.com/book/tut_classes.html#S2

But Ruby’s not perfect. A subclass can access attributes from its parent. which means you’re dependant on its implementation, but a code review can stop that.

The bigger problem is clashes with mixins. If a mixin uses an instance variable you can get collisions. A mixin has no state, that instance variable it refers to belongs to the object that included the mixin, so if it uses a variable with the same name you can get some weird behaviour. Because there is no static typing, the object’s methods and the mixin’s method can change what is held in that attribute and you won’t see that error until runtime where you’ll probably see a missing method error. Typical workarounds are prefixing variables with some sort of namespace to avoid collisions, or using a module level hash to store the mixin’s state outside of the object.

All in all I prefer the Ruby way of getters and setters. On the surface it looks the same but by preventing direct access to attributes and using virtual attributes (not covered here), you classes are less likely to become structs and more like genuine objects.

Now that I have some free time I can work on my golf league Rails app. There’s a bunch of stuff I want to do:

• Upgrade to Rails 1.1
• Upgrade to the stable release of Typo (4.0.x)
• Start using Capistrano for deployment
• Add in some tests

Typo

Last time round I started using Typo to manage news and photos (via Flickr). The problem was that I was using a trunk version (r933), which had some stability issues to say the least, but did the job. The biggest problem was a memory leak that caused DreamHost to kill it off whenever it got some significant load. A lot of these issues have been fixed in the current stable release (4.0.x), and it also uses Rails 1.1, so that’s a good excuse to upgrade (although unnessary for the other bit because it’s a separate app).

One thing I always wanted to do was integrate the admin screens of the league manager as tabs in Typo’s admin pages. I think this is being talked about for 4.1 but isn’t available now. So that doesn’t leave much space for tighter integration, and I don’t like having to maintain two code trees. Typo is also overkill for the odd monthly announcement.

Another thing I’ve considered is using a simpler CMS, e.g. Radiant. I haven’t looked at it much, but it supports something called behaviours, which allows you to do something different on a particular page. That could replace the standalone app that handles leaderboards, forms, etc. Another alternative is to just write a simple news posting system, then I wouldn’t have to worry about merging code bases, user models and all the authentication headaches.

If anyone else has experience in running two Rails apps as part of one web app, I’d love to hear about it.

Rails 1.1

I only just upgraded to 1.0 the last time round. It would be nice to see what the current state of the art is. The main problem here is that my copy of Agile Web Development with Rails only covers Rails 1.0, all my info on Rails 1.1 is a bunch of blog clippings.

What I’d prefer to focus on is the performance and memory enhancements I’ve been reading about on RailsExpress.blog. Rails on DreamHost is slow, and if you consume too much memory, your app gets killed. It’d be nice to sort this stuff out, especially since my users aren’t all technical.

Capistrano

Another pain with Rails is that almost certainly, deploying the thing that works on my laptop onto DreamHost won’t work. I don’t know much about Capistrano, but I’ve heard it takes away deployment pain, so I want to give it a go.

Testing

Being a hobby app there are no tests. Most of the logic is just editing records so I don’t need tests, but there are some tricky scoring and ranking things that should be verified with test cases. After that there’s ZenTest. It’s an automated tester that makes sure everything is still working with each change. It’s a different style of development that I’d like to try, it sounds a lot more helpful than occassionaly doing an ‘ant test’ that takes several minutes to run.

This is something that always frustrates me with Eclipse, unless you create a project as a Java project there appears to be no way to make it one through the interface. The most common case I have is I check something out of Subversion but can’t compile it because it’s just a regular project.

I should be able to go to Project Properties > Builders and add a Java builder. But it’s not possible. If I choose ‘New’ I can add an Ant Builder or a Program. If I choose ‘Import’ I have to find some configuration file. Why isn’t ‘Java’ in the new list?

The only way I’ve found is to add the following to your .project file then restart Eclipse:

<buildSpec>
    <buildCommand>
        <name>org.eclipse.jdt.core.javabuilder</name>
        <arguments></arguments>
    </buildCommand>
</buildSpec>
<natures>
    <nature>org.eclipse.jdt.core.javanature</nature>
</natures>

Then you can configure the project as a Java one and setup the build path, library dependencies, etc.

Does any one know of an easier way?

Can anyone recommend a SDK for J2ME on Linux? I want to try out a few things but getting started doesn’t appear to be as easy as it does with J2SE. I need the standard Java stuff as well as some sort of phone emulator.

Sun’s Toolkit needs Windows XP, as does Sony Ericsson’s. I’ve tried IBM’s WebSphere Everyplace Micro Environment, but when I start the emulator it keeps complaining about font paths. Even when I do fix the font paths it just displays the error message in a different font!

Is there a simple SDK out there?

Continuing my look into language features, today I’m asking why are we still using arrays? Or more specifically why does Java have C-style arrays? An array is essentially a list, an ordered collection of things. Lists are a vital data structure in programming but why is there this first-class array primitive in Java?

Let’s first look at C. Arrays in C are nothing more than syntactical sugar for pointer arithmetic. Consider the following example.

int[] a = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
a[1]; /* equals 2 */

int *a = malloc(10 * sizeof(int));
for (int i = 0; i < 10; i++) {
    *(a + i) = i;
}
*(a + 1); /* equals 2 */

These two bits of code are, for all intends and purposes, the same. Since they are the same there are some limitations placed on arrays in C, i.e. they are fixed length, and things need to be next to each other in memory because of the way pointer arithmetic works.

We don’t really want these restrictions on lists, I may want to change the number of elements, and where they’re located in memory should be an implementation detail. For the second point in particular, Java does make it an implementation detail when you decide to use ArrayList or LinkedList.

So what is an array in Java? It’s not an instance of the Array class, but it is an object. It has a field named ‘length’ (public final), and it implements the Cloneable interface. int[].class.getName() is [I. That doesn’t tell us much, but IMHO it’s a hack in the language to implement C-style arrays. It is fast, according to Peter Norvig’s IAQ on Java, accessing an array is 15-30 times faster than accessing an element of a Vector. But that could just be synchronization overhead, and Vector is probably implemented with arrays anyway. There should be some low level language feature that allows us to access that speed.

So what’s my gripe? Arrays in Java should be so much more than copies of the things in C. The Java Collections API which is one of the best Java APIs, and the List type should have the array syntax. Take a look at Arrays in Ruby, which are essentially a good list implementation with array syntax.

a = [1 ,2, 3, 4, 5]
a[1] » 2

b = [6, 7, 8, 9, 10]
a + b » [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

N.B. this produces a new array, but you can use the ‘concat’ method to append them to the same array

c = [2, 4, 6, 8, 10]
(a + b) - c » [1, 3, 5, 7, 9]

Ruby’s Array class also does a lot more.

The concept of C-style arrays need to be dropped. We don’t handle pointers any more, we shouldn’t be bound by the limitations. The concept we’re using is the list data structure, we should make that, along with all of its potential features, our first class type.

Update: I simplified the way to get the int[] class name (Thanks Shai).

Update 2: Corrected a typo in the C example (Thanks JDB).

Disclaimer: In the C example the first declaration will assign memory from the stack and the latter from the heap, so they’re not the same, but I just want to demonstrate elements in the array are next to each other in memory and hence [] notation can be changed to pointers.

Disclaimer 2: I know Vector’s methods are synchronized, and ArrayList is essentially the same thing without the synchronization overhead, hence faster. The performance numbers I pulled up are old and it used Vectors, thanks Shai for providing up to date numbers.

One nice feature of Ruby that I wish I had with Java is the able to change the standard classes. For example, Ruby’s Array class has a map function, but no reduce function. So we simply add methods to the class:

class Array
  def reduce(n)
    each do |value|
      n = yield(n, value)
    end

    n
  end

  def sum(initial = 0)
    reduce(initial) { |n, value| n + value }
  end

  def product(initial = 1)
    reduce(initial) { |n, value| n * value }
  end
end

[ 1, 2, 3, 4, 5 ].sum   »  15 
[ 1, 2, 3, 4, 5 ].product   »  120

(Example from Programming Ruby, where the method is called ‘inject’ and is defined in a separate Mixin so it can be included in other classes, e.g. Range)

In the above example we add the reduce method to the Array class and two additional methods, sum and product, which make use of reduce. The reduce method takes an initial value for the reduction and a code block to act on each element of the array.

We can’t replicate this elegance in Java because the classes are closed. Extending the class only gets us halfway there because only instances of the sub class have the method, i.e. others methods that return the original class won’t have it. Therefore we tend to end up abandoning OO and sticking the function somewhere else, e.g.:

public interface Functor {
  Object function(Object acc, Object value);
}

public class ArrayUtils {
  public static Object reduce(Object[] array, Object initial, Functor f) {
    Object result = initial;
    for (Object o : array) {
      result = f.function(result, o);
    }

    return result;
  }

  public static Integer sum(Integer[] integers) {
    return reduce(integers, 0, new Functor() { 
      public Object function(Object acc, Object value) { return ((Integer) acc) + ((Integer) value); }
    });
  }

  public static Integer product(Integer[] integers) {
    return reduce(integers, 1, new Functor() { 
      public Object function(Object acc, Object value) { return ((Integer) acc) * ((Integer) value) }
    });
  }
}

ArrayUtils.sum(new Integer[] {1, 2, 3, 4, 5});   »  15 
ArrayUtils.product(new Integer[]{1, 2, 3, 4, 5});   »  120

The Java version does the same thing, but just looks wrong to me. Sure autoboxing cleans it up a bit and generics would do more (at the expensive of having to instantiate ArrayUtils), but you can’t get around defining the methods outside of the class, and having code blocks passed around as anonymous classes.