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:
- personHasInsurence (A)
- personNeedsInsurence (B)
- 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.
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:
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:
Corewars – An Introduction to Hostile Programming
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:
org wipe
step equ 5
first equ bomb-10
bomb:mov.i #1, -1
ptr: sub #step, #first
wipe:jmz.f ptr, @ptr
mov bomb, >ptr
djn.f wipe, {ptr-5
end
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?