250 Enigma Variations

It's been 11 months since I started up the Enigmatic Code site — a place to share programmatic solutions to New Scientist's Enigma puzzles — and I've just posted the 250th Enigma Puzzle to the Enigmatic Code site. This means there is the best part of 5 years worth of puzzles there, along with my own solutions to them.

I've got all puzzles from 2012 (to date), 2011, 2010 and 2009 and most of 2008, as well as some puzzles from the very start of Enigma in 1979 (thanks to Google Books) along with a handful of other dates that I've come across.

And so to celebrate the 250th puzzle going up I've posted the oldest not-yet published puzzle I've been able to find — Enigma 12: Cubic Walks — which after pondering over a Rubik's Cube for some time I came up with a sort of solution to in Python, although I'm not entirely happy with it. But it makes the list of Notable Enigmas, which is my personal view of the 20 most thought provoking Enigma Puzzles I've posted. (Also on that page are a handful of Enigmas that I've not been able to come up with a satisfactory programmatic solution for).

I will keep on posting new Enigma Puzzles as they are published in New Scientist, (they usually go up on a Wednesday evening in the UK) and I'm filling out the gaps with puzzles that I already have solved. I have programs going back continuously to Enigma 1482, when I started using them as a weekly programming challenge. Up until Enigma 1554 I was using Perl, but then I switched to Python and I've been using Python since. Sometimes I publish my original Perl code, but usually now I just write a Python solution rather than clean up my Perl code ready for posting.

Once the puzzles I've already solved are posted I'll start working through Google Books and put up older puzzles.

If you're a fellow Programmatic Enigmatist feel free to add comments to the Enigmatic Code site.

Mac to Mac AirPlay Mirroring

I've had my old laptop (currently a 2008 MacBook) plumbed into my TV for some time and use it mainly as a PVR by running EyeTV on it, but often I want to send media from my currently laptop to the TV and have never really found a satisfactory solution. [*]

Until now. Luckily the hardware on my MacBook Pro supports Intel's Quick Sync technology, so with the recent release of OS X 10.8 it is able to do AirPlay Mirroring to an AppleTV. Which would be great... if I had an AppleTV (and I've almost considered buying one just for this). But given that I've already got a MacBook plugged into my A/V set-up it would be more convenient to use that.

I tried a couple of free AirPlay server applications on the MacBook (both AirPlayer and BananaTV allowed media to be sent from Caroline's iPhone to the TV (BananaTV worked better with audio)) but they didn't allow AirPlay Mirroring from my laptop. But when I downloaded the paid AirServer app I found that it did exactly what I wanted. I'm less than a day into the week long free trial, but unless I find some serious flaws I'll be purchasing it.

Update 2012-09-24: There was a security update for my MacBook, which required a restart, which ended my free trial. But I purchased AirServer, and am happy with it. There are some problems with video/audio synchronisation when sharing the screen from the MacBook Pro to the MacBook (I found that setting the Audio Buffer Size to 2200 seemed to give the best synchronisation), but the best solution for streaming video is to do it from iTunes, and then the video and audio stay in sync.

[*] My previous best solutions were just to use a cable (3.5mm for just audio, HDMI for video/audio), although for audio only setting up AU Lab 2.1 to send the System Audio (intercepted by SoundFlower) to another instance of AU Lab running on the target system worked with the lowest latency. Setting up a reverse VNC connection worked well enough to allow displaying of photos to the computer plugged into the TV, but both of these are a bit fiddly compared to just plugging a cable in, or the wireless simplicity of AirPlay.

Farewall appscript?

In preparing for Macaroni Penguins Gig #126 tonight I noticed that my newly updated iTunes 10.6.3 didn't seem to be playing with my py-appscript scripts.

A quick search brought up this posting entitled "The first nail in the coffin of Python appscript", which reveals that new security technologies coming along in Mountain Lion (OS X 10.8) might well stop existing appscript based scripts from working. And anyway appscript itself is no longer being developed or supported, so I fully expect all my useful little scripts to gradually decay into non-functionality over time.

For the time being I have managed to use appscript.terminology.dump() to make a static glue from iTunes 10.6.1 that I can use to allow my scripts to continue to run with iTunes 10.6.3, but it doesn't feel like a robust long-term solution.

Update 2012-09-12: I updated to iTunes 10.7 (under OS X 10.8) and my py-appscript scripts are working again. Hurrah!

Another One Bites The Dust

In 2008 I bought a Western Digital My Book Home Edition 500GB external hard drive to do Time Machine backups to. Although when I got a Time Capsule the drive was repurposed as an adjunct to my Media Centre Computer (i.e. my old 12" PowerBook plugged into the TV), although it didn't seem to like the fact the PowerBook went to sleep and eventually the file system got corrupted. I wrote a Perl script to recover files from an "unrecoverable" HFS+ filesystem (if anyone is interested I could clean up this code and post it) and got all the data back off it, reformatted it and attached it as an external disk to the Time Capsule.

And so it chugged on, occasionally having things dumped on it. Until last week, when I noticed that the Time Capsule seemed to be playing up, and the cause was apparently the external disk. I disconnected it and had a quick look with it plugged into my laptop and it seemed to be OK (although in retrospect I should maybe have done a bit more investigation that just looking to see if a directory listing showed there were files there).

Shortly afterwards I happened to be in Maplin and noticed they had a deal on Seagate GoFlex Desk 2TB External Drives, and so I got one of those, hoping I would be able to copy all the data off the failing 500GB drive before it lost the plot completely.

It turned out that although all the empty boxes in the shop proclaimed the drive was USB 2.0 and "upgradable to USB 3.0" (the GoFlex drives have swappable bases that allow you to choose different interfaces) that the drive I got already had a USB 3.0 adapter base. And so I ended up with my first USB 3.0 device, which by itself isn't particularly useful. However the supplied cable was perfectly adequate to connect the rather wacky USB 3.0 Micro-B socket on the HDD to the standard USB 2.0 A socket on the Time Capsule, and everything seemed to work fine. I kicked off an archive of the Time Capsule's internal disk and the next morning all my backups had been duplicated to the new disk.

So then I tried to recover the data from the failing 500GB drive. It turned out that it wasn't as happy as I'd originally thought. Although files would show up in Finder, if you actually tried to copy them off the drive the whole thing failed, making spin-up/spin-down noises and then disconnecting. I tried it through various interfaces (FireWire and USB), and also with the drive in various physical orientations (you never know). I even tried a different power supply in case the original one could no longer supply enough juice, but to no avail.

After I decided that there wasn't anything critical on the drive (mostly old TV shows I hadn't got round to watching) and that it was out of warranty, I thought I'd open it up. This was easier said than done. I eventually managed to lever the sides of the MyBook slightly open with a screwdriver and then open it like, well, a book, and get to the drive inside.

The MyBook is a sturdy well-constructed package, but once I got in I found there was a WD Caviar GP 3.5" SATA drive inside. Unfortunately I don't have a 3.5" SATA/USB enclosure. I probably should have guessed it was a SATA drive, as the MyBook has an eSATA connection as well as FireWire and USB. So I had a last ditch attempt at reviving it without it's case on, and even tried dropping the drive from about 6" onto my desk - just in case it helped. Then it dawned on my that the adapter for the GoFlex drive is just a SATA/USB3 bridge, so I removed the GoFlex drive from it's base, and then precariously balanced the bare WD drive on top of the adapter and proceeded to recover all my data from the WD drive.

This makes me think that the SATA/USB/FireWire bridge board in the MyBook enclosure is the component that is failing. Although it's not completely failed as it still talks to the disk to some extent. I find this slightly perplexing as I would have thought it was the component least likely to fail. Maybe some component on the board is undergoing heat failure.

Anyway, I offer this story up to the Internet in the hope that someone in a similar situation may be able to recover some important data that they thought was lost for ever, by using the power of the search engine, a screwdriver and a SATA adapter.

New Scientist: Enigma 45

This is the item published in the New Scientist #2853 Feedback section about my solution to Enigma Puzzle 45.

It only took 32 years to solve Enigma No 45. The version of the weekly New Scientist puzzle that was set in the issue of 3 January 1980 - a problem in linear algebra - was, it seemed, too difficult even for New Scientist's notoriously clever readers. The deadline for responses passed and, two weeks later on 17 January, Enigma's editor announced: "No correct solutions were received for Enigma No 45."

And that's how things stood until December 2011, when Jim Randell emailed New Scientist to say: "I was browsing through Google Books and I came across Enigma 45..." He promptly had a go at the puzzle himself and found "a solution that satisfies the conditions".

"What I'd like to know," said Jim, "is whether mine is the first correct solution you've received for this puzzle - albeit almost 32 years late."
We forwarded Jim's email on to the mathematical genius who regularly checks readers' solutions for Enigma puzzles.

He said that Jim had indeed got the answer right, and added that he had used "a reasonably straightforward computer program" to do the checking. "Presumably the reason no one got this answer 32 years ago," he surmised, "was because of the lack of computers then."

Our congratulations go to Jim Randell, who will be awarded an Enigma prize - at the 2012 rate, not the 1980 one. His solution to the puzzle is published in this week's Enigma on page 35.

And on page 35:

Answer to 45 Six squares - harder: P=434657, Q=420968, R=150568
The winner Jim Randell of Bristol, UK

Retrocomputing Enigma 45

A few months ago I launched Enigmatic Code - a place to post programmatic solutions to New Scientist's Enigma Puzzles.

As well as solving contemporary puzzles I found that Google Books has archives of back issues of New Scientist dating back to the 70's and 80's, and in my search for early Enigma puzzles I came across Enigma 45: Six squares - harder. Which involves finding non-negative integers P, Q, R such that P+Q, P+R, Q+R, P-Q, P-R and Q-R are all perfect squares.

After a couple of false starts - the solution clearly wasn't as small as I'd hoped - I came up with an algorithm to attack the problem in a reasonable amount of time.

However, when I checked my solution against the one published in the following issue of New Scientist I saw that the answer I had got wasn't the same as the solution they were expecting. But we had been asked to minimise the sum P+Q+R and my answer had a smaller sum than the published solution.

Curiously in New Scientist #1190 it is noted that no correct entries were received for this puzzle. "Shame on you!", they said. So I sent an email with my solution to ask if I was the first correct entry, albeit 32 years too late.

In the current issue of New Scientist (#2853) they published a short item in the Feedback section about this story, and they have awarded me a £15 prize for solving the puzzle!

If you're thinking it's a little unfair to unleash 2011 computing power on a 1980's problem, I decided to put a more contemporary machine up to the challenge. The BBC Micro was launched at the end of 1981 (although I don't think I would have been using them until probably '82 or '83), and I did quite a lot of programming on them at school, so I stood a fair chance of being able to get a program together to attack the problem.

So, I downloaded BeebEm3, and managed to get a BBC BASIC program together to solve the problem. The hardest part was trying to input the program, as the keymap of the emulator doesn't match the layout of my laptop keyboard. Nevertheless I managed to get my program typed in and running. (See image above).

It took about 40 minutes to run, and the Emulator said it was running at a speed of around 17, which I'm assuming means it's running at 17x the speed of a real BBC Micro. If so, that would mean that a contemporary-ish home computer could have solved the problem in under 12 hours (in BASIC!). Admittedly it's not up to the 255ms runtime of my present day Python solution, but it would be a bit of a poor reflection on 32 years of computing development if it was. (Note: I found that the TIME command reports the elapsed time as it would be on a real machine (presumably it's derived directly from the CPU clock), so I augmented the program to report elapsed timing and it seems the program would take 5h2m to find the smallest solution and and additional 2h17m to find the published solution on an actual BBC Micro).

Note: It turns out this problem was posed by Italian mathematician Pietro Mengoli in 1674, and the smallest solution was discovered by Euler a century later, probably without the benefit of even a BBC Micro.

Note: I've now received my physical copy of New Scientist #2853 and I've reproduced the article (and the illustration) on my own blog: New Scientist: Enigma 45.

A Variation on the West Mendip Way

Last year (2011) I walked various bits of The West Mendip Way, and this year (2012) I thought it would be nice to do the whole thing.

The walk goes from Wells Cathedral to Weston Bay at Uphill, just south of Weston-super-Mare. (Officially it goes the other way, but I think it might be more aesthetically pleasing to finish at the sea).

I've made some variations to the official route, these are:

1. Avoid dropping down to the road at Draycott, instead cut through Draycott Sleights Nature Reserve.
2. Walk along the cliff edge from Cheddar to Blackrock Gate.
3. Go along Velvet Bottom and up to Beacon Batch (the highest point in the Mendips), and then rejoin the official route at Rowberrow Warren. (Although an even further extension could be added here to take in Dolebury Warren).
4. A minor detour from the official route to visit the summit of Crook Peak.

Here's the route on Google Maps. This variation comes in at around 31 miles (50 km) (without going to Dolebury Warren). And it's bound to turn out a little longer in real life.

The route could be split into 3 stages of around 10 miles each:

1. Wells to Cheddar, 11 miles (17.4 km).
2. Cheddar to Winscombe Hill, 10 miles (15.8 km).
3. Winscombe Hill to Uphill, 10 miles (16.0 km).

My initial research (on Google Maps) indicates that it should be possible to get a bus between Wells and Cheddar (Tweentown) for Stage 1 (33 min), between Cheddar (Tweentown) and Winscombe Hill (17 min) for Stage 2 (or you could extend the walk by returning to Cheddar along the Strawberry Line).

The last stage is trickier, you would need to get a bus between Winscombe Hill and Weston-super-Mare, and then another one between Weston-super-Mare and Uphil (Beach End Road), which will take over an hour. It may be easier to arrange for someone to meet you at the beach for a celebratory ice-cream.

Or it could be done in 2 stages of around 16 miles each, by breaking the route at the summit of Beacon Batch. That way you get to do the highest point in the Mendips on both days.

1. Wells to Beacon Batch, 16 miles (25.8 km)
2. Beacon Batch to Uphill, 15 miles (23.4 km)

The car park at the top of Burrington Combe is handily only 1.3 km from Beacon Batch.

My plan is to do this when there is a fine spell of weather in the spring.

Enigmatic Python

While attempting to find a programmatic solution to Enigma 1602 (which really is much easier to do with pencil and paper) for the Enigmatic Code Blog, I briefly toyed with the idea of writing my own code to solve sets of linear simultaneous equations.

Then I discovered the rather marvellous SymPy library, which can do that and much more, and made for a very neat solution.

I've really only scratched the surface of this module, but I expect to use it more in the future.

Along with other Python modules that aid in the writing Enigma solutions: unlimited precision integers, set, itertools, collections, fractions, probably lots of other standard modules I have yet to discover, and, of course, my own set of useful routines.

And finally, to squeeze that bit extra out your Python programs you can always try using PyPy, which is a Python interpreter, written in Python. It includes a JIT compiler and often ends up running faster than the standard CPython interpreter.

I tried it on my code for Enigma 1653 - one of the trickier ones - and I got the following runtimes:

CPython 2.7.1: 2m01s
CPython 3.2: 1m52s
PyPy: 0m10s