Creating Shazam in Java

A couple of days ago I encountered this article: How Shazam Works

This got me interested in how a program like Shazam works… And more importantly, how hard is it to program something similar in Java?

Continue reading »

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 »