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?
Tuesday, 14 February 2012
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:
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:
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)
I would appreciate any comments on my Haskell code, I'm a bit of a novice... and any other feedback would be greatly appreciated.
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
Friday, 11 November 2011
iPad 2 glass digitizer replacement...
My iPad2 had an unfortunate encounter with the pavement recently resulting in a broken glass digitizer.
Replacements are readily obtainable off ebay for around $50 so I thought I would have a crack at fixing it, which is not as easy as you would hope. That's because Apple have made their best efforts in the name of built-in obsolesence and glued the screen on. This means that in a few years when your perfectly functional iPad's battery starts to fade, you'll probably have to throw it away and buy a new one because removing the screen to access the battery is a major ordeal.
I was lucky in that I did not have to worry about keeping the screen intact, since I had a brand new replacement.
I used the iFixit teardown guide, as well as some hands on support from my friend Spoonie, who had already done his own teardown -without him I'm sure it would have taken much longer.
Anyway, I discovered a few things on the way...
iFixit recommends you use a heat gun to loosen the adhesive, which helps a great deal. However, make sure it is not too hot, as the screen sits on a thermoplastic bezel, which melts and deforms if it gets too hot. I discovered this the hard way, and as a result the new screen doesn't sit flush like it should. I managed to crack my brand new screen trying to reseat it with a little too much force.
So, I have bought another screen, a replacement bezel and some proper adhesive to glue the new screen on.
Hopefully the job will be much easier the next time around!
Replacements are readily obtainable off ebay for around $50 so I thought I would have a crack at fixing it, which is not as easy as you would hope. That's because Apple have made their best efforts in the name of built-in obsolesence and glued the screen on. This means that in a few years when your perfectly functional iPad's battery starts to fade, you'll probably have to throw it away and buy a new one because removing the screen to access the battery is a major ordeal.
I was lucky in that I did not have to worry about keeping the screen intact, since I had a brand new replacement.
I used the iFixit teardown guide, as well as some hands on support from my friend Spoonie, who had already done his own teardown -without him I'm sure it would have taken much longer.
Anyway, I discovered a few things on the way...
iFixit recommends you use a heat gun to loosen the adhesive, which helps a great deal. However, make sure it is not too hot, as the screen sits on a thermoplastic bezel, which melts and deforms if it gets too hot. I discovered this the hard way, and as a result the new screen doesn't sit flush like it should. I managed to crack my brand new screen trying to reseat it with a little too much force.
So, I have bought another screen, a replacement bezel and some proper adhesive to glue the new screen on.
Hopefully the job will be much easier the next time around!
Friday, 21 October 2011
Installing an SSD without reinstalling windows
Introduction
Congratulations on receiving your new SSD disk! The best way to make use of it is to use it as your system disk and local subversion cache for lightening fast boots and builds.
It is possible to do without reinstalling windows and all your software using windows inbuilt tools such as Windows Backup and Disk Manager. This guide applies to Win2k8r2 but it might work for other OS versions
Step 1 - Install your SSD
You may need to tweak the BIOS to enable the SATA port if windows can't see the disk. Also make sure the SSD is higher in the boot priority than your existing system disk
Step 2 - Shrink your OS disk
Windows backup will only restore to a disk that is at least the same size the original volume. Delete any unnecessary files and shrink the volume using Disk Management. If you are lucky it will be small enough to restore to your new SSD. If you are unlucky there will be some unmovable files such as page files, or indexing files that prevent the disk being shrunk.
To remove the page file, disable virtual memory and reboot the computer
I found I had to disable indexing as well. Select "Indexing Options" in the control panel, remove all the folders or disks under "Included Locations". Then rebuild the index using the "Advanced" button.
Now try shrinking again. If its still to big you are out of luck, you will need to reinstall windows and all your favourite software.
Step 3 - Backup your OS Disk
Use Windows Backup or Windows Server Backup. Select Backup once and choose a custom backup - you want to select "Bare metal recovery", "System State" and your system disk (C: drive). I also has an additional partition called "System Reserved" that I backed up as well just in case. Choose a destination for the backup, either an external disk or your other internal disk and wait for the backup to complete.
Step 4 - Restore your backup
To restore a bootable system you will need to reboot with the OS install disk. I also disconnected the original windows disk just in case.
Choose restore your backup. Now at this point it failed with a cryptic message about a data disk having an active partition. This apparently was because my SSD had some stuff on it. I went to the commandline and ran diskpart clean - which deleted everything from the SSD. After that the restore proceeded successfully.
Step 6 - Reboot and enlarge your system disk
You system should reboot successfully and super quick thanks to the new SSD, but because you shrunk the windows partition in step 2 there may be some unallocated space on the disk. Use diskmanager to enlarge your c: partition and reclaim this unused space.
Step 7 - Enjoy your fast booting computer and lightning quick build times
I hope this guide was useful.
WARNING
I initially had a problem when I reconnected my original HDD with the OS on it. My dell optiplex 755 didn't remember that i changed the boot order, booted off the old disk and screwed the startup for the SSD. I suggest reformatting your original HDD to remove all trace of the OS before restarting with it connected to your computer.
Alternatively you may prefer to use the free disk migration utility from Intel
However, this will not work with server grade OSes like Win2k8
Thursday, 1 September 2011
Project Euler Problem 2
Due to my upcoming redundancy, I thought it is about time I learned some new skills, so naturally I have chosen to learn a language with virtually zero commercial application - Haskell.
So the first step in solving this problem is to generate a list of fibonacci numbers... which is very easy to do using Haskell's list comprehension feature:
This is because it is fiendishly inefficient, having to recalculate each entry in the list from scratch, rather than re-using the previous two entries calculation. Clearly, this approach will not satisfy the Project Euler criteria that the solution should take less than a minute to run.
A new approach to calculate the fibonacci sequence using the results of the previous calculation is shown below:
So in this case the effect of zipWith is to add the nth element of fibs with the n-1th element of fibs. This function will generate an infinite fibonacci sequence.
We can use a list comprehension to filter out the odd valued terms using the predicate x `mod` 2 == 0.
mod is actually a prefix function (ie: called before its arguments, eg: mod x 2 ), but using `backticks` allows us to call it using infix notation, which is more natural for mathematical functions.
Instead, we can use the takeWhile function which takes values from a list whilst as a boolean criterion is satisfied, eg:
If you don't know what Haskell is, it's a functional programming language, which means that is it it deals with what to do, rather than how to do it, as most people are used to with typical procedural languages such as C.
Anyway, a good way to learn a new language is to try it out on some classic problems, such as those on the Project Euler page.
Problem 2 states:
The fibonacci sequence starts with 0, 1.. then subsequent entries are constructed by summing the previous two entries. This conveniently recursive definition can be specified in Haskell recursively, ie:
fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = fib(n-1) + fib(n-2)
So the first step in solving this problem is to generate a list of fibonacci numbers... which is very easy to do using Haskell's list comprehension feature:
[ fib x | x <- [0..] ]This basically says construct a list by calling the function fib x, where x is bound to the range of numbers from 0 to infinity. Infinite lists are a quirky feature of Haskell made possible by its use of lazy evaluation, which means Haskell will defer actually calculating a result until it absolutely has to. The above expression will keep printing the list until the cows come home, but you will notice that after around 30 elements it gets slower and slower...
This is because it is fiendishly inefficient, having to recalculate each entry in the list from scratch, rather than re-using the previous two entries calculation. Clearly, this approach will not satisfy the Project Euler criteria that the solution should take less than a minute to run.
A new approach to calculate the fibonacci sequence using the results of the previous calculation is shown below:
fibs = 0 : 1 : zipWith (+) fibs (tail fibs )Note that it is recursively defined also. By way of explanation, zipWith is a function which takes two lists and applies a function to the elements in the same corresponding positions in the list and tail is a function which returns a list minus the first element.
So in this case the effect of zipWith is to add the nth element of fibs with the n-1th element of fibs. This function will generate an infinite fibonacci sequence.
We can use a list comprehension to filter out the odd valued terms using the predicate x `mod` 2 == 0.
mod is actually a prefix function (ie: called before its arguments, eg: mod x 2 ), but using `backticks` allows us to call it using infix notation, which is more natural for mathematical functions.
[ x | x <- fibs, x `mod` 2 == 0 ]Note that the predicate x <= 4000000 will also filter out all values less than 4000000, but the list comprehension will never terminate.
Instead, we can use the takeWhile function which takes values from a list whilst as a boolean criterion is satisfied, eg:
takeWhile ( <= 4000000 ) [ x | x <- fibs, x `mod` 2 == 0 ]
[0,2,8,34,144,610,2584,10946,46368,196418,832040,3524578]Now all that is left if to sum the list to get our answer
sum (takeWhile ( <= 4000000 ) [ x | x <- fibs, x `mod` 2 == 0 ])
Which makes me the 139646th person to solve that problem on the Project Euler page. Only 342 left to solve!
4613732
Thursday, 4 August 2011
SuperMemo to Anki database converter...
My girlfriend recently decided to move her study materials from SuperMemo to Anki, due to Anki's better support for Mac and a superior iPhone app that allows study cards to contain media such as images and sound.
However, she faced the prospect of losing all her learning history on thousands of cards, which would have meant unnecessary repetitions as Anki rebuilt her learning database.
Thankfully I found this useful project on GitHub:
https://github.com/ggodlewski/smux-anki-converter
It's a java program that converts the SuperMemo UX course data into Anki format. It seems to have been written to work on courses published from the SuperMemo website - but when I tried it on her data and it failed :(
It parses the supermemo SMPAK file, which is akin to the MS compound document file, ie: a single file which contains multiple streams of data. The course data is found in the course.xml and item####.xml streams in the SMPAK file. However, it seems that self created supermemo courses actually store the course data as XML files in a subdirectory called "override"- with the same names as the streams in the SMPAK file.
Grzegorz Godlewski's code did all the heavy lifting of parsing the course data and repetitions and then writing the data in Anki format. All I had to do was make a small change to first look on the filesystem for the courses xml files.
The only problem was I'm not a java programmer - C++ and C# are my areas of expertise, so I was forced to download the JDK, Eclipse and Maven and see what I could do. It was suprisingly not too painful... and I managed to knock up something that worked.
You can find my efforts here on GitHub:
https://github.com/pceccato/smux-anki-converter
Thanks to Gregorz for his hard work and sharing his code with the world!
However, she faced the prospect of losing all her learning history on thousands of cards, which would have meant unnecessary repetitions as Anki rebuilt her learning database.
Thankfully I found this useful project on GitHub:
https://github.com/ggodlewski/smux-anki-converter
It's a java program that converts the SuperMemo UX course data into Anki format. It seems to have been written to work on courses published from the SuperMemo website - but when I tried it on her data and it failed :(
It parses the supermemo SMPAK file, which is akin to the MS compound document file, ie: a single file which contains multiple streams of data. The course data is found in the course.xml and item####.xml streams in the SMPAK file. However, it seems that self created supermemo courses actually store the course data as XML files in a subdirectory called "override"- with the same names as the streams in the SMPAK file.
Grzegorz Godlewski's code did all the heavy lifting of parsing the course data and repetitions and then writing the data in Anki format. All I had to do was make a small change to first look on the filesystem for the courses xml files.
The only problem was I'm not a java programmer - C++ and C# are my areas of expertise, so I was forced to download the JDK, Eclipse and Maven and see what I could do. It was suprisingly not too painful... and I managed to knock up something that worked.
You can find my efforts here on GitHub:
https://github.com/pceccato/smux-anki-converter
Thanks to Gregorz for his hard work and sharing his code with the world!
Subscribe to:
Posts (Atom)