I only came across H.264 recently, up to that point I thought DivX was supposed to be the be all and end all of video encoding. Two things brought it to my attention, first the promise of much smaller video sizes, and secondly, the new AppleTV doesn’t support DivX, but does support H.264.

So I installed thin liquid film, which is a Python QT frontend for ffmpeg. Once installed the program is very straightforward:

1. Select the file
2. Select the encoding (H.264)
3. Select the audio quality (I went for 128kbps)
4. Select the output directory
5. Click ‘Encode’

My test program was an old episode of Stargate SG-1 that had been recorded via a TV card, then encoded with DivX. The quality is pretty good, and the 45 minute show took 347M. The re-encoding took just under an hour (P4 - 2Ghz laptop, with stuff running in the background), pretty long if I’m going to re-encode every video I have. First impression, great, the file size dropped to 98M! More than a threefold saving, that would put off the construction of that 1TB NAS device I keep thinking about. Sadly it was not to last. The quality suffered a lot, even on my 14″ laptop screen the image was blurry. I guess two lossy encodings is too much, no matter how fancy they are.

But all might not be lost, I also have several DVD boxsets that I’d like available on my PC. With a DVD as a source it should produce a good quality video.

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.

At the moment both my desktop and laptop run Gentoo Linux. It’s a fine OS and it’s been the longest running Linux distro I’ve had, but it takes a lot of effort to keep it up to date. Over time I’ve used my desktop less and less for work, to the point it’s really just a media server. Since it hasn’t been used for much, I haven’t kept it up to date, and it’s still awaiting the split-X upgrade, and now the gcc 4.11 upgrade. I don’t want to do them again, I’ve done them on my laptop and they take a long time, and there’s always something that needs fixing at the end. So I figure it’s time to try out something a little more low maintenance, enter Kubuntu.

I’ve had some experience with Ubuntu before, and it’s pretty pain-free, providing you don’t mix and match your source lists too much, all too common when you want to try some new version of a package. I downloaded a copy of Kubuntu Feisty Fawn, which is the latest development version, so strictly speaking you shouldn’t use it as your current desktop OS, but I don’t plan to upgrade for a short while so I just wanted to give it a test run.

N.B. This was done with the live CD rather than doing an install.

Startup

Overall pretty good, it did try to use an unsupported video mode between the original boot menu and X, but I just sat it out and it was fine. It brought up X and found the network.

X

X did start up and was working but still needed some configuration to get to a decent state. It had chosen the highest resolution possible, which meant a low refresh rate, I had to copy over my old settings to get it the way I liked it. I was surprised to see an option to change the resolution and refresh rate in KDE control center, but these had no effect besides restarting X. It also setup a US keyboard, so that needed changing.

Other Hardware

It didn’t detect my printer, but I’m still using the parallel port, so fair enough. More annoyingly it didn’t create any mount points for my hard drives and DVD drive, so I had to do this for myself.

Multimedia

Since the main purpose of the box will be to serve media files, this is an important area. Sounds works fine, so we were off to a good start, but that’s where it ended. There’s a definite lack of multimedia software with Kubuntu, namely:

• mplayer
• freevo
• mythtv
• Any UPnP AV servers (mediatomb, ushare, etc.)

The only media player was Kaffeine and when it started, it complained about various things, e.g. missing Win32 codecs, insufficient permissions to read /dev/dvd, not great. The lack of codecs was a real problem. Most files couldn’t play (duh, they’re avi files!), but also some mpegs lacked sound.

That’s where my first adventure into Kunbuntu ended. The appeal of apt-get is a strong one, so I think it’ll continue, I just need to find a source list that will give me multimedia love I crave. If I can get that sorted and setup a CUPS and Samba server, it might be time to retire one of the older Gentoo installations out there.

I just came across a free fax by email service from TPC. It looks like it’s been going for a long time. Very handy when you come across a company who doesn’t have an email address or phone number!

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!

I’ve started using Gmail at work and I like it. The conversation view really grows on you, and little things like filtering out duplicate mails (think replies to a mailing list) are really handy. After using it for a few weeks it made Squirrel Mail, which I was using for my personal mail, feel really basic. So I decided to setup Gmail to be my main mail client, but with my regular email address. Here’s what I did:

1. Register your personal email address with Gmail. This allows you to send mail from your regular address instead of your Gmail address. You might also want to set that address to be the default one messages are sent from.
2. Start forwarding your other mail to Gmail. This step really depends on your ISP, I have shell access so I use procmail:

   PATH=$HOME/usr/bin:$HOME/usr/local/bin:/usr/local/bin:/usr/bin:/bin:/usr/bin/X11:/usr/games
   MAILDIR=$HOME/Maildir
   PMDIR=$HOME/.procmail
   LOGFILE=$HOME/procmail.log
   SHELL=/bin/sh
   
   # ... SpamAssassin stuff omitted ...
   
   
   # Forward to Gmail (if not from Gmail, e.g. bcc’s)
   :0c
   * ! ^Sender: user@gmail.com
   ! user@gmail.com
   
   
   # Default entry to make sure mail is delivered
   :0
   $HOME/Maildir/
   

   N.B. replace user@gmail.com with your email address.

   The bold bit forwards all mails to Gmail unless it’s sent by your Gmail user, e.g. if you’re bcc’ing each mail to yourself (useful for normal mail clients to maintain a conversation view but unnecessary for Gmail), but the main idea is to stop loops.
Optional step
3. I like to send a copy of each mail to myself using BCC. This means I can backup sent mail, and still see the whole thread if I’m using another client. This can’t be done automatically with Gmail, but can be done with a greasemonkey script, I’m using Gmail Auto BCC. The procmail rule above allows you to BCC your main email address without sending a copy back to Gmail, but it’s not perfect. When you bcc yourself Gmail spots this and marks it as a new message in your inbox, I haven’t found a way around this yet with only one address. But I have my own domain so I can have as many addresses as I like, so I setup a bcc@ address for my auto forwarding.

With this setup a copy of all my email is forwarded to Gmail, I can send mail from my regular address, and a copy of each message I send is backed up to my ISP. It’s working well at the moment, the only downside being I have to sort through mail twice, first in Gmail, and secondly went downloading the backup from my ISP, I’ll have to see how that works out in the long run. My next tasks will be to see if I can upload my old mail, and to try out the new mobile Gmail app.

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.

The Register reports that from next month, T-Mobile will introduce a new tariff that allows people to use VOIP on their phones.

Ahead of next week’s announcements, The Register has learned Web ‘n’ Walk Max will have a 10GB data limit and no restrictions on VoIP or instant messaging use. It’ll cost consumer punters £22.50 as a standalone product and £44 for suits, who get voice bundled in.

Also new will be Web ‘n’ Walk plus, which provides 3GB without VoIP, but with instant messaging allowed.

Standard Web ‘n’ Walk, as available now, will remain unchanged at £7.50 for 1GB. Instant messaging will be allowed for light users too.

I was already planning to switch when my Vodafone contract runs out at the end of this year so I could surf on my phone. This news provides an interesting new option. I’ve been mucking around with WengoPhone, which is like Skype but uses the open SIP standard. They already have a mobile client, but it’s for Windows smart phones, which I definitely won’t get. Hopefully they’ll put together a J2ME version soon.

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.