dasman’s World

After playing around with writing Sudoku Solvers in the past, I was interested to see this page which details a number of tiny sudoku solvers in a variety of languages such as Perl, Ruby, etc.

They have a few basic rules – no line over 80 bytes, etc, etc. And the examples take their input as a string of 81 digits, which represents the 9 rows of 9 digits, with “0″ being a blank square.

As I apparently have way too much time on my hands , I got up the motivation to convert one of these examples into Java. The results?

• The end program is around twice as many lines as the Perl original, and
• Yup – you can make Java programs as unreadable as anything else out there!

There may well be shorter possibilities out there – I didn’t put in a great deal of effort past converting the Perl original. But, for the record:

import java.util.*;public class S{static char[] A;static void R(){int i,j;for(i=
0;i<81;i++){if(A[i]!='0')continue;HashMap h=new HashMap();for(j=0;j<81;j++){h.
put(j/9==i/9||j%9==i%9||(j/27==i/27)&&((j%9/3)==(i%9/3))?""+A[j]:"0","1");}for(j
=1;j<=9;j++){if(h.get(""+j)==null){A[i]=(char)('0'+j);R();}}A[i]='0';return;}for
(i=0;i<81;i++){System.out.print(A[i]);}System.out.println();System.exit(0);}
public static void main(String[] a){A=a[0].toCharArray();R();}}

Assuming you have an appropriate classpath, you can run it with a line like:

java S 006070800000000000078601520030405010400000002090302060052103690000000000003020100

This code was converted from the excellent Perl example at:

http://www.ecclestoad.co.uk/blog/2005/06/02/sudoku_solver_in_three_lines_explained.html

Its the new development methodology thats taking the developer-world by storm….

Well, not really.

Just a cute phrase that occurred to me today when chatting to a colleague. We’d just spent 15 minutes discussing the desired behaviour of a system I was working on. Usual stuff – at first blush it seems straightforward, but plenty of edge cases, historical behaviour requirements, and other nastiness.

So we got it figured out, and its 11:45. Lunch booked at 12:00. No way am I even getting 10% of the code done in that time. But its just enough time to do the Javadoc.

So, 15 minutes later, my code has the 2 method signatures I need and around 40 lines of Javadoc describing the code’s behaviour, exceptions, and assertions. And after lunch, I was able to get straight into coding, all details of my discussion safely preserved.

And as an added bonus, when it comes time to rework it, I (or the next guy) will have some great doco to get started.

Not rocket science. Certainly not worthy of its own buzzword-esque title (although it does roll off the tongue ). And probably something everybody should be doing anyway as part of their actual methodology. But its a neat little anecdote worth telling!

Well, they say you learn something new everyday. And given the size of the Java API, thats not too hard to believe

After doing serious Java programming for at a least a few years, and having dabbled for a few years more (all the way back to the 1.0 days!), I’m pretty happy with my breadth of Java knowledge. Until a co-worker today mentioned using Collections.shuffle() to randomize a list.

“Pffffft”, says I, “Surely you jest”, says I. “No such thing.”

Well, there is. java.util.Collections (not Collection, note – theres an “s” on the end!). A nice, chunky class, full of juicy, static methods just waiting to save you from having to re-invent the wheel when it comes to operating on Collections. There’s the obvious stuff – shuffle() and sort() to randomize and sort, for instance. And small, but useful stuff – min() and max(), swap(). And some real useful stuff, like synchronizedList() (which returns a thread safe version of your list).

Many’s the time I’ve done my own “max()” routine. Each time, I trawled through the Collection interface looking for one and was mildly surprised it didn’t exist. And I never thought to look any further afield. I’m guessing that there may be one or two Java guys out there who are in the same boat (How many library classes are there now in Java?). Seeing as my co-worker doesn’t have his own blog…yet (come on H! Get your act together! ), I’m doing this posting for the other people like me!

Of course, I’ve always got the excuse for my ignorance that its a relatively recent addition. I mean, its only been around since Java 1.2….. *grin*

I came across this entry while scanning Java Blogs yesterday about how to handle exceptions within a constructor. The essence of the article is how do you handle the situation where you couldn’t instantiate your object?

So, if the user passes invalid parameters, do you throw an exception? And, slightly more subtly, if your constructor encounters an exception during object setup, how does it handle this?

Interesting article and well worth the read.

But it struck a bit of a chord with me – I recently bought a Nokia N70 phone, and have been cruising the net looking at how you can code for these things. The N70 is a Symbian phone, and while it has J2ME support, the hardcore stuff seems to be done in C++. Now, C++ is an … interesting language, but is not really known for its in-built protection against memory leaks, and when you’re running a program on a device with limited memory, where your app may well run for the order of days or months this suddenly becomes a big deal.

OK, so you just code, really, really carefully.

Well, turns out that constructors are a special case in terms of memory leaks. Symbian doesn’t use standard C++ exceptions, but it does have an analagous concept called “leaving” grafted on. And not being a C++ guru, I couldn’t tell you what difference there is between normal C++ exceptions and the Symbian variety. In any case, the issue when writing Symbian programs appears to be this:

1. Constructor called
2. Constructor initialises an instance variable that points to some new object
3. On the next line, the constructor encounters an error and leaves

So, we now have allocated memory for some new object (step 2 above), but the object that owns it no longer exists – it crashed during construction. And because the object never fully formed, the destructor wasn’t run on it and so couldn’t free up the memory. Ladies and gentlemen, we have memory leak….

Turns out that Symbian programs have an accepted idiom on how to handle this stuff. Objects that can suffer this way have a static construction method (like the whole getInstance() idiom you see in Java). This static constructor creates the object using a constructor that only performs trivial operations that won’t crash, then once the object exists, calls an instance method on the new object that performs 2nd-phase construction. If things turn to jelly, there is at least a concrete object in existence, so the destructor will be called as normal.

Pretty neat. And pretty eye-opening as to the kind of issues you can be exposed to without garbage collection.

(Which is not to say that Java doesn’t have its own issues with memory leaks, but thats a whole other blog post… )