Algorithm.co.il

Math

Fractals in 10 minutes No. 1 – LStrings

Posted on by 1 Comment

Lately it started to be quite fun to find some fun mathematical formula, and just code it in python, and plot the result. Fractals are such fun. LStrings is an example of that. For those who don’t know – lstrings are simple strings with three letters, ‘f’ for forward, ‘l’ for left, ‘r’ for right. An iteration of an lstring is replacing all occurrences of ‘f’ with the original string.

During high-school I recall long lessons when I would draw complicated iterations of some simple lstring just to see the result. Sometimes I still draw them. A few days ago I just wanted to see how long it would take me to program one. It actually was quite short. What really took me time is blogging about it ;)

The source and the results are available here.

This post is going to be the first in a series of posts about some fractals. I will continue to write other examples of simple code that (hopefully) generates beautiful results. Stay tuned for more.

Do you know any elegant\short\simple pieces of code that generate fractals?

"Where is Waldo?", or "Security by Origami"

Posted on by 6 Comments

The Problem

A friend of mine gave me a riddle this morning regarding “Where’s Waldo?”. The riddle is as follows:

You and a friend play “Where’s Waldo?”. You solve the puzzle before your friend, and you want to prove to your friend you solved the puzzle, without giving him any hints. How do you do this?

Obviously, this is of course very reminiscent of zero knowledge proofs. A good zero knowledge proof will allow your friend to be convinced before he found Waldo himself, and even if he never finds him at all. A somewhat less interesting solution is a solution that will allow your friend to be convinced if and when he finds Waldo himself and can then verify your proof.

There are obviously many “intuitive” solutions, and I will not write them here… I will write here the second solution I thought of, but I consider it to be the more interesting one. However, this solution doesn’t solve the original problem – it only allows your friend to verify your solution once he solved it himself.

The Solution

Take a sheet of paper of identical dimensions to the picture, and mark a spot on it in the position where Waldo would have been on that sheet of paper. Fold that sheet of paper to some kind of origami animal, and give it to your friend. Once he solves the puzzle, he can open the folding, and see for himself that the point was marked correctly.

This is obviously not a very good solution. It is just a glorified note – you write down your solution on a note, and ask your friend not to peek until he solves it himself. So I came up with an improvement:

Agree beforehand with your friend on some (large) origami folding (such as a beetle). He shouldn’t know the instructions to fold it. Take a sheet of paper, and mark Waldo’s position on it (with a dot). Hold the paper above the fold, and mark on the fold (with another dot) the projection of the original dot on the folding. Now unfold the origami – you have a crease pattern. Give the crease pattern to your friend. When he solves the puzzle, refold the origami, and prove to your friend that the projection of the dot on the fold coincides with the dot on the picture. As an added bonus – your friend just learned how to fold another origami beast!

Of course, this solution isn’t water-tight. It also relies on crease patterns being hard to solve. It is mostly security by obscurity – but this time, ‘security by obscurity’ becomes ‘security by origami’. I just found that fascinating – that origami may be considered a function that is ‘hard to reverse engineer’ (even if it is not so) – such as a hash function. Origami does behave a little bit like a hash…

Tell me your original solutions to the problem.

Reachability on arbitrary maps

Posted on by 2 Comments

The other day I had an idea. What if you took a map of some country, and from each coordinate computed the time it took to any other coordinate. The basic assumptions are that you can drive on road by car from parking lot to parking lot, and from parking lot to another point you can get only by foot. You can also add trains, and airplanes, each having less routes, but are actually faster. So for example, traveling from city A’s center to city B’s center is quite fast, but traveling from city A’s center to some point near the road from A to B will take some time.

This is a bit similar to computations done by game AI’s to determine how to get from point A to point B on a game board.

Now let us assume assume we want to draw the resulting graph on some kind of a 3D map, where the distance of each point from other points is determined by the time it takes to reach from that point to the others. Actually, it might not always be possible to plot this graph on a 3D map as a friend pointed to me, as 3 neighboring points already lock our point in space. But let us say that you can plot this 3D map. A’s center and B’s center will be near each other, a bit like a paper folding – which is incidentally the most common depiction of ‘science fiction wormholes’ explanations to laymen. It was pretty nice to try and visualize this kind of map. It is also interesting to think what is the least number of dimensions required to plot a given map.

Although I couldn’t come up with ideas about how this kind of visualization might be useful, it was still fun to to think of.

Interesting links – 3

Posted on by Leave a Comment

How to Write a Spelling Corrector

This was a very interesting article, with some interesting python code, and a good mathematical explanation. I enjoyed reading it. I got to it through Peterbe.com, which appeared on Daily-Python.

Robert Lang’s Origami Page

Fascinating page. A few months ago I was getting back to doing some Origami (it is a good relaxation method, also helps your wrists after typing too much :). I was trying to find ways to create origami creatures with more then two limbs, a head, and a tail, and I was fascinated by pictures of origami foldings of intricate creatures with many limbs, such as spiders and dinosaurs. I was also trying to formulate for myself some of the mathematical laws for origami. So I started to look into the subject and found out about crease patterns, and among many other sites, I got to Robert Lang’s site. The subjects he writes about are very diverse – and include using ‘origami knowledge’ to fold airbags, a program to create complicated crease patterns, an origami simulator (something I wanted to write myself :), and so on. Really, a fascinating read.

Interesting Links – 2

Posted on by Leave a Comment

Anti-Patterns

I first saw this term on The Daily WTF, in “Inner Platform Effect”. I quote: “They describe a frequently repeated problem in designing a commonly-occurring solution”. Recently I came upon them while going over wikipedia, and found that Anit-Patterns could be actually used as a teaching tool. Some patterns that were an interesting read for me are “Database as an IPC” and “Lava Flow”, mostly because I came close to them. It is interesting to note that programming is about naming things. When you successfully name a concept – it probably means you understand it. Going over this list might give you a frightning feeling of deja-vu. So read and take heed.

Catching Lions

Well, this is an old one… Not many people know, but the first mention of the subject was in the article by H. Petard, “A Contribution to the Mathematical Theory of Big Game Hunting”, that appeared in 1938. Since then many more articles were written on the subject. It is always amusing to note that the regular algorithm for searching a sorted array is often-times called “lion in the desert”, only because of this article. I actually wanted to look it up just because I came across this link, and near it were other old jokes, one of them being this old subject. This is usually regarded as the worst kind of humour :)