Marko's Hacks

Home network: Monolith vs beehive

2011-08-30T21:37:00.004+02:00

The first choice I am faced with is: a lot of small specialized devices, one large device or something in between.

One large server

Having one large server is a viable solution, albeit a classic one. A single 8 disk server running in RAID0 has more than enough storage space. It can serve as a SSH server and VPN server. A large server is also cost effective and easily(ish) upgradeable.

However, there are a few problems with one colossal server: power usage, noise and coolness factor.

A large machine requires lots of power. Now, granted, a lot of small machines add up to lots of power, however small machines are much simpler to switch off when not needed. Even though you can spin down drives in a server and clock down CPU it still costs you SOME power. And even if you do spin down drives and clock down CPU the PSU is still rated for 500W or so, so operating at 40W is not exactly efficient.

Large classic server also has a bit more moving parts and a larger box. This affects the noise both ways. You can suspend drives with elastic to reduce noise, pad out the box, use larger fans that spin on lower RPM and put in other sound improvements. What you can't do, is hide it. It's a big box that has to be connected to your TV and sound system. Of course you can drag cables or try wifi, but those are either ugly, require construction work or cost a lot. And that is if you have somewhere to hide a box of that size, which I don't really have.

Also, it's much more cool to build a large network of small machines. Much more SF :D

How would one large server look like?

For comparison I decided to look into a large server assembly as well. First off, some performance requirements.

Storage

I am looking at around 100GB of 3x replicated storage, 1TB of 2x replicated storage and around 2TB of non replicated storage. On top of that, some small amount of storage is used up by the OS, let's say 10GB SSD.
To get replication I can use RAID or simply make backup of everything on different drives. RAID is good because it comes with performance improvements, is mostly hassle free and is considered the way to go.
I however, do not think RAID is appropriate for home networks. In a typical home network, instantaneous replication is not really all that important. In fact, sometimes it's not wanted. If, for example, I would accidentally delete a folder RAID would be of no use to me at all. On the other hand, if I made automated backups to another disk every 6 hours, I would have at most 6 hours to rescue my data. Of course this means I don't have the performance benefits or RAID, and I have to take care not to ware out one drive more than other, but that can be coded away mostly. And performance is not such a big issue, once the initial copying is done.
Keeping that in mind, my storage needs can be satisfied by 3 2TB drives. Currently one of the best on the market are WD Caviar Green disks. They are low power, low noise and cost effective.

A WD Caviar Green 2TB drive is around 6.5W.

CPU/Motherboard

The most CPU intensive action for this machine would be HD video encoding/decoding. Today, that is not such a big thing. Both Intel and AMD offer "standard" and low power platforms. After going through the roundups at http://www.silentpcreview.com/, a site with lots of great reviews for silent builds, I picked out:

Undervolted Intel Core i5 2400 as it has the best performance per watt and is midrange in performance per dollar.
Intel Core i3 2100T has the best absolute power usage, rated at 35W

Both of these would easily power all my needs. Of course, a motherboard is needed as well, Asus P8P67 would do. Or any of that lot. Intel motherboards are said to be the most energy efficient ones. Intel DH57JG (not the correct socket for i3 2100 but....) is one of the better ones and puts CPU+MB at around 75W.

GPU and other

Is not needed. The integrated GPU in Intel chips is good enough for video playback. A stand alone GPU could easily use 100W or more, and would be the most expensive part in the whole box.

Total

So in total we have worst case power consumption at (75 + 3*6.5) = 94.5W. Truth be told, the drives will be idle most of the time, so will the CPU and MB so the number is somewhere in the 40-50W area. However, we do need a good PSU. Rated at 100W, at least. And since those are actually not so easy to find and can be costly, we probably end up with something along the lines of Enermax PRO II 425W, so 40W will actually be quite outside the optimal operation area.

With the modular design I am aiming at 10W while "idle", with a max of 54W on full usage. Also, perfect setup should be with 0 moving parts when the disks are spun down.

Now, I actually already run one such installation with a single large box. I will measure in full detail the power consumption on it and compare it to the eventual beehive design I plan to put up in my apartment. So at the end, there will be some real data here as well.

Home Network: Initial requirements analysis

2011-08-28T16:11:00.001+02:00

Introduction

I decided to pimp up my home network, and this time do it properly. It turns out, a lot of analysis goes into doing so, so I decided to keep it as a series of blogposts. This is mostly going to serve me as a central place for all my plans, but if someone finds my results usable, even better.

So the first step is to list everything I would like my network to do.

Use cases

The following is a list of use cases. You might notice that they are broken down into small, manageable chunks:

Data storage - photo
Data storage - audio
Data storage - video
Data storage - documents
Music player
Video player
Permanent SSH server (DynDNS)
VPN server

Some details for each case:

Data storage - Photos, Audio, Video, Documents

You might wonder why data storage was broken down in 4 components. The reason is lifetime. Storing photos is for life, or longer. I want to store all my photos, have automated backup system within the network, health checks and also manually assisted remote backup either to the cloud (Picassa proved usable so far) or to some other network under my control. This requires a paranoid level setup. Luckily, photos are usually on the order of 1-10MB size. Worst case for me are RAW 14.1MB photos.

Storing audio files is for decades. Some people like to imagine large collections of music. Perfectly sorted, tagged and ready for usage. I am one of them. Naturally, it takes quite a lot of time and energy to create such collections. Therefore it's a long lasting project. Years. Maybe decade or two. So I want my audio storage to be backed up within the network as well. File sizes are similar to photos for compressed, and a bit larger for lossless files.

Documents are also for decades. However, they are usually quite small. I can safely asume an average of 1MB per document.

Videos on the other hand, do not need such extensive backup and safety measures. They are however much much much larger.

Music &amp; Video player

All that data would be pointless if unused. A small HTPC, media center or some other form of music &amp; video player is needed. HD is probably required.

SSH server

SSH server is very important for two reasons:

It allows me to use the network even when outside
It allows me to grant access to the network to other people

I have a reasonable cable internet connection so bandwidth should not be a problem. Latency might be, but only in peak hours, and even then only for latency sensitive tasks such as editing files.

VPN server

Since I plan to have this kickass setup, I might as well use it to secure myself when I am out of the safety of the network. A VPN server would do wonders here.

Other stuff

Aside from what I would like the network to enable me to do, there are some other things I would like it to be. On top of the list is SILENT. I wan't the devices to be as silent as possible. What I am looking for is in the dark of the night, 3am, to be able to be in the same room with them and not notice anything. Luckily, this goes hand in hand with the next requirement: ultra low power. Some of the parts are going to be operational 24/7 and I do not want them to draw more power than is absolutely necessary. Next in line is cost. I understand that what I am going for is not the cheapest option out there, but I'm not ready to pay for overpriced hardware either. In the end, size matters. And visual design.

Research results: Can JavaScipt getTime() be used for measuring performance of JavaScript code?

2011-03-26T11:16:00.021+01:00

Recently, during research for my masters thesis I had to answer the question "Can we use JavaScirpt getTime() function in our benchmarks and get portable benchmarks that are valid?".

For the tl;dr crowd here is a short answer: Yes on Linux (and OS X probably) - not really on Windows.

After some research on the Internet, I found this blog post from 2008. by John Resig that explores this issue. He concludes that getTime() is basically useless on Windows XP irregardless of browser choice, while being safe to use it on OS X. I wanted to update his results to 2011 and explore the issue a bit more.

My goal was to measure the precision and not the accuracy (the difference is nicely explained in this Wikipedia article) of the getTime() function. We could do some analysis of accuracy, but opt not to because it's not so easy to setup a good experiment for accuracy. Precision on the other hand is nicely quantified in terms of the standard deviation of the experiment. Smaller standard deviation is better. The best possible outcome would be for the results to follow a very narrow Gaussian distribution.

The setup

The code for most benchmarks in JavaScript can be summarized in these three lines:

var start = (new Date).getTime()
doStuff()
var diff = (new Date).getTime() - start

so this is the scenario I decided to test. The obvious question of course is what to use as a sample load. It's important for the test load to have deterministic duration that can be easily controlled, and is too complicated for the browser to simply optimize away. A nice way to do this is to have a O(n^2) math function that does some of the slowest operations, such as the modulus operation. I used the following code:

    function sample(size) {
  var result = 0;
  for (var i = 0; i < size; i++) {
    innerSample(i, result);
  }
}

function innerSample(i, result) {
  result = i * i + i + (0x09F91102 % i) / 2;
  for (var j = 0; j < i; j++)
    result = (result * result) % (0x09F91102);
  return result;
}

The reason it's split in two is because I had a pre calibration step first. Since we are not interested in comparing relative browser speeds we do not need to use the same number of iterations of the sample function on all browsers. What would be much better is to have the same duration on all browsers. This is why, before testing, I run a pre calibration step that determines the number of iterations I should use so that the average duration of one sample is a bit under 75ms. Since we are not measuring accuracy a rough estimate will do just fine, as long as the duration is long enough so as to allow for anomalous shorter run times.

This completes the setup.

The experiment

The experiment is performed by looping 500 times over the sample code with the pre calibrated number of steps. After that the standard deviation is calculated. This is repeated a few times if possible to see if the results are stable.

The results

I tested Firefox 3.6 and 4.0 and Chrome 9 and 10 on Linux (Arch Linux 2.6.37 kernel), Windows XP fully patched and Windows 7 fully patched. I did run the Linux test on four machines: an Intel i3 desktop, two different Core2Duo laptops and Atom netbook and the results did not differ significantly. This shows that the hardware itself does not influence the tests. As for the Windows tests, I don't even own a Windows box so I used volunteer help for those tests (if you were one of these unfortunate "volunteers" I am so so sorry, I promise not to spam you all again). They were run on a wide variety of machines. There were significant variations on Windows machines, these are analysed below.

Mac OS X is omitted because I do not have access to a Mac OS X machine at the moment. In future the results will be appended. I also plan to include Opera and Safari. What will never be included is Internet Explorer, for two reasons: the script runtime limit in Firefox and Chrome is based on actual time whereas IE limits the number of operations you can execute between events (MSDN site sets the limit as ~5.000.000 operations) and, more importantly, you can switch OFF the runtime limit in Firefox and Chrome.

The results were pretty much consistent with the previous results from 2008. Here is a summary table of standard deviations:

	Linux	Windows XP	Windows 7
Firefox 3.6	0.5ms	6.8ms	[1.2ms, 7.3ms]
Firefox 4.0	0.4ms	37.4ms	[3.6ms, 7.9ms]
Chrome 9	1.2ms	12.7ms	[4.7ms, 17.3ms]
Chrome 10	1.7ms	33.8ms	[4.9ms, 19.7ms]

As you can see from the results, Firefox on Linux is the most precise with only 0.4 ms of deviation on 75ms test load. Chrome works OK on Linux too. It's worse than Firefox but still excellent. The results on Linux were stable across many different machines and are quite good. I did not test it against older kernels, but I don't think this is a major problem since all major Linux distributions do have up-to-date kernels.

This is a normalized graph of all 4 browsers on Linux. The X-axis values are omitted on purpose since each series is normalized so that the smallest value is 10. Since we are not interested in accuracy this gives a nicer and equally valid image:

As you can see the results are neatly packed with more than 95% of results packed in a 2ms range.

The results on Windows were much more inconclusive. You will notice that the results for Windows 7 are given as intervals. This is because the results varied wildly between different machines. The results were quite stable on any given machine, so it's not an artifact of the experiment itself. If you look at the best results, they are larger than on Linux, but still usable: 4.9 ms is not that bad. It's an order of magnitude bigger than 0.5, but still usable. In my personal opinion (since extensive tests should be done for a stronger result) good results on Windows were rare. Only 2 out of 10 Windows 7 machines produced good results. A typical distribution for a Windows machine is displayed below:

This chart was produced on Chrome 10 tested on Windows 7. Interesting observation is that the first few measurements were on the 75ms mark, but the execution slowed down afterwards moving the median value up to 125ms. This slow down was not accounted for or explained. It's left as an open question.

The conclusion

Using getTime() on Linux in the manner described here is VALID on both browsers. Using getTime() on Windows will give some results, but you can never be sure that another user will be able to repeat them on his machine.

The future

These results are a good start but there is much room for expansion. If time permits I plan to answer some of these questions in the future:

How does the standard deviation behave on longer loads, say 1000ms?
What are the possible factors affecting precision on Windows?
How do other browser place?
Do Windows results follow a pattern? Can some results be discarded and attributed to "start up" problems?
Test on more machines

The update

The code used can be found on GitHub https://github.com/ivankovic/cccm-benchmark. There is also a GitHub Page that can be used at once http://ivankovic.github.com/cccm-benchmark/

One possible reason for Windows is that the precision of the GetSystemTime system call is in the 10ms - 16ms range. This however does not explain why sometimes the results of Windows were good. Or how to deal with benchmarks on Windows.

Science in pursuit of lazyness: Cleaning a silver ring in 60 seconds

2011-02-09T15:47:00.003+01:00

I'm gonna go ahead and start with this: Following this advice will make you put metal inside a microwave. You probably should not be following this unless you can understand the full implications of that.

What is the best way to clean a silver ring with cubic zirconia ornaments? I have no idea.

There is however a lazy way to do it under 60 seconds. For this you will need:

The ring
Citric acid (the household variety, it's dirt cheap)
Small glass
Water
Microwave oven

Put enough water in the glass so that you can fully submerse the ring. You might want to leave at least some space between the water level and glass edge, because boiling could happen and cleaning the microwave would be very un-lazy.

Pour citric acid in the water. Make a fine solution. I have no idea how much I used, but I'm going to guess it as around 5-10%. Drop the ring in the acid. Put all of that in the microwave. Let her rip with 700W on 30 seconds, or until everything starts boiling and you think it would be a good idea to pull it out.

Carefully take the glass out, extract the ring, cool it, wipe it dry. Enjoy the no effort sparkliness.

Things to note:

Too much water is better than too little watter.

Citric acid is, well, acidic. Also, HOT citric acid will burn you. Use some gloves man!

The ring is made of metal, and metal in microwave is not a good idea. However, there should be no danger. In fact, we are counting on the fact that the metal will act as an antenna, causing it to absorb microwaves which in turn will heat up the metal much faster than the water around it causing:

The acidic reaction around the ring to speed up
Formation of water vapour bubbles on the ring surface that will physically remove dirt particles of the ring.

Darts during storms

2010-03-22T10:57:00.003+01:00

My brother and I tried to play darts outdoors a few days ago during heavy winds. Needles to say, it didn't exactly go as planned. It did however bring forth a crazy idea for a brand new sport.

The ballista darts!

Think about it, each team must construct a ballista from scratch. Then they fire comically sized darts into a 10-meter-radius dartboard. All other rules would be like standard darts, except everything would be HUGE.

It would be awesome. Until somebody loses an eye, that is. Than it would be just hilarious.

Simple fast edit distance

2010-02-09T15:32:00.004+01:00

Edit distance (or Levenshtein distance) is a measure of similarity between two strings. Given two strings A and B, if you are allowed to delete any character in B, insert a new character in B (at any position) or substitute any character in B what is the minimal number of operations required to turn B into A?

The solution is simple dynamic programming. Suppose we want to know how much operations it takes to make the first i characters of A equal the first j characters of B. If A[i] equals B[j] than it's the same number of operations it takes to make the first i - 1 characters of A equal the first j - 1 characters of B. If not, than its one more operation than making:

The first i - 1 characters of A equal the first j characters of B (this correspond to deleting a character from B)
The first i characters of A equal the first j - 1 characters of B (this correspond to inserting a character in B)
The first i - 1 characters of A equal the first j - 1 characters of B (this correspond to substituting a character in B)

Whichever number is the smallest, plus one, gives the answer. Using this we can solve the problem bottom up or top down. The worst case complexity of this algorithm is O(n * m) where n and m are lengths of strings A and B respectively.

Now, in certain areas this problem is expanded to: given a string A and a dictionary D. Find the closest string (with minimal edit distance) to A in D. The simple solution is to run the algorithm described above and just take the minimal distance. This however, can be greatly improved upon.

Our first observation is this, if the length of string A is n and the length of some string B in D is m. The distance between A and B is at least the absolute value of n - m. Now suppose that we have processed some words in D and the current solution is x. We now know there is no point in even considering any word whose length is more than x away from A.

But suppose we have a string B whose length is less than x away from A. Can we use the current minimum solution to our advantage here? It turns out we can. If you use top-down approach for the algorithm described above, you can maintain the current minimum number of operations. If this number increases above x, you can terminate that entire branch without fear. This reduces the complexity from O(n * m) to O(n * x). If we can rapidly decrease x to small numbers (say 1,2,3) this is quite a speedup.

The best way to rapidly decrease x is to apply the first observation again. The only words who can have edit distance 0 in D are those that have exactly the same number of characters as A. So it makes sense to first start with them and try to get x as small as possible. If we do not find a match, it makes sense to try words who have 1 character more/less first. Then 2. Then 3. Then 4. So by preprocessing D, grouping by word length, we can greatly increase the speed.

Another thing you might notice is that it makes sense to prefer the diagonal top-down move (using i - 1, j - 1 to calculate i, j) first since diagonals are more likely to yield smaller solutions.

If you would like to try out some of the things described here you can try this facebook puzzle. I was able to speed up my solution by a factor of 15 using the observations above.

No code this time, solve the puzzle yourself :D

Puzzled

2010-01-09T12:28:00.002+01:00

Tom Bohman, Oleg Pikhurko, Alan Frieze and Danny Sleator from Carnegie Mellon run a cool puzzle site The Puzzle Toad.

They present a series of quite interesting and challenging puzzles. A friend of mine raised some questions about the solution to one of their puzzles called "Seating".

Without further ado here is a monte-carlo simulation confirming their result.

On a side note the current puzzle "Let there be light" is fascinating and difficult and that same friend of mine and I are trying to storm it as you read this.

HTC Hero

2009-12-08T10:28:00.002+01:00

So, recently I got a HTC Hero and it really is good. Of course I am not the average Hero user, having no Facebook or Flickr (and Hero Loooooooooooves syncing with Facebook and Flickr) so I may be having a bit different experience than the rest. I got a black version of it, and my first thought when I saw it was: "Wow, this thing totally looks like some Sci-Fi scanning thingy". My first instinct was "Install scanning stuff". And oh did the market provide:

WiFi analyzer by Kevin Yuan - this is the hackers dream. It displays serious amount of data on wireless networks surrounding you. Channel list, signal strength, encryption type, BSSID. What it lacks however is the ability to save IV-s from WEP networks and handshakes for WAP networks. That would turn it into a real hacking tool. I know that active attack is the best for WEP but don't think that will come so fast to android.
Metal detector (not the musical kind) by Kurt Radwanski - does exactly what it says on the tin - it detects metal objects under your android. This is hyper useful if you ever need to drill a hole next to a power line. I tested it around my apartment and it successfully detected around 80% of wires running through my walls. It failed on one wall, but I think it is the main wall with armed concrete so it kept constantly detecting wall armature.
Compass by Snaptic, Inc. - a nice looking compass. Tested it, it works really well. Not much to say here. If I ever get lost, maybe I'll post more about it :)
GPS Test by Mike Lockwood - this one I installed a bit late in the game, it does one thing, but it does it good. It shows the GPS status and locations of detected satellites. Really useful if you want to check your GPS quality before launching Google Maps. It also helped me determine one important thing: GPS doesn't work while you are in train. Not sure why. I guess the train acts as a Farradey cage.
Spectral View Analyzer by RadonSoft - It computes the spectral analysis of audio input it gets from the mic and shows it on screen. I only have the free version, sampling in 0-8 kHz range but it works really well. The full version (4 euro) gives you the option to select ranges and color schemes. It's really fun to scan your speakers and determine the range they opperate in. Also, it changes the way you look at some things. You can notice patterns in sound that you would never notice before.

Now, there is one app that would do all this: the tricoder ( http://code.google.com/p/moonblink/wiki/Tricorder ). But I couldn't find it in the market. I am not completely sure why is that. The web site states that it can be found at the market, but my search runs blank every time I try.

So, that's that. I already downloaded Android SDK and will write stuff for it. Probably start with something WiFi oriented. I wonder how difficult it would be to write a passive sniffer for WEP IV-s and WAP handshakes.

Brainfuck genetic programming

2009-11-14T18:42:00.002+01:00

For fun and a bit of overkill I decided to code a genetic programming project. For starters I needed a problem so I decided to evolve Brainfuck programs. For starters I wanted to evolve a basic "Hello World!\n" program.

And boy was it different than I expected. First of all, NOT ALL brainfuck codes are valid. The brackets need to be balanced or the whole thing explodes. Second, not all valid brainfuck codes terminate. Now I did expect both of these things, but accounting for them was funny. At first I generated random strings of BF code, and accounted for it's validity in the fitness function. That did not turn out so good. Turns out it is much more efficient to always produce valid code, even if it does complicate mutations somewhat.

Other observations I made are:

A lot can be done in less than 10.000 execution steps of BF code. Setting 10.000 as the endless loop limit is ok.
Getting to the exact output is far more difficult than getting somewhere in the ballpark.
Crossovers are not as useful as advertised in this problem

Of course my code is quite bad and could be improved much more beyond this point, but it is usable as is so you can download it here. If you tinker with it and improve the performance drastically please let me know.

Oh yeah, fragments of the code suggest input support, and I do plan to evolve programs that consume user input. But that will be another post.

StarCraft AI Tournament

2009-11-13T11:37:00.002+01:00

I recently got this link from a friend:

http://eis.ucsc.edu/StarCraftAICompetition

It's so incredibly awesome. I always wandered how it would be to write a StarCraft AI but was always set back by the idea that I have to spend god-only-knows how long hacking StarCraft itself so that it lets me interface. But with the API these guys provided, this could prove to be quite fun.

It could actually be a continuation of my project for the machine learning class, the micromanagement part at least since it requires fast tactical adaptation.

CEPC

2009-10-17T17:33:00.004+02:00

Today my team and I competed at the university tryouts for this years CEPC. We totally rocked and are going as the second team for our university. All tasks, test data and results can be found here.

It's in Croatian, so in the off chance that somebody that doesn't understand it and reads my blog a brief translation is presented here: Zadaci = tasks, Test podaci = test data, Rezultati = results.

Wrocław, here we come!

Pmrpc

2009-10-05T15:33:00.004+02:00

I've been working on this project sometime now and finally it is good enough to be presented to the world.

Pmrpc is a HTML5 inter-window cross-domain JSON-RPC based remote procedure call JavaScript library. The library provides a simple API for exposing and calling procedures from windows or iFrames on different domains, without being subject to the same-origin policy. Pmrpc also provides several advanced features: callbacks similar to AJAX calls, ACL-based access control, asynchronous procedure support and fault-tolerance via retries.

It's based on open standards and distributed under Apache v2.0 license which is awesome :D

I'm very excited about it because it's such a bountiful project. We have a lot of ideas where to go next and we would appreciate community input to help us in choosing our direction. Comment here, on google code, why you can even email me if you like :D

Wikipedia game - in 5 clicks

2009-09-17T20:46:00.009+02:00

A friend of mine told me about a game he stumbled upon recently. It's called "five clicks to Hitler". The objective of the game is to go to the Wikipedia Random article page and try to get to Adolf Hitler article in 5 clicks or less.

I was a bit bored one day and said, "well, why would I play the game myself? Real programmers write scripts to do all the dirty work for them.". So I did. And I release it to the world so nobody has to actually play the game.

The starting page is passed as a command line argument. You don't need to enter the full URL. Just the part after "/wiki/". For example if you want to start from this Wikipedia article describing the fascinating Bodok seal: http://en.wikipedia.org/wiki/Bodok_seal , you would start the script like so

./wikiscp.py Bodok_seal

The default target of the script is the Wikipedia article on Mahatma Ghandi, but if you want to change that a -t command line option is provided. So if you would like to know the shortest click-path between the Bodok seal article and Alpine skiing article you start the script like this

./wikiscp.py -t Alpine_skiing Bodok_seal

Have fun.


#!/usr/bin/env python
# A small script that seeks the shortest path between two wikipedia articles
#
# Copyright 2009 Marko Ivankovic
#
#    This program is free software: you can redistribute it and/or modify
#    it under the terms of the GNU General Public License as published by
#    the Free Software Foundation, either version 3 of the License, or
#    (at your option) any later version.
#
#    This program is distributed in the hope that it will be useful,
#    but WITHOUT ANY WARRANTY; without even the implied warranty of
#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
#    GNU General Public License for more details.
#
#    You should have received a copy of the GNU General Public License
#    along with this program.  If not, see http://www.gnu.org/licenses/.


from urllib import FancyURLopener
import re
import getopt, sys

class CoolURLOpener(FancyURLopener, object):
   version = 'Mozilla/5.0 (Windows; U; Windows NT 5.1; it; rv:1.8.1.11) Gecko/20071127 Firefox/2.0.0.11'

opts, args = getopt.getopt(sys.argv[1:], "t:", ["target"])

target = "Mohandas_Karamchand_Gandhi"
limit = 5
for o, a in opts:
   if o in ("-t", "--target"):
      target = a

coolOpener = CoolURLOpener()
prefix = "http://en.wikipedia.org/wiki/"
for start in args:
   visited = {}
   existing = {}
   queue = []
   existing[start] = (0, "N/A")
   current = start
   num = 0
   links = 0
   targetFound = False
   maxDist = 0
   while not targetFound:
     visited[current] = existing[current]
     step = existing[current][0]
     del existing[current]
     if step == limit:
         current = queue[0]
         del queue[0]
         continue
     handle = coolOpener.open(prefix + current)
     data = handle.read()
     data = re.findall(r"<a href=\"/wiki/(.*?)\" .*?>.*?</a>", data, re.S)
     num = num + 1
     for candidate in data:
         if not ":" in candidate and candidate != "Main_Page":
          links = links + 1
          if not candidate in visited and not candidate in existing:
              if candidate == target:
               targetFound = True
              existing[candidate] = (step + 1, current)
              if step + 1 > maxDist:
               maxDist = step + 1
              queue.append(candidate)
     current = queue[0]
     del queue[0]
   
   if target in existing:
    print "Target found in %d steps" % existing[target][0]
    print "Path is (upsidedown):"
    print "\t %s" % target
    target = existing[target][1]
    while target != start:
     print "\tarrived from: %s" % target
     target = visited[target][1]
    print "\tarrived from: %s" % target
   else:
    print "There is no link between %s and %s" % (start, target)