I’ve just stumbled across a new program: Eureqa
Its a program, developed by the Cornell Computational Synthesis Laboratory, that can detect equations in sets of data. Its primary goal is to identify the simplest mathematical formulas which could describe the underlying mechanisms that produced the data.
Its best described using their instructional video:
I’ve been playing around with it, for example trying to find a good prediction equation for the Son of Darts competition I blogged about earlier.
The algorithm(s) used in this program are based around “symbolic regression”. It is a form of Genetic Programming (GA) where the computer processes a tree of possibilities recursively searching for the best suited building-blocks.
What is #songsincode ?
Last week I discovered a new hype on Twitter. The so-called “#songsincode”. It’s a huge hype under programmers and technical users. The best way to explain is probably by showing an example:
This obviously is Paint It Black by the Rolling Stones (if the door is red, paint it black)
My own #songsincode:
Here is a collection of the #songsincode I created and tweeted:
And here is my all-time favourite (in CSS!!) created by @codepo8:
I hope you liked them!
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
For example the piece of code below:
Of course, there seems to be not much wrong with the code, I see it all the time. Yes, the code breaks if you put something else in the comparator, but hey… the Javadoc says it only accepts LabelPlaceholders! So lets use this code:
Done! Its working and no problems right? Not quite, your IDE (Eclipse in my case) complains about this code.
For example Eclipse says:
Type safety: The expression of type LabelPlaceholderComparator needs unchecked conversion to conform to Comparator<? super T>
At this point, most programmers at the company I work for now will just ignore this warning. They might even add:
What a shame… Lets just examine this warning, what is Eclipse trying to tell us here? The compiler doesn’t know we created the Comparator with only LabelPlaceholders in mind. But the compiler does know (with generics) that the List only contains LabelPlaceholders. So the warning is (in understandable English):
I’ve got a list here of T (LabelPlaceholders) and a Comparator for Objects, this can go wrong! I’d rather have a specific Comparator for this job. Do you have one for me?
The solution to this problem is very simple, but most neglect to use it:
As you can see, the code is much smaller. The interface is now generified, it knows we are going to compare LabelPlaceholders now, nothing more, nothing less. Also, we don’t have to cast anymore, because of the generics you can’t put anything else in there.
So, lets go to the conclusion: Why is the latter code better code?
- As you can see, the code is smaller!
- There are no casts, the code is safer (no ClassCastException or eleborate class checks)
- If somebody uses your code, he/she knows what kind of objects the Comparator can handle. You don’t have to read the Javadoc or the code to see what it does.
Throughout the projects I encounter I keep finding examples of places where generics would have made the code smaller/safer/more understandable. For some reason the programmers still only use generics on collections. So, even though generics aren’t perfect, please use them where/when you can, it’ll always add clarity to the code, and most of the time it’ll also make your code safer, and in some cases the code gets smaller because you can leave away casts and class-checks.
Don’t ever let me see public int compare(Object o1, Object o2); again!
(You see, it is possible for me to have a discussion about Java generics without mentioning reified generics!)
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
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.
About a week ago I had a discussion with a fellow programmer about some boolean logic. We had three parameters, something like:
- personHasInsurence (A)
- personNeedsInsurence (B)
- personIsKnownAtThisAgency (C)
We also had two particulair cases for an insurance page:
Person has insurence and isn’t yet known at this agency
Person doesn’t have insurence, needs insurence and is known at this agency
Person doesn’t have insurence, doesn’t need insurence and is known at this agency
So the view-logic was a bit complex:
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.
Minterm: A small boolean function which has all the different input variables, once. So for example, a minterm using the above variables would be: ABC (A and B and C), or A’BC (not A and B and C).
The first thing you do using this algorithm is that you find so called “prime implicants”. An implicant is a combination of one (or more) minterms, and a prime implicant is a implicant which can’t be combined with other implicants (for more details, read the wikipage with examples)!
After combining all the minterm of your case(s), you’ll end up with a “prime implicant chart”. This is a chart with all the prime implicants and the fields they cover. Sometimes its easy to spot “essential prime implicants”. That is, implicants which are unique in covering a field. You have to use these implicants in the final logic.
When you have multiple options left to combine to cover all the fields, you can use Petrick’s Method to select the best/smallest option.
Using the above example, if you minimize, you’ll come down to:
The algorithm is pretty fun to program, and its a bit different from most algorithms I’ve seen lately!
And if you need something even faster, try out Espresso!
ps. I love browsing this page: List of algorithms
But OTOH, its kind of depressing I still have soo much to learn.
I’ve implemented a Brainfuck interpreter!
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:
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:
Corewar is a game from the 1980’s, played between computer programs written in Redcode, a language similar to assembly. The programmers design their battle programs to remove opponents from the memory of the MARS virtual computer by any means possible.
Some of the simpler techniques include blindly overwriting memory, searching for the opponent or spawning off new processes. These are commonly known as stone, scissors, paper after the popular playground game. Stone usually wins against scissors, scissors normally defeat paper, and paper mostly beats stone.
Here’s an example of a typical Corewar program:
This simple example of scissors once held a 20 point lead over it’s rivals. The first instruction is never executed, it’s the bomb used to overwrite opponents. The next two instructions form a loop which looks through memory for an opponent, and the final two instructions actually overwrite it.
Corewar is still going strong, and celebrates it’s 25th anniversary in 2009. If you’d like to discover more about Corewar, here are the top resources:
- The Beginner’s Guide to Redcode will teach you the language of Corewar
- pMARS is a portable implementation of the Corewar virtual machine
- Corewar Tutorials exist on virtually every aspect of the game
- Koenigstuhl is an archive of thousands of published Corewar programs
- SAL organises a number of on-going king of the hill tournaments
- sfghoul and impomatic report the latest Corewar news on their blogs
- #corewars is the official Corewar discussion channel, hosted by irc.freenode.net
What are your experiences with Corewar, have you ever had any success?