Morse Decoder’s Lean And Sexy Search Algorithm

November 15, 2014 by Mike Szczys 27 Comments

Often the Morse Code centered projects that we feature are to help you practice transmitting messages. This one takes a tack and builds an automatic decoder. We think [Nicola Cimmino’s] project is well worth featuring simply based on his explanation of the Digital Signal Processing used on the signal coming in from the microphone. Well done. But he’s really just getting warmed up.

What makes this really stand out is a brilliant algorithm that allows conversion from Morse to ASCII using a lookup table of only 64 bytes. This provides enough room for A-Z and 0-9 without chance of collision but could be expanded to allow for more characters. Below is a concise description of how the algorithm works but make sure you take the time to read [Nicola’s] project description in its entirety.

The algorithm can be decribed as follows. Have an index inside the lookup string inizialied to zero. Have an initial dash jump size of 64. At every received element (dot or dash) halve the initial dash jump and then increase by 1 the index inside the lookup string if a dot was received and by dash jump size if a dash was received. Repeat until a letter separator is reached, at that point the index inside the lookup string will point to the ASCII corresponding to the decoded morse.

Have you heard of this technique before? If so, tell us about it in the comments below. Before you jump all over this one, realize that Magic Morse uses a different technique.

Using Tetris Like MS Paint

November 8, 2014 by Mike Szczys 11 Comments

Check out Samus looking boss in this pixelated image. Who would have thought of using Tetris as a canvas for these types of graphics? Coming up with the original idea of strategically clearing and leaving Tetris pieces to end up with what is shown above is hard enough. But how in the heck do you implement the algorithm that generated this programmatically?

First off, two thing should not be surprising about this. It wasn’t manually generated during normal gameplay. That would be beyond savant level. The other thing to note is that the order in which pieces occurred was not random, but strategically calculated by the algorithm. The challenge is not only to occupy and clear the correct pixels, but to make sure the correctly colored pieces remain.

You need to see the fast-motion video embedded after the break to fully appreciate the coding masterpiece at work. We’re not going to try to paraphrase how the algorithms functions, but get comfy with the link above which walks through all of the theory (in addition to supplying the code so you can try it yourself).

Continue reading “Using Tetris Like MS Paint” →

Dithering In Processing

December 6, 2012 by Mike Szczys 20 Comments

dithering-experiments

To be honest, we’ve heard of dithering but that’s the extent of our knowledge on the topic. After looking through [Windell’s] post about using Dithering in Processing we can now say we’ve got a base of knowledge on the topic.

Dithering is used to produce an image out of two colors that our eyes can put together into something meaningful. The history of the algorithms goes back to monochrome displays. But now the hobby electronics we work with for fun have comparable computing power and perhaps it’s time to rediscover these techniques. [Windell’s] project implements the Atkinson dithering algorithm in real-time on your webcam. He’s doing this in Processing, which should make it pretty easy to port for your own purposes.

So why might you want to use dithering in your own projects? Because if it can be used to make very cool milled artwork there must be other undiscovered uses lurking around your workshop.

Calculating Pi To 10 Trillion Digits; The Last Number Is 5

November 28, 2011 by Brian Benchoff 44 Comments

In August, 2010, [Alexander Yee] and [Shigeru Kondo] won a respectable amount of praise for calculating pi to more digits than anyone else. They’re back again, this time doubling the number of digits to 10 Trillion.

The previous calculation of 5 Trillion digits of Pi took 90 days to calculate on a beast of a workstation. The calculations were performed on 2x Xeon processors running at 3.33 GHz, 96 Gigabytes of RAM, and 32 Terabytes worth of hard drives. The 10 Trillion digit attempt used the same hardware, but needed 48 Terabytes of disk to store everything.

Unfortunately, the time needed to calculate 10 Trillion digits didn’t scale linearly. [Alex] and [Shigeru] waited three hundred and seventy-one days for the computer to finish the calculations. The guys used y-cruncher, a multithreaded pi benchmarking tool written by [Alex]. y-cruncher calculates hexadecimal digits of pi; conveniently, it’s fairly easy to find the nth hex digit of pi for verification.

If you’re wondering if it would be faster to calculate pi on a top 500 supercomputer, you’d be right. Those boxes are a little busy predicting climate change, nuclear weapons yields, and curing cancer, though. Doing something nobody else has ever done is still an admirable goal, especially if it means building an awesome computer.

Microsoft Points Algorithm Cracked… They’re Out $1M

March 11, 2011 by Mike Szczys 44 Comments

Looks like someone figured out the algorithm that Microsoft uses to generate unique codes for their alternative currency: Microsoft Points. We were always a bit baffled by the need to do this sort of thing (Disney dollars, tokens at arcades, etc.) but figured it’s just a grift to get you to spend more dough. Looks like this time it may have come back to bite them in the ass with early loss projections somewhere in the $1-$1.2 million range.

But as most of you know, it’s not just an algorithm that can cause this kind of havoc. Whomever figured out how to crunch the numbers apparently packaged the method into a nice GUI and distributed it over the Internet. Check out the video after the break to see that not only will it give you a code, but you can verify that it works at the click of a button. Microsoft is taking steps to invalidate all of the ill-gotten redemption codes, but we wonder how effective they can be at it. Surely they already had contingency plans for this and we wonder if the company didn’t also carry insurance against this kind of loss.

Try as we might, we couldn’t turn up a press release on the subject. If you know of any, please be kind and leave a link in the comments.

Continue reading “Microsoft Points Algorithm Cracked… They’re Out $1M” →

The Chief Cook Robot

May 24, 2008 by Eliot 8 Comments

We feel the need to apologize immediately for the use of Yakkity Sax in the preceding video and recommend you watch the longer, yak free, video below. It shows researchers at the Learning Algorithms and Systems Laboratory teaching a robot how to make a ham and cheese omelet. Each working area and food item is labeled with a machine recognizable tag. The researcher demonstrates the task by guiding the robot’s hand. The robot combines multiple demonstrations to generalize the skill. It can then adapt the learned skill to the specific task. You can see this in the video when the robot adjusts to the location of the bowl and cutting board when they’re moved around. Teaching through demonstration would make the use of robotics much easier for the general population.

Continue reading “The Chief Cook Robot” →