Java Generics for Compare

I’ve been developing with Java 5+ for quite a while now. Not all developers are this lucky, some are still stuck with 1.4… some even with 1.3! But my clients all made the excellent step forward to Java 5 (some even to 6). The problem is, they moved the runtime/JDK but forget to move their developers!

In Java 5 the language brings some good improvements, the for-loop is easy to understand, and almost all the developers are using this by now. The problem starts with generics. There is a part most developers understand, the Collections API. Almost all programmers use lists now as: List<Integer> instead of a plain old List. This is a good start, but it must not end here! First, I must admit, generics in Java can sometimes be hard and confusing (when using <? extends X> and <? super X>). So I’m not going to talk about any of this ‘hard stuff’. Its the use of ‘easy’ generics that can our lifes so much easier.

For example the piece of code below:

Continue reading »

Son Of Darts

Another thing I’ve been very busy with lately is AZsPCs (Al Zimmermanns Programming Competition). The current contest is called Son of Darts.

The idea behind these contests are that they are easy to grasp, but very hard to master.

Lets take three darts. You have to throw them to a dartboard which is divided into 4 regions. For example, the values on these regions are: 1,2,4,6.
The first question is: What is the lowest value you can’t throw with these three darts?

This is easy to calculate:
Can we throw one? Yes: 1 dart in the 1
Can we throw two? Yes: 1 dart in the 2, or 2 darts in the 1
etc etc
Can we throw nine? Yes: 6,2,1
Can we throw ten? Yes: 6,4
Can we throw eleven? Yes: 6,4,1
Can we throw twelve? Yes: 6,6
Can we throw thirteen? Yes: 6,6,1
Can we throw fourteen? Yes: 6,6,2
Can we throw fifteen? Err… no, sorry…

So the score is: 15 points.

The main question: Can you think of better values for the regions of the dartboard to get a higher topscore??

This is what the competition is about. But not only for a dartboard consisting of 4 regions, but up to 40 regions. And not only for three darts, but also 4, 5 and even 6 darts.

If you can create a good solver its pretty easy to bruteforce up to a certain point, but the problem is, you quickly get more and more options for which you have to check the scores… It is an exponential function…!

Actually, this is not a new puzzle. Its been around of quite a long time. But its more commenly known as the local postage stamp problem (LPSP). Formulated just a little bit different, instead of a dartboard with regions you have a postcard with room for H stamps. What is the lowest value you can’t create with stamps Nh? Also check out Wolfram’s description of the problem.

This problem has been proven to be NP-hard, so bruteforcing won’t be an option, you’ll need to use something different. Put on your thinking-caps and create some good innovative heuristics.

Quine – McCluskey

About a week ago I had a discussion with a fellow programmer about some boolean logic. We had three parameters, something like:

1. personHasInsurence (A)
2. personNeedsInsurence (B)
3. personIsKnownAtThisAgency (C)

We also had two particulair cases for an insurance page:

Case 1:
Person has insurence and isn’t yet known at this agency

Case 2:
Person doesn’t have insurence, needs insurence and is known at this agency

Case 3:
Person doesn’t have insurence, doesn’t need insurence and is known at this agency

So the view-logic was a bit complex:

if( (A && !C) || (!A && B && C) || (!A && !B && C ) ) {
    showPage();
}

Then I remebered something I learned at school some time ago. So called karnaugh maps. I’ve completely forgotten how to use them, but I knew it was possible to calculate the shortest form to comply to the logic rules. When looking further I found the so called “Quine McCluskey“-algorithm, and I decided to implement it (just to learn how it works).

Quine – McCluskey algorithm

First of, lets go through a couple of terms.

Continue reading »

Corewars – Brainf*ck

I’ve implemented a Brainfuck interpreter!

Yes, you heard it right, Brainfuck (BF).
BF is an esoteric programming language. More information on BF can be found here.

The language itself is pretty simple, and most of it was implemented rather quickly in Redcode. The only big problem was navigating back to the correct closing brackets in a loop. This is now solved by counting the amount of open/close brackets in between.

So here is the code:

Continue reading »

Corewars – SUBLEQ interpreter

In my previous blogpost I talked about Corewars and the Redcode language. But instead of playing the game, you can do a lot more with the programming language. John Metcalf posted a blog about OISC (One Instruction Set Computers). He decided to implement the RSSB algorithm, so I took on the challenge of implementing SUBLEQ, another single instruction set computer.

And here is the result:

Continue reading »