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?
Category: Algorithms, Java Programming | Tags: algorithm, music matching, shazam | Comments (38)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!
Category: Algorithms | Tags: arithmetic coding, compression, ppm | Comment (0)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:
- I have a field with 122 points
- 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..!
Category: Algorithms, Java Programming | Tags: algorithm, guess | Comments (3)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.
Category: Algorithms, Math | Comments (3)