Compression by prediction

The last couple of weeks I have been playing around with compression/decompression algorithms. This is a field that has always intrigued me. It gives me a magical feeling, like a magician you wave some algorithm around and suddenly the files shrink and bytes dissapear. With the same motion you can undo all your actions and re-generate the original files from thin air!

Continue reading »

Placement of circle over points

For the Queue ICPC programming game Capture I ran into a geometrical problem.
While programming my little robot I wanted to have an algorithm calculate this for me:

1. I have a field with 122 points
2. I have a circle of fixed size

How do I calculate where to put the circle so it encapsulates the most points?

This is what I came up with, three algorithms:
Continue reading »

Guess the algorithm

Yesterday I found and programmed a nice little algorithm. I’m not going to tell you (yet) what it does and how its called, but I’ll just show the code:

	private int function(int x, int y) {
		int r = 0;
		while(x!=0) {
			if((x&1)==1) {
				r+=y;
			}
			x>>>=1;
			y<<=1;
		}
		return r;
	}

So tell me, what does this do, and what is the algorithm called?

Edit:

And indeed (it was a simple one) the correct solution is multiplication, and to be specific, Ethiopian or Russian Multiplication.

I’ll probably do more, harder ones, in the future..!

MD5 quine, fixed point

MD5 quines

Sometimes I let my mind wonder and I get crazy questions. Today was a good example, I encountered a MD5 hash and I started to wonder, would there be a hash which would (when hashed again) be the same?

Thus: MD5(x) = x

This would be a kind of MD5 quine, when fed into the algorithm you get the original value back. This is actually called an MD5 fixed point.

Continue reading »

Eureqa

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.