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: 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. Well 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

Enigmatic Code

For the past few years I've been treating the weekly Enigma puzzles in New Scientist magazine as a programming challenge. I started writing programs to solve the puzzles in Perl (and occasionally C, when speed was all important), but more recently I've been coding up solutions in Python.

Now, I've decided to set up a blog to share programmatic solutions to Enigma puzzles. I opted for a WordPress blog, as I couldn't get Blogger comments to accept pre-formatted code. Whereas WordPress comments let you use HTML <pre> tags.

I aim to add new puzzles (and solutions) as they are published (usually on a Thursday in the UK), and also retroactively add old puzzles that I have coded solutions for, or found from the New Scientist archives on Google Books, as time allows.

If you'd like to join in, please visit the Enigmatic Code blog.

Dice Emulator

The Merry Game of Floundering

The other day Caroline came home with a charity shop find - The Merry Game of Floundering* - which I'm sure we used to play as kids (although my Mum claims never to have heard of it).

All the pieces were there with the exception of one of the dice (it needs to two). So rather than search for another die I did what any self-respecting programmer would do, and knocked up a dice emulator in Python.

Thanks to the pygame library and Unicode characters U+2680 - U+2685 I was able to get a program together quickly which we then triggered using the Apple Remote (using Remote Buddy's Virtual Mouse behaviour). Simple as that!

dice.py

The program is presented below. Be aware, though, it makes some assumptions about running on my MacBook. If you're running it on non-1280x800 screen size you'll probably need to change the font sizes, and if you're running on a non-Apple system you'll probably need to change the font for the die characters (or go back to using ASCII numbers, as it was originally), and the location of the sound that is played when the dice is rolled. Also there is some code there to highlight special scores (doubles, and 6 and 1), which are specific to the Floundering game - take them out, or define your own. Enjoy!

• Download dice.py

[*] While searching for more information on the game I found someone selling a set on eBay as "The Messy Game of Floundering".

Gotta Catch 'Em All

"Fade to Black"

From 6th July 2011 to 7th September 2011 there are 60 decorated gorilla statues roaming the (mostly) Bristol area. (See the Wow! Gorillas page for for details).

We're now half way through their visit and I've managed to collect 53 out of 60. You can see my efforts in my Facebook photo gallery. (Facebook registration not required).

So I'm missing 7:

• Gorilla 5 ("Sky Gorilla"), Anchor Square, Bristol Harbour.
• Gorilla 9 ("Willard"), A Marriott Hotel Lobby, Bristol.
• Gorilla 25 ("Elvis"), Bristol Bus Station.
• Gorilla 26 ("Hubert"), Holiday Inn, Bristol.
• Gorilla 29 ("Ape Scape"), Bristol Airport.
• Gorilla 40 ("Winston"), Avon Gorge Hotel, Bristol.
• Gorilla 60 ("Guerilla Tourist"), Birmingham(!) Coach Station.

I missed #5 on my visit to Bristol Harbour - I think it must have been obscured by a fairground ride that was there.

I foolishly thought that the Marriott Hotel City Centre would be the one by The Centre, but it turns out that that's the Marriott Royal Hotel, and the City Centre one is at Broadmead (I suppose that's "City Centre" when compared to Bristol Airport or somewhere). So I ended up at the wrong hotel. (Although #9 is in the Broadmead one from today).

I don't usually happen to pass through Bristol Airport on my day-to-day travels, but I might be able to get out there sometime in the next month to collect #29.

But Birmingham seems a bit of a way to go. Although I know the closer I get to completing the set the more I will feel compelled to make a trip up to Brum.

But there maybe a solution. Apparently Gorilla #61 ("Doris") is currently floating around Bristol Harbour on the prow of The Matthew, and was organised too late to make it on to the official maps. So there may be hope of sneakily collecting 60 Gorillas after all.

Update 2011-09-04: I'm now on 59/61 - only #29 and #60 to get!

Update 2011-09-06: I went to Bristol Airport and collected #29 today. 60/61.

Update 2011-09-25: I finally collected "Guerilla Tourist" today, now that he's outside Bristol Zoo and no longer in Birmingham. 61/61.