Labels

3G (1) 8600GT (1) AI (4) amazon (1) API (1) apple (3) apple mail (1) atlassian (1) audio (1) bambo (1) Bamboo (1) bloat (1) boost (1) bugbear (1) C++ (5) calling conventions (1) cdecl (1) chromecast (1) CI (1) compiler (1) continuous integration (1) coursera (1) custom domain (1) debugging (1) deltanine (1) diagnosis (1) diy (5) DLL (1) dns (1) don't be evil (1) ec2 (1) education (1) electronics (1) express checkout (1) fail (6) fink (1) firewire (1) free hosting (1) GAE (1) google (1) Google App Engine (4) H170 (1) hackerx (1) hackintosh (1) Haskell (3) homebrew (2) i1394 (1) icloud (2) iOS 9 (1) ipad2 (2) jobhunting (2) lag (1) letsencrypt (2) libjpeg (1) linux (1) mac (2) mbcs (1) mechanic (1) memory (1) MFC (3) Microsoft (1) migration (1) ML (1) mobile (1) movi (1) MSBuild (1) music (1) naked domain (1) NLP (2) o2 sensor (1) obd (1) Optiplex960 (1) osx (1) outlook express (1) payments (1) paypal (1) photos (2) PIL (1) Project Euler (1) projectmix (1) python (2) raspberrypi (3) recruitment (1) renwal (1) skylake (1) soundcloud (1) ssl (2) stdcall (1) stripe (1) subaru (2) supermemo (1) supermemo anki java (1) sync (2) Telstra (1) tests (1) thunderbird (1) udacity (1) unicode (1) Uniform Cost Search (1) university (1) upgrade (2) vodafail (1) vodafone (1) VS2010 (1) vs2013 (1) VS6.0 (1) weather (1) win (1) Win32 (1) Z170 (1)

Monday 31 December 2012

Upgrading the RAM in a 2006 MacBook Pro (Merom) - MacBookPro2,2

I just upgraded the RAM in a 2006 Macbook Pro with the Merom Chipset - the system identifier for this mac is MacBookPro2,2 ( About this Mac ->More Info->System Report).

The ram it comes with is DDR2 667 Mhz 5300 SO-DIMM - this ram is hard to come by these days and I heard conflicting reports about whether higher speed RAM would work. Apparently the later model Penryn chipsets machines would not downclock the RAM and fail to to boot.

Anyway, my local computer store had some Patriot 800Mhz RAM for much cheaper than the Mac spec RAM could be had on ebay, so I took a chance and bought some.

After a false start because I didn't seat the RAM properly, I can report that 800 Mhz RAM works on my MacBookPro2,2 just fine!

Wednesday 7 November 2012

DLL hell


I have recently found myself working on a C++ MFC application written in MSVC 6.0 . After my initial despair about not being able to port it to VS2012, due to some legal issues – it is based on a third party product, and whilst we have the source code, and the changes required to get it to compile are minor we are required to engage the third party to make ANY code changes to their source code.
Anyway, I though the least I could do was upgrade the compiler to VS6SP6. This was mostly painless, just a few small code changes.
The most interesting compiler bug that was uncovered is illustrated below:

class foo
{
public:
     foo() {}

     static void bar();

protected:
     bool m_var;
};

void foo::bar()
{
     char * message;

     message = m_var ? "foo" : "bar";
     printf( message );
}


Note that a static function is able to reference an instance variable of a class so the above code should not compile... in fact, in this case it only compiles when used with the ternary operator - ? as 

if( m_var )
     printf("foo");
else
     printf("bar");

produces the compiler error. This bug was fixed in one of the service packs.
Anyway, after upgrading my machine to VS6SP6 I found that I would encounter COM registration errors with DEBUG code built on other machines without SP6... and bizarrely even code built with SP6. Code built on my machine was okay.
These errors manifested as debug asserts such as:

"File: Ctlreg.cpp Line:520"
"File: Olecli3.cpp Line:502”
"File: Olelink.cpp Line:288”
"File: Olelink.cpp Line:291”

As the code was written to link dynamically with MFC and the c runtime library – I suspected I was in DLL hell- I had the wrong versions of some obscure dll. The best way to diagnose this is with dependency walker –also known as depends.exe. This will load an executable or dll and tell you exactly what other dll files it depends on.
In this case I found:

MFC42D.DLL
MFCO42D.DLL
MFCD42D.DLL
MSVCP60D.DLL
MSVCRTD.DLL

When I replaced these DLLs with versions from machines without the problem, the problem resolved on my machine. The question was, which DLL was the culprit? I was suspicious of the MFC dlls, as the asserts were in MFC code. It turned out to be MFCO42D.dll – the version on my machine was dated 1998 version 6.0.8168.0. The SP6 version was dated 2004 and had version 6.0.9782.0.
For some reason, VS6SP6 failed to update this DLL when installed on my machine.

Anyway, the upshot is that the MFC debug DLLs are NOT binary compatible between versions of the compiler.

Plenty of people have stumbled across this problem in my google searches, so I thought I would post this for the next person! Hope it helps you

Wednesday 24 October 2012

War On You

Obama has been in the news a lot lately due to the upcoming presidential election, so I took the opportunty to update an old track from my album Entheogenic with some Obama samples and additional production.

It's good an old skool vibe with 303 bass and 909 drums. It's on soundcloud!

Monday 22 October 2012

RaspberryPi

Today I was excited to find my RaspberryPi in my mailbox months after I placed my order with RS.

I checked the serial and unfortunately I didn't score the upgraded chip with 512 Mb memory.
I also didn't realize that it needs a micro USB cable to connect the power... of the myriad of computer cables I have collected over the years, I had never managed to aquire one of those, so it had to wait for a trip to my local computer store.

Anyway, that gave me time to setup an SD card with linux so it would actually boot and when I finally I powered it up I had the joy of watching the linux boot sequence as she booted up. When running, these things draw only 3W of power and my big plan for this baby is for a remote internet enabled door opener, so my first step was to get an IO module with some relays off ebay.

More news as it follows

Tuesday 18 September 2012

The Knights Travail

Recently I was challenged to solve the Knights Travail in C++ - its a fairly simple problem in finding the shortest path between two squares on a chess board that would be legal moves for a knight piece.

The knight can move 2 squares across and 1 square up or down and vice versa. The positions on the chess board are represented using algebraic notation. There are a number of ways to solve this problem, but I chose a simple uniform cost search - which is like a bredth first search with each move on the chess board being having an equal cost, so the shortest path will always have the least number of moves. 

Because this challenge was to demonstrate my knowledge of C++, of course my solution is object oriented and completely over engineered. Anyway, you can find my solution here: The Knights Travail.

It's hosted on ideone.com so you can even execute it and put your own travails in. Just type them in to the input box down the bottom, eg: A1 B2

Happy Travailing!

Sunday 16 September 2012

Google weather api is dead... long live wunderground.com

Recently google retired their free weather api... it was never officially supported, and was always a private API, but nonetheless many, many applications came to rely on it, and were rudely broken last month when the api stopped working.

Anyway, this also broke http://sydneyinlinehockey.com, so after some research I settled on wunderground which has a pretty good replacent which is free for up to 500 requests a day. You have to apply for an api key to call it and the response can come back as xml or json. I prefer json as it is so easy to parse python.

It is this easy to call... what are you waiting for? Fix your apps with broken weather now!


Saturday 25 August 2012

Migrating from Outlook Express to Apple Mail

The other day I arrived home to find my elderly neighbours lugging a rather large large box from their car - on closer inspection I could see it was a brand new iMac. Their 6 year old Dell had died and they had been convinced by their friends to crossover to the Apple ecosystem.

Unfortunately, the so called Apple Genii at the Bondi Junction store were incapable of transferring over their old files as promised so I offered to help. Although the screen was dead on their Dell, it made some whirring and booting noises so I pulled out the HDD to see if I could recover anything. Thankfully the disk seemed fine, I was able to mount it on my windows 7 box and copy off all the files (so much for the skills of the apple genii).

I was able to load the contacts into Windows 7 contacts and export them as vcd files so they could be imported into the mac. The path for the outlook files was a little more convoluted....

This is how I managed to do it.... basically the workflow was Outlook Express Data Files -> Windows Live Mail -> export to eml files -> Import eml files to Thunderbird -> export Thunderbird to mbox -> cleanup mbox files with clean_moz script -> import cleaned mbox files in to Apple Mail.

Here are the details:

I downloaded Windows Live Mail as Outlook Express is not supported on Windows 7. It was able to import the outlook data files once I was able to find them... their location varies depending on the version of windows and outlook express, but from memory I think they were in the Local Settings/ApplicationData directory (this is a hidden folder so you need to enable viewing of hidden files  to see it).

Next I exported the mail in Windows Live Mail format- from memory I think this stores the mail in a folder structure, with each email as an individual eml file

Then I imported the Windows Live mail into Thunderbird, using the thunderbird import export tools plugin.

Then I used the Thunderbird import export plugin to export the mail. Thunderbird stores its mail in the mbox format, which Apple Mail promises to import.

Next, I used the import feature on Apple Mail to import the data in thunderbird format. This took a long while, but somehow only managed to import a single email from each folder. Same result when I imported the mail in mbox format... after some google foo I discovered the Apple Mail import is a bit broken  and does not fully support the mbox format.  Thankfully Trevor Harmon had this problem back in 2004 and wrote an awesome python script to cleanup the mbox files so Apple Mail wouldn't choke.

After cleaning, the files imported perfectly- thanks Trev!


Tuesday 17 July 2012

Subaru Outback O2 sensor replacement...

In a previous post I mentioned how I had managed to diagnose a check engine light on my 2005 Subaru Outback and tracked down the fault to a burned out heater coil in the front o2 air/fuel or lambda sensor.

After baulking at paying $530 for the official Subaru part I tracked down a compatible Denso sensor part number 234-9015 on ebay for only $110 shipped from the USA. Then it lay around on my shelf for a month or two, as I actually had no idea where this part was supposed to go.

I didn't have a service manual, so I watched a few you tube videos, and read some forum posts, then finally got under the car and had a look. Finally I saw what looked like an O2 sensor, it was on the exhaust system as expected, but there was barely any room under the car, and it looked like I needed a special tool- a 22mm O2 sensor wrench to remove it anyway. I duly ordered the tool from ebay for $17, then one Sunday afternoon parked the car with the drivers side wheels up on the kerb so I could squeeze under the car and replace it.

I came off easier than I expected, but it looked a little different to my replacement part. Never mind, I plugged it in, also noticing that although the plug fit, the connector was not quite the same either, and would need to be taped to hold it together.

It wasn't till I started the car and checked the OBD codes on my Mac with the excellent Movi software that I realized the damn error codes were still present... only then did it twig that I had mistakenly replaced the rear O2 sensor!!! Finally, I located the front O2 sensor, but it was up near the drivers side wheel obstructed by the plastic engine undercover, and looked like it would be a real pain to replace from  under the car, as it would involve removing the engine undercover. After much cursing, I swapped back the original O2 sensor, incredibly glad that I didn't remove it by cutting the wires, and resolved to pay my mechanic to fit the replacement sensor a my next service.

But it actually turned out easier than I expected - I opened the bonnet and removed the air intake duct that goes into the air filter so I could get a better look and observed that it was quite possible to remove the O2 sensor without having to muck about under the car. It was about as hard as replacing a light bulb, then all I had to do was clear the codes and BAM! No more annoying engine light and flashing cruise control indicator distracting me on the dashboard.

So all up it cost me $110 for the part, $17 for the tool, $20 for an OBD code reader and $50 for the software... all up $197 instead of $530 for the official part, plus labor.

So awesome, I blogged about it...



Wednesday 11 July 2012

Google App Engine with a custom domain

So, you don't want to publish your brand new groundbreaking web app to the world with a boring old url like http://sydneyinlinehockey.appspot.com ?


Just say say you want to use your own custom domain such as sydneyinlinehockey.com.

One would think this would be a relatively simple and straight forward thing to do, but apparently not so...

First they make you sign up to Google Apps, then you have to prove you own the domain, then finally you have to tell them the domain name you plan to use, finally you have to update the details with your dns registrar so it points to google apps hosted website.

This was the tricky bit... so if anyone else wants to know how to do it, here's how I did it.

you need to create a CNAME record for your website,

eg:

www.sydneyinlinehockey.com

and point it to:

ghs.googlehosted.com.

Google app engine does not support naked domains, such as

http://sydneyinlinehockey.com.

to get this to work I setup a 301 redirect with my dns registrar, redirecting

sydneyinlinehockey.com

to

www.sydneyinlinehockey.com

voila.

just posting this cos I spent hours googling this...


Friday 6 July 2012

Installing Python Image Library (PIL) with jpeg support on mac os 10.7.4

Recently I have been playing with Google App Engine - I'm porting the  Sydney Inline Hockey website from PHP (ugh!) to Google App Engine using Python.

Anyway, in order to use the google image library to manipulate images in App Engine, you need to have Python Image Library installed locally if you want to test your code.

Python's easy_install module maged to install PIL, however at runtime it would crash with an error about no jpeg decoder. No jpeg support was a bit of a dealbreaker... it seems libjpeg needs to be installed before PIL.

That's cool - lets just install libjpeg using fink, which seems to be one of a myriad of different tools for installing package on unix systems. But I didn't have fink installed...

after much yak shaving, I was finally able to to type:

sudo fink install libjpeg
sudo easy_install PIL

and it was all good!

For detailed instructions - see this post on Marcio Garcia's blog. Thanks Marcio!




Monday 7 May 2012

Subaru Outback check engine light diagnosis

The other day the check engine light came on on my 2005 Subaru Outback. The manual says take it in to a service centre to have them check it out... sounds expensive!

Most modern cars have an OBD II interface you can connect to the cars computer to find out what the check engine light means. The OBD port on my Subaru Outback is located under the dash above the accelerator pedal. OBD scanners or code readers can be found on ebay for as little as $15 dollars so I thought I would try and diagnose the issue myself.

I actually opted for a bluetooth OBD scanner from a local seller based on the ELM-327 chipset for around $30 - thinking "cool, I can use my iPad or iphone to see what my car is doing"

That was a mistake - Apple have crippled the bluetooth interface on the iphone so that it only works with handsfrees and does not support the serial port profile. But it will work with android devices.

The other mistake was that pairing a bluetooth device adds another layer of complexity compared to using a USB scanner. I could pair it with my mac, but could I find any free software I could use to download the codes from my car? No... the only thing that seems to exist on the mac are two python projects, confusingly both named pyobd - this one and this one - pyobd2. Neither of which I could get to work - pyobd2 would run but not find my bluetooth serial port and pyobd would crash when I tried to run it.

So then I turned to windows - which has a myriad of software for reading OBD scanners - most incredibly ugly VB apps. Unfortunately I couldn't get any of them to read codes from my OBD bluetooth scanner under parallels on the mac... at best they would connect but then fail to read any data from my OBD scanner.

However, there is some nice software on the mac that will do the trick- movi. I downloaded the demo version, verified that it works with my scanner. But I could read any codes until I bought the full version, so I gritted my teeth and forked out $52 bucks to buy it from the App store.

Lo and behold - the mysterious code was P0032 - which means high voltage on the front oxygen sensor heater coil. Most likely the heater coil had burned out - which is not that serious - it just means it will take a little while to get accurate readings from the air -fuel sensor when the engine is cold until the sensor warms up. But having an engine warning light may mean your car will not pass rego.

So i called my local subaru dealers spare parts desk, gave him my vehicles VIN code and he advised me that the part I needed was part number 22641aa230, which was in stock and available for the bargain price of $530!!!

After my jaw hit hit the ground in shock I did some googling and found I could buy the genuine subaru part online in Australia for as little as $250. But I kept searching, and discovered that the subaru genuine part is manufactured by Denso, and the Denso equivalent part number is 234-9015. There is also a Bosch part 15501.

Further googling revealed that the Denso part on ebay could be had for $105 including shipping from the USA to Australia- what a saving! I think that is where I will be buying it from. But first I need to open the hood, and see if I can locate that pesky air/fuel sensor and see how feasible it is for a car novice like me to replace.

Anyway, I just thought I would post this info for the benefit of anyone else to save me the hours of googling I wen through.





Wednesday 25 April 2012

Hackintosh on Dell Optiplex 960 with Nvidia GeForce 8600 GT

Recently, I bought a GoPro Hero HD2 camera which I have used to gather some 1080 footage... unfortunately the extremely long in the tooth early 2008 MacBook Pro I'm typing this on struggles to edit it. I really need to upgrade it - only only one USB works, and intermittently at that - and the audio has its good and bad days - however I can work around those issues with the odd NVRAM reset to fix the USB ( hold down the power button for 5 seconds when the machine is off and the battery removed) and some bluetooth headphones solves the audio issues - so no need to upgrade just yet.

I tried Windows Live Movie Maker on a fairly grunty Dell optiplex 960 with 8 Gig RAM- but that POS software kept crashing every time I rendered my video, and anyway it only supports Microsofts proprietary WMV format.

Since I know how to use iMovie and I didn't want to learn anything else, I thought I would see if I could install OSX lion 10.7.3. I had already managed to run it in a VM, but the video driver for the VM didn't support Quartz Extreme, which is required to run iMovie.

Anyway, after several days I managed to get it all working for the following configuration with my Nvidia GeForce 8600GT card, so if anyone else wants to give it a try here a few tips that might save you the several days of pain I went through.

* Make sure your bios is in AHCI mode

* I used the iATKOS L2 installer DVD - which hangs during boot on an Optiplex 960. So I removed my HDD, put it in an Optiplex 755 which managed to boot and install the OS. I then swapped the disk back into my Optiplex 960 which successfully booted. I then ran software update, and downloaded the 10.7.3 Combo update standalone to bring the machine up to 10.7.3. There are other ways to install OSX, which involve using a USB key to boot the machine and a retail copy of the OSX lion DVD

* I now had OSX with no network, sound and only basic graphics

* using MultiBeast I was able to install the kernel extensions (kexts) to get the network card working. I used the AppleIntelE1000e network driver, which is packaged with Multibeast.

* I couldn't find any drivers to support the onboard sound hardware ADI 198x Integrated HD Audio.
Luckily I had an old soundblaster live card lying around and was able to install the awesome kx project audio drivers by Eugene Garilov. Unfortunately the audio inputs don't work, but I was pretty stoked that my 12 year old soundcard has a new lease on life in my hackintosh!

Getting the video working was the biggest pain.

Some suggestions I found by trawling the forums such as adding the GraphicsEnabler=Yes setting in the org.chameleon.boot.plist file that is used by the boot loader did NOT work. Neither did hardcoding some magic EFI string distilled from the video cards ROM.

What finally worked was installing NVEnabler64.kext. All the forum posts seem to assume you know how to install kexts... kext utility is what you need to do this. Just drag the kext file onto kext utility and it does all the magic, copying the files and repairing permissions. I found it only worked if it was in System/Libaries/Extensions... not Extras/Extensions as mentioned in a few forum posts.

And voila... you now have a working Hackintosh.

If you are thinking of trying this then http://www.osx86.net and http://tonymacx86.blogspot.com.au/ or http://www.tonymacx86.com/ are great resources. Good luck!

Monday 23 April 2012

Awesome free online university level classes.

I just finished the inaugural offering of CS373 - Programming a robotic car at udacity.com. It was a really interesting course taught by the world leader in self driving cars and winner of the 2005 DARPA grand challenge, Prof Sebastian Thrun. I really enjoyed his teaching style last year when I did the Stanford Introduction to Artificial Intelligence course that was made available online. The other teacher of that class, Peter Norvig, also has a new class he's teaching at udacity - CS212 - The design of computer programs, which I'm enjoying as well.

Udacity have really done a good job adapting their content to the web - the lectures are made up of short, easily digestible videos for each topic with plenty of interactive quizzes and programming assignments along the way, which make it much more engaging than your traditional university lecture. Best of all, they are free and taught by experts in their fields.

There are also a lot of new courses from bricks and mortar universities coming online at Coursera too.
I just enrolled in Stanford's highly regarded  Machine Learning course which starts this week.

Tuesday 14 February 2012

Subaru Engine Immobilizer Shennanigans

My key for my Subaru Outback no longer remotely locks or opens the vehicle. This has been a minor inconvenience for a while- I have to open the drivers door manually and then operate the central locking to open the rear hatch or other doors. Anyway, today whilst strolling through Newtown I had the brilliant idea to get the battery replaced at one of those little key cutting places that for some reason was located at the back of a tobacconist. Strangely, this is not the only multi-function tobacconist in Newtown, there is another place across he road that features a barber out the back of pipes, bongs and incense blends of dubious legality. Anyway, I digress...

This particular key cutting business seemed to exist to provide employment for the tobacconist proprietors elderly father, who deftly went about opening my car key with a jewellers screwdriver and inscrutably inspected the innards. After much hunting through his poorly organised shelving, he indicated for me to come over and showed me the battery with the number 1620 inscribed on it that apparently he did not have in stock. This is what I assumed, because at this point I realised he had the faintest grasp of the English language. As he fumbled to reassemble my key, I heard the sound of something tiny hitting the floor which I assumed to be a screw, but when he continued assembling the key it seemed the screw was accounted for.

I thanked him and wandered off, half heartedly checking every store that I walked past that looked it might sell batteries for the elusive 1620 with no luck until I finally made it back to my car.

I turned the ignition and the car started then immediately stalled, which was extremely unusual, even more so considering the car had just been serviced. I tried again with the same result, and then my hear sank when I saw the little key light on the dashboard blinking plaintively. It was then I realised that the sound of a tiny thing dropping to the floor as my key was reassembled was actually the sound of my tiny immobiliser chip dropping to the floor and no doubt bouncing off into an awkward and inconvenient place somewhere out the back of the tobacconist/key-cutter business.

Fortunately I was able to grab a spare key, and armed with the working ignition key and my other non-ignition key that was now only useful for opening the drivers door,  I made my way back to the tobacconist on a mission to explain to the man who spoke no English that he had lost an extremely important and expensive thing and could I have a look on his floor? This was accomplished with help from the tobacconist proprietor, and when the old man opened my spare working key we could see a small, black rectangular prism shaped immobiliser chip was indeed missing. After a cursory look on the floor, he gave up and then with a small pair of scissors began fashioning me a replacement immobiliser chip out of a piece of black rubber to fill the sad void in the body of my car key remote. I explained it was a computer chip, which remarkably he seemed to understand, and ceased his miraculous feat of semiconductor engineering with the rubber and the scissors, and we had another proper look.

Finally, only after moving the extremely heavy rickety workbench where he had emasculated my key, the tiny chip was located and the key reassembled. Thankfully, it started my car the first time... but it still doesn't work the remote central locking!

Anyone know where i can find the elusive 1620 battery?


Saturday 28 January 2012

Decoding Shredded Messages in Haskell using AI techniques

Part 2 of my Introduction to Artifical Intelligence programming assignment was to decode a message,
which had been shredded and reassembled as a random jumble of strips like so:


de|  | f|Cl|nf|ed|au| i|ti|  |ma|ha|or|nn|ou| S|on|nd|on
ry|  |is|th|is| b|eo|as|  |  |f |wh| o|ic| t|, |  |he|h 
ab|  |la|pr|od|ge|ob| m|an|  |s |is|el|ti|ng|il|d |ua|c 
he|  |ea|of|ho| m| t|et|ha|  | t|od|ds|e |ki| c|t |ng|br
wo|m,|to|yo|hi|ve|u | t|ob|  |pr|d |s |us| s|ul|le|ol|e 
 t|ca| t|wi| M|d |th|"A|ma|l |he| p|at|ap|it|he|ti|le|er
ry|d |un|Th|" |io|eo|n,|is|  |bl|f |pu|Co|ic| o|he|at|mm
hi|  |  |in|  |  | t|  |  |  |  |ye|  |ar|  |s |  |  |. 


You could brute force this and generate all 19! combinations, but this is not the AI way.

The approach I took was to greedily combine strips from left to right until all strips have been used. That is, choose an initial starting strip then try all remaining strips, then choose the one that results in the highest score for the combined strips based on trigram frequency. Rinse and repeat until all strips used.

We then do this again, choosing a new starting strip from each of the candidates, and the result with the best score is our winner.

Sounds simple, doesn't it? However, to arrive at the correct result required some tweaking of the scoring.
In my first attempt, the first 15 or so strips would be correct but the last 4 would be jumbled... I think this was because the last line is mostly blank, which upset the scoring, which was based on the sum of the log probability score for each row (see my previous post for more info on trigram probability scoring).

Using only the first 6 out of 8 rows for scoring improved this significantly, however the correct answer was actually only the third highest scoring result. The other two were almost correct but started with a column of spaces. Tweaking the scoring code to punish rows with a leading space (assuming the text is left justified) brought the correct answer to the top of the list. Hooray!

This was quite a challenge, especially as it was only my third ever Haskell program.

If you're interested in seeing how I tackled this problem in a functional language like Haskell the source code is hosted on ideone. Any feedback appreciate!

Finally, here is the output:



Shredded Message Solver (ai-class)

shredded message:
de|  | f|Cl|nf|ed|au| i|ti|  |ma|ha|or|nn|ou| S|on|nd|on
ry|  |is|th|is| b|eo|as|  |  |f |wh| o|ic| t|, |  |he|h 
ab|  |la|pr|od|ge|ob| m|an|  |s |is|el|ti|ng|il|d |ua|c 
he|  |ea|of|ho| m| t|et|ha|  | t|od|ds|e |ki| c|t |ng|br
wo|m,|to|yo|hi|ve|u | t|ob|  |pr|d |s |us| s|ul|le|ol|e 
 t|ca| t|wi| M|d |th|"A|ma|l |he| p|at|ap|it|he|ti|le|er
ry|d |un|Th|" |io|eo|n,|is|  |bl|f |pu|Co|ic| o|he|at|mm
hi|  |  |in|  |  | t|  |  |  |  |ye|  |ar|  |s |  |  |. 

Top 3 results...
score: -1619.5501131298224

Claude Shannon founded information    
theory, which is the basis of         
probabilistic language models and     
of the code breaking methods that     
you would use to solve this problem,  
with the paper titled "A Mathematical 
Theory of Communication," published   
in this year.                         

score: -1631.76535223795

nnon founded informationClaude Sha    
ich is the basis of     theory, wh    
tic language models and probabilis    
e breaking methods that of the cod    
use to solve this probleyou would   m,
aper titled "A Mathematiwith the pl ca
Communication," publisheTheory of   d 
ar.                     in this ye    

score: -1632.7894584577352

nded informationClaude Shannon fou    
he basis of     theory, which is t    
uage models and probabilistic lang    
ng methods that of the code breaki    
olve this probleyou would use to s  m,
led "A Mathematiwith the paper titl ca
ation," publisheTheory of Communic  d 
                in this year.     

Tuesday 10 January 2012

Solving Caesar Ciphers Using Haskell

I recently completed the free online Stanford Universivity Introduction to Artificial Intelligence class, taught by Peter Norvig and Sebastion Thrun. I can't highly recommend this course enough if you are interested in AI - and did i mention it's free?

Anyway, one of the optional programming assignments was to decode the following message:

"Esp qtcde nzyqpcpynp zy esp ezatn zq Lcetqtntlw Tyepwwtrpynp hld spwo le Olcexzfes Nzwwprp ty estd jplc."

The message is encoded using a Caesar Cipher - a very simple shift cipher, where each letter is substituted for another a fixed number of positions down the alphabet. Those of you old enough to remember Usenet may have encountered rot13, which is an example of a Caesar cipher.

The key to solving this problem is probabilistic analysis of the text. My first, rather naive approach based on intuition rather a strict application of probability theory was simply to analyse the text with the assumption that the most frequent letter in English is 'e'. Using AI jargon, we could say I used a probabilistic unigram letter model.

Anyway, I thought it was a great opportunity to practice my freshly minted Haskell skills, and to my surprise this naive approach actually worked!

Blogger does a lousy job of inlining code so I have hosted the code here on ideone.com, an awesome site that not only displays code with syntax highlighting, it can even take input, run the code and display the output. Thanks to Maxim on aiqus for improving my Haskell code.

Flush with my success, I tried a more sophisticated approach. This time I would use a trigram letter model, which are basically sequences of three adjacent letters- for example, one of the most common letter trigrams in English is 'THE". The approach was to generate all 26 possible decoding of the string, and score each one based on the trigram probabilities, choosing the one with the highest score as the most likely candidate. A few tricks that I learned in AI class were employed here - I used Laplace Smoothing to ensure that unlikely trigrams that I didn't have scores for would not invalidate my probability score due to multiplying by zero.  I also used the log of the probabilities so I could simply sum them and didn't have to deal with ridiculously small numbers.

The source code, along with the trigram input data and output can be found here on here on oneide.com.
I have copied the output below

Caesar Cypher Solver (ai-class)

encoded message:
Esp qtcde nzyqpcpynp zy esp ezatn zq Lcetqtntlw Tyepwwtrpynp hld spwo le Olcexzfes Nzwwprp ty estd jplc.

The top 3 candidates based on trigram letter probabilities for english language
The first conference on the topic of Artificial Intelligence was held at Dartmouth College in this year.
score: -742.9796021883617

Nby zclmn wihzylyhwy ih nby nijcw iz Ulnczcwcuf Chnyffcayhwy qum byfx un Xulngionb Wiffyay ch nbcm syul.
score: -913.8004146160043

Esp qtcde nzyqpcpynp zy esp ezatn zq Lcetqtntlw Tyepwwtrpynp hld spwo le Olcexzfes Nzwwprp ty estd jplc.
score: -921.9751546970537

I would appreciate any comments on my Haskell code, I'm a bit of a novice...  and any other feedback would be greatly appreciated.