Google+ Pieces o' Eight: 2011

Saturday 31 December 2011

Understanding eBay/PayPal fees

Selling things on eBay used to be a pretty simple and straightforward affair. The costs were fairly easy to understand and people, generally speaking, were happy. Then eBay bought PayPal which should have made things even easier for all concerned, but strangely (or not so strangely) has resulted in a multitude of costs, fees and other considerations that directly impact your bottom line. I wouldn't exactly call these "hidden" costs, but nor would I describe them as "well advertised" and could certainly catch the unwary seller off-guard. Here is a brief guide on what to watch out for.

Sunday 11 December 2011

An implementation of LZW compression in Python

I've been doing some research on data compression and differencing recently and came across an excellent article by Mark Nelson on the LZW compression algorithm: http://marknelson.us/2011/11/08/lzw-revisited/

It's well worth a read, however all the code examples are in C++ so I decided to implement LZW in Python to enhance my understanding of the algorithm.

To start with we need something to compress. I picked the opening paragraph from George Orwell's 1984:

string = """It was a bright cold day in April, and the clocks were striking thirteen. Winston Smith, his chin nuzzled into his breast in an effort to escape the vile wind, slipped quickly through the glass doors of Victory Mansions, though not quickly enough to prevent a swirl of gritty dust from entering along with him."""

The next step is to initialize a dictionary with all possible single character codes:

codes = dict([(chr(x), x) for x in range(256)])

Here's the compressor:

compressed_data = []       
code_count = 257
current_string = ""
for c in string:
    current_string = current_string + c
    if not (codes.has_key(current_string)):
        codes[current_string] = code_count
        compressed_data.append(codes[current_string[:-1]])
        code_count += 1
        current_string = c
compressed_data.append(codes[current_string])

A couple of quick notes: I'm using a list - compressed_data - to store the compressed data, in the real world you'd probably want to use a file. You may also notice that code_count is initialized to 257, whilst the dictionary only has codes 0-255. What happened to 256? This is reserved for a control character, which I haven't implemented.

To decompress the data we just compressed, we need to initialize another dictionary containing all possible single character codes. In order for the algorithm to work, this dictionary needs to be the same as the dictionary used to compress the data:

strings = dict([(x, chr(x)) for x in range(256)])

You might have noticed that whilst this new dictionary contains the same data as the first the Keys and Values have swapped positions.

Here's the decompressor:

next_code = 257
decompressed_string = ""
previous_string = ""
for c in compressed_data:
    if not (strings.has_key(c)):
        strings[c] = previous_string + (previous_string[0])
    decompressed_string += strings[c]
    if not(len(previous_string) == 0):
        strings[next_code] = previous_string + (strings[c][0])
        next_code +=1
    previous_string = strings[c]

Again, next_code reserves 256 for an un-implemented control character. Also you'll see that I'm decompressing the data to a string, decompressed_string.

Finally, let's take a peek at the codes the compressor created and also display the decompressed string:

print "".join(str(compressed_data))
print decompressed_string

Conclusion

LZW is a pretty clever algorithm, but is also pretty easy to implement. Part of the cleverness is the way the decompressor is able to reconstruct the code dictionary used by the compressor on-the-fly and does not require the dictionary to be sent with the data.

My implementation is incomplete as it doesn't put a restriction on the number of codes generated and used, specify the control character or interface with files or streams external to the script, but even so I found it to be a useful examination of LZW and a good introduction to the techniques of lossless data compression.




Friday 7 October 2011

Setup Virtual Box shared folders with Linux Mint guest

Here's how to setup Virtual Box shared folders with a Windows 7 host and a Linux Mint 11 guest and have it automatically mount in Linux Mint on boot.

Software used:
Windows 7 (host OS)
Linux Mint 11 (guest OS)
VirtualBox v4.1.4

Instructions
1) Create a folder on your host machine - I created mine in the root of C: and called it Shared.
2) Start your Linux Mint virtual machine.
3) Once booted, click the Virtual Box Devices > Shared Folders... menu option:


4) Make sure Machine Folders is selected and click the Add button:


5) Navigate to the shared folder on the host and tick the Make Permanent box. 


6) In Linux Mint we now want to create a folder where the shared folder will be "mounted". Open a terminal and type:
sudo mkdir /mnt/shared
and enter your password when prompted.

7) We'll now make the share mount on boot. In the terminal type:
sudo gedit /etc/fstab

8) At the bottom of the file add a new line that reads:
Shared    /mnt/Shared           vboxsf           default               0        1

9) Save the file and reboot Linux Mint.

10) If everything went to plan, you should now be able to navigate to /mnt/Shared and view the shared folder!

How to: Install FreeBSD on Windows Virtual PC

DON'T BOTHER! YOU'LL ONLY WASTE YOUR TIME!

It took me about four hours to realise this, but Microsoft really don't want you hosting non-Microsoft operating systems in Windows Virtual PC. 95, 98, XP, Vista and hell even 7 hosting 7 works fine. Try a *nix O/S though and you're out of luck.

By the time I'd finally got FreeBSD installed - after much piss-balling about with vhd's - I thought I was on to a winner. But no. The cocking thing wouldn't boot and entered an eternal "Kernel Panic" reboot mode. Then, for fun, it did boot but wouldn't reboot properly. And finally, just for the kicks, it decided that the vhd was no longer a valid boot device!

I don't blame the FreeBSD lot for this. I installed VirtualBox and FreeBSD into it on the same machine and that worked fine. I'd suggest you do the same if you fell into the same Microsoft trap I fell into.

Thursday 6 October 2011

List comprehensions are cool!

Lists - or arrays - are an essential part of programming. While their usage varies depending on the problem being solved, the typical method of constructing one is to create a loop and append each new item to an array or list, as the following pseudo-code shows:

myList = new List

for i = 0 to 9

    myList.append(i)

end for

While this is perfectly ok, Python - and indeed other languages - provide an alternate method of creating lists based on existing lists known as list comprehensions. Lets see how the above pseudo-code example could be implemented in a Python list comprehension:

[i for i in range(10)]

The first and most immediate benefit is that the list comprehension took only one line of code to implement. This cuts down on the amount of boiler-plate required to do something as common as creating a list and also has the effect of making the code easier to read.

What if we wanted to build a list containing only the even numbers in the range? Well this is catered for by including an if clause in the comprehension:

[i for i in range(10) if i%2 == 0]

(Here I used the modulo division operator to only append the item (i) to the list if the remainder of the division i/2 is equal to 0)

List comprehensions aren't just for ranges of numbers:

[c for c in "abjkfghi" if c in "abcdef"]

In this example I'm scanning through a string and only appending the character to the list if it appears in the string "abcdef", and:

[d for d in os.listdir(r"C:\Photos") if d.startswith("Holiday")]

here I'm looking though the directories in my Photos directory and only appending those directories that start with the word Holiday.

As you can probably see from those few trivial examples, list comprehensions are pretty flexible and powerful and they save a considerable amount of time!

Saturday 24 September 2011

Improving my random password generator in Python

Learning Python is a great programming experience. The immediacy of the environment lends itself perfectly to experimentation, trying out new things and a very iterative approach to coding.

Previously I wrote a random password generator in Python. This worked well, but had a couple of problems. The first, identified at the time, was that there was a slight bias in the algorithm which would return certain characters more often than others. A second problem, identified after some pondering, was the inclusion of some redundant code. That version of the function had three lists and a dictionary - could this be consolidated down to just the dictionary? As it happens... YES!

The typical usage of dictionaries is to pass in a key to obtain a value. However, it's perfectly possible to obtain a key, value or both by supplying an index using a dictionary's .keys(), .values() or .items() methods and supplying the index such as:

phoneticDictionary.items()[15]

This means, of course, that it would be possible to get a randomly generated index from the dictionary, like so:

phoneticDictionary.items()[random.randint(0, 61)]

Knowing this meant I was able to alter my code to get rid of the three lists and use just the dictionary itself. It also got rid of the bias noted earlier.

Here's the complete listing:

import random

def getRandomPassword(length):
    phoneticDictionary = {"A" : "ALPHA",
                          "B" : "BRAVO",
                          "C" : "CHARLIE",
                          "D" : "DELTA",
                          "E" : "ECHO",
                          "F" : "FOXTROT",
                          "G" : "GOLF",
                          "H" : "HOTEL",
                          "I" : "INDIA",
                          "J" : "JULIET",
                          "K" : "KILO",
                          "L" : "LIMA",
                          "M" : "MIKE",
                          "N" : "NOVEMBER",
                          "O" : "OSCAR",
                          "P" : "PAPA",
                          "Q" : "QUEBEC",
                          "R" : "ROMEO",
                          "S" : "SIERRA",
                          "T" : "TANGO",
                          "U" : "UNIFORM",
                          "V" : "VICTOR",
                          "W" : "WHISKEY",
                          "X" : "XRAY",
                          "Y" : "YANKEE",
                          "Z" : "ZULU",
                          "a" : "alpha",
                          "b" : "bravo",
                          "c" : "charlie",
                          "d" : "delta",
                          "e" : "echo",
                          "f" : "foxtrot",
                          "g" : "golf",
                          "h" : "hotel",
                          "i" : "india",
                          "j" : "juliet",
                          "k" : "kilo",
                          "l" : "lima",
                          "m" : "mike",
                          "n" : "november",
                          "o" : "oscar",
                          "p" : "papa",
                          "q" : "quebec",
                          "r" : "romeo",
                          "s" : "sierra",
                          "t" : "tango",
                          "u" : "uniform",
                          "v" : "victor",
                          "w" : "whiskey",
                          "x" : "xray",
                          "y" : "yankee",
                          "z" : "zulu",
                          "0" : "Zero",
                          "1" : "One",
                          "2" : "Two",
                          "3" : "Three",
                          "4" : "Four",
                          "5" : "Five",
                          "6" : "Six",
                          "7" : "Seven",
                          "8" : "Eight",
                          "9" : "Nine"}

    password = []
    phoneticPassword = []                          
    for i in range(length):
        c, pc = phoneticDictionary.items()[random.randint(0, 61)]
        password.append(c)
        phoneticPassword.append(pc)

    return "".join(password), "-".join(phoneticPassword)

And here's the function's output run 10 times specifying a length of 8:

pnReI0lg papa-november-ROMEO-echo-INDIA-Zero-lima-golf
7g7SnNKl Seven-golf-Seven-SIERRA-november-NOVEMBER-KILO-lima
7Q3Zy4Ya Seven-QUEBEC-Three-ZULU-yankee-Four-YANKEE-alpha
697vxMRX Six-Nine-Seven-victor-xray-MIKE-ROMEO-XRAY
R214zUMk ROMEO-Two-One-Four-zulu-UNIFORM-MIKE-kilo
f0db3LbG foxtrot-Zero-delta-bravo-Three-LIMA-bravo-GOLF
IC9046VT INDIA-CHARLIE-Nine-Zero-Four-Six-VICTOR-TANGO
8mg5Vufa Eight-mike-golf-Five-VICTOR-uniform-foxtrot-alpha
C2Puu9dc CHARLIE-Two-PAPA-uniform-uniform-Nine-delta-charlie
tcK6OCsG tango-charlie-KILO-Six-OSCAR-CHARLIE-sierra-GOLF

Space Harrier 32X

Here's a quick video - level 1 of 32x Space Harrier played by me!


A random password generator in Python

For a recent project I needed to create a lot of random passwords. There are plenty of websites out there that can do this for you, but as I'm learning Python I thought I'd have a go at rolling my own solution.

My requirements were that each password be of a specified length and constructed from a random pick of the letters A-Z and a-z and the digits 0-9. I also wanted the function to return a phonetic spelling of each password. Here's what I came up with:


import random

def randomPasswordGenerator(length):
    upperCase = ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"]
    lowerCase = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"]
    numbers =   ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "1", "3", "5", "2", "4", "6"]
    phoneticDictionary = {"A" : "ALPHA",
                          "B" : "BRAVO",
                          "C" : "CHARLIE",
                          "D" : "DELTA",
                          "E" : "ECHO",
                          "F" : "FOXTROT",
                          "G" : "GOLF",
                          "H" : "HOTEL",
                          "I" : "INDIA",
                          "J" : "JULIET",
                          "K" : "KILO",
                          "L" : "LIMA",
                          "M" : "MIKE",
                          "N" : "NOVEMBER",
                          "O" : "OSCAR",
                          "P" : "PAPA",
                          "Q" : "QUEBEC",
                          "R" : "ROMEO",
                          "S" : "SIERRA",
                          "T" : "TANGO",
                          "U" : "UNIFORM",
                          "V" : "VICTOR",
                          "W" : "WHISKEY",
                          "X" : "XRAY",
                          "Y" : "YANKEE",
                          "Z" : "ZULU",
                          "a" : "alpha",
                          "b" : "bravo",
                          "c" : "charlie",
                          "d" : "delta",
                          "e" : "echo",
                          "f" : "foxtrot",
                          "g" : "golf",
                          "h" : "hotel",
                          "i" : "india",
                          "j" : "juliet",
                          "k" : "kilo",
                          "l" : "lima",
                          "m" : "mike",
                          "n" : "november",
                          "o" : "oscar",
                          "p" : "papa",
                          "q" : "quebec",
                          "r" : "romeo",
                          "s" : "sierra",
                          "t" : "tango",
                          "u" : "uniform",
                          "v" : "victor",
                          "w" : "whiskey",
                          "x" : "xray",
                          "y" : "yankee",
                          "z" : "zulu",
                          "0" : "Zero",
                          "1" : "One",
                          "2" : "Two",
                          "3" : "Three",
                          "4" : "Four",
                          "5" : "Five",
                          "6" : "Six",
                          "7" : "Seven",
                          "8" : "Eight",
                          "9" : "Nine"}
                          
    all = [upperCase, lowerCase, numbers]
    password = []
    phoneticPassword = []
    
    for i in range(length):
        character = all[random.randint(0,2)][random.randint(0,25)]
        password.append(character)
        phoneticPassword.append(phoneticDictionary[character])

    return ''.join(password), '-'.join(phoneticPassword)

It's pretty simple. The function takes a length n and then loops n times randomly picking one of three lists (A-Z, a-z or 0-9) and then picks a random entry from that list.

The chosen character is then appended to the "password" list and also passed to the phonetic dictionary, which returns the phonetic spelling of the character and appends it to the "phoneticPassword" list. Finally the function returns the password and phonetic password by joining the arrays into strings.

Here's the output of the function run 10 times specifying a password length of 8:

FAhFh0fy FOXTROT-ALPHA-hotel-FOXTROT-hotel-Zero-foxtrot-yankee
46Ne3XNu Four-Six-NOVEMBER-echo-Three-XRAY-NOVEMBER-uniform
1PcCnBX2 One-PAPA-charlie-CHARLIE-november-BRAVO-XRAY-Two
qAYVAB75 quebec-ALPHA-YANKEE-VICTOR-ALPHA-BRAVO-Seven-Five
y41Q3w7l yankee-Four-One-QUEBEC-Three-whiskey-Seven-lima
4NW55yYH Four-NOVEMBER-WHISKEY-Five-Five-yankee-YANKEE-HOTEL
bjihtPPk bravo-juliet-india-hotel-tango-PAPA-PAPA-kilo
H56a0Ydf HOTEL-Five-Six-alpha-Zero-YANKEE-delta-foxtrot
KaQkrlk8 KILO-alpha-QUEBEC-kilo-romeo-lima-kilo-Eight
77m302O1 Seven-Seven-mike-Three-Zero-Two-OSCAR-One

You might have noticed that the numeric character list contains some repetition to get the list length up to 26. I did this largely for expediency, but it does create some bias in that the numbers 1-6 have a slightly higher chance of being picked than 0,7-9. I'm not sure if this makes much of a difference, but it's as well to aware that this could be a potential weakness of the algorithm.

Without a doubt you could achieve the same in practically any programming language. What I particularly liked about Python for this, however, was the immediacy of the scripting environment and the built-in methods - such as "join" - which negate having to write tedious boiler-plate code to stitch strings together.

Saturday 9 April 2011

Fish! (A maths puzzle and a proposed solution)

A fish is made up of three parts: head, tail and body.

The tail is equal in length to the head, plus one-quarter of the length of the body.
The body is equal to three-quarters of the entire length of the fish.
The head is 4cm in length.


How long is the entire fish?

SOLUTION

Let's pose this in the following way:

T = Tail
B = Body
H = Head
L = Total Length

Therefore:
4 + 4 + 1/4 B + 3/4 L = L

Which can be simplified to give:
8 + 1/4B + 3/4L = L

Look also at the relationship between the Tail, Body and Total Length. The body, so we're told, is 3/4 of the Total Length and the fractional part of the tail is 1/4 of the length of the body. This means that we must be able to describe the fractional part of the tail in terms of the Total Length:

1/4 x 3/4 = 3/16

So the fractional part of the tail is 3/16 of the length of the fish!

Now we know that, we can work out what proportion of the fish the fractional part of the tail plus the body is:

3/16 + 3/4 = 3/16 + 12/16 = 15/16

So the fractional part of the tail and the body account for 15/16 of the Total Length, giving us:

8 + 15/16 L = L

What of the remaining 1/16 L? Well given the above, 1/16 L must be equal to 8 which means:

8 x 16 = Total Length = 128

So the fish must be 128cm in length! Lets try it:

1/16 L + 3/16 L + 12/16 L = 1/16 x 128 + 3/16 x 128 + 12/16 x 128 = 8 + 24 + 96 = 128

Sunday 13 February 2011

The Geek Manifesto

Mark Henderson - science editor of The Times - is writing a book on science and politics called The Geek Manifesto. It sounds like an interesting project in itself, but he's also set up a blog to canvass views, suggestions and other contributions.

You can find his blog here: http://geekmanifesto.wordpress.com/2011/01/14/introducing-the-geek-manifesto/

Five Sci-Fi Classics You Should Own

5 - Dark Star
For a film seemingly produce on a budget of about 50p and a length of string, Dark Star is one of the most influential films of the genre. Without Dark Star there would be no Alien and without Alien where would we be?

Suicidal smart bombs, alien life and a lack of toilet paper - this film has it all.



4 - Tremors
Ok, so Tremors rips the idea of giant worms straight from Dune, but when the result is this good we can let the plagiarism slide. This sci-fi comedy horror pretty much bombed at the box office in 1990, barely breaking even, but performed far better when it was released to video. It's easy to see why - the cast, script and production are superb and it manages to walk the fine line between comedy and horror almost perfectly.



3 - Aliens
Ah, the 80's. Big hair, big shoulder pads and big-budget sci-fi action epics. From start to finish, Aliens is an edge of your seat roller-coaster ride of tension, action, classic quotes you can apply to everyday life and huge explosions. If action sci-fi is your thing, it doesn't get any better than Aliens.

Just don't bother with the third and fourth films in the series.
 


2 - Akira
Some Anime/Manga is just plain weird, being little more than highly-fetishized cartoon pornography appealing to the frankly bizarre Japanese market. Akira isn't like that. The animation - which was all hand drawn - is simply stunning and while the script clearly loses something in translation enough remains to retell the epic story of ESP, government conspiracies and all-out nuclear war.



1 - The Thing
John Carpenter's masterful retelling of the 1951 classic "The Thing from Another World" works on so many levels it almost boggles the mind. From the humour to the suspense to the paranoia, everything is perfectly pitched to pull you in and deliver the sucker punch. The special effects are superb, the acting good (if not Oscar good) and the cinematography epic in scope. This is a film you'll watch again and again.

Saturday 12 February 2011

Martin to Base Station (The Odyssey Part 2)

During my recent dealings with Three Mobile in search of a better signal it occurred to me that I've never seen a mobile phone base station or mast in or around Fair Oak. This probably means one or the other of two things: 1) I've seen plenty of them, but not realised what they are or 2) They're generally in out-of-the-way places I don't tend to go. Feeling in an inquisitive frame of mind, I determined to find out where the nearest base stations to home are located.

My starting point was Google, which turned up Ofcom's Site Finder - an online utility that allows you to enter a postcode, town or street name and displays the nearest base stations on a map. You can then click on each base station to reveal details - such as operator, type and frequency range - about each base station. The site is a bit old fashioned and clunky, but it revealed the following result:



The blue triangles in top left quadrant of the map are mobile phone base stations, the furthest right of which is apparently Three Mobile's 18-metre tall, UTMS macrocell transmitter operating at 2100 Mhz.

Switching to Google Maps, the calculated distance between home and the base station is about a mile if following the directions given, or half-a-mile as the crow flies. Odd, then, that the signal should be so weak at home.

Zooming in on the approximate location of the base station was not as revealing as I'd hoped. Instead of seeing the base station clearly defined, all that was visible were trees, fields and buildings:


View Larger Map

Although disappointing, this was not altogether unexpected. As readers may be aware, Google use several different sources for images depending on the level of zoom. Images at this resolution are generally taken from aerial photography which, given the expense, may not be updated very often, so the image could well pre-date the building of the base station. It might also be the case that the footprint of a base station is so small that it isn't readily identifiable from an aerial photograph.

What was more surprising was switching to Google's street view. A ~20 metre tall mast should tower over the surrounding landscape, a cluster of 5-6 of them, as shown on Ofcom's map, more so. So why, then, did street view show nothing more than houses, fields and trees?


View Larger Map

Something was definitely up, and it didn't seem to be mobile phone masts! Was Ofcom's map wrong? Was Google out of date? Had alien invaders stolen them and left a message "All your base are belong to us" in their place? The internet having only got me so far there was nothing for it but to dress up warm, stock up on provisions and venture into Deepest Darkest Fair Oak.

In search of a better signal (The Odyssey Part 1)

Since upgrading my mobile phone to HTC's (utterly fabulous) Desire HD I've hit a minor snag: Three's data and voice coverage seems to be patchy at best in and around Fair Oak. In the five+ years I've been with Three this has never been much of a problem, so much so that I've never really noticed.

Although it seemed unlikely, given that in other places both voice and data signal was good, I wondered if this might be a problem with the handset. Three's post code search function certainly suggested that signal strength should be pretty good in Fair Oak so I registered a complaint on www.three.co.uk.

Within 12 hours I received an email from Three suggesting a couple of steps that might help. These amounted to little more than turning the phone off and then back on again, which needless to say did not fix the problem. So I filed another complaint, including the previous reference number and the results of Three's so called fault finding steps.

Two days later I received a call from Three's Customer Service department. I get to talk to India a fair amount during my day job and it's often a bit hit and miss as to a) whether you'll be able to understand the person on the other end of the phone, b) whether the person on the other end of the phone will be able to understand you and c) whether or not they'll actually do anything to help. Fortunately for me Three seem to have spent some time and effort training their people as the woman I spoke to was both easy to understand and helpful. She came to the conclusion that it probably wasn't the handset at fault and would I like to talk to Network Support? I confirmed I would and she attempted to put me through, but unfortunately the line was busy so she would arrange for them to call me.

The next day India called again - it was the Network Support team who confirmed that the low signal strength was due to a network coverage issue and would not be resolved until Three installed a new base station. I asked if there was anything I could do to escalate the call, and the chap on the end of the line said that Three were usually very quick to resolve these sorts of problems. I asked again if I could do anything to escalate the matter, and was put through to the Network Support manager. He also assured me that Three are very quick to resolve such matters and that he'd personally package up the call and pass it to the correct department. I've been fobbed off like this before, so I asked again if there was anything I could do to escalate the matter and so he gave me the URL of the complaints department and a call reference.

A day or so after filling in the complaint form with an explanation of the problem and the complete call history I received an email from Three's Customer Complaints department. This basically stated that although no dates have been confirmed, a new base station is due to be installed which should significantly boost signal in the area. We'll see. It's possible - and indeed highly likely - that I've been the victim of another corporate fob-off, but you never know.