Obfuscate Penguin

While googling for GNOME Games on Windows (yes; I’m aware of the contrariness), I had to detour slightly to find out how A computer without Windows is like a dog… ended.  The answer, revealed as the tagline to blog Turing Uncomplete, was without bricks tied to its head. Anyway, Euler in a post title there again ruthlessly grabbed my highly distractible mind.

Project Euler is a set of mathematical challenges that a well-written program running on a modest computer should be able to solve in under a minute, which I thought might be interesting to pass a little time with every now and again.  The first problem was, unsurprisingly, exceptionally simple, requiring just 5 short lines of Python to solve.  So I skipped down the list a little to the first problem with fewer than 3000 solutions so far: problem 43.

From the problem page:

The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility property.

Let d₁ be the 1^st digit, d₂ be the 2^nd digit, and so on. In this way, we note the following:

• d₂d₃d₄=406 is divisible by 2
• d₃d₄d₅=063 is divisible by 3
• d₄d₅d₆=635 is divisible by 5
• d₅d₆d₇=357 is divisible by 7
• d₆d₇d₈=572 is divisible by 11
• d₇d₈d₉=728 is divisible by 13
• d₈d₉d₁₀=289 is divisible by 17

Find the sum of all 0 to 9 pandigital numbers with this property.

A friend had previously challenged me with another pandigital number problem so I dug out the code I wrote for that (in Perl) and modified it (in Python).  This was the result:


# A script to solve Problem 43 at Project Euler
# http://projecteuler.net/index.php?section=problems&id=43
# by, and copyright ©2008, Marc Stewart
# http://www.obfuscatepenguin.net/
#
# =====================================================================
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program. If not, see http://www.gnu.org/licenses/.
#
# =====================================================================
#
# Start with the digits 1 to 9, and alternate between sequences from previous and current iteration
sequences_a = range(1, 10)
sequences_b = []
sequences = [sequences_a, sequences_b]
#
# List prime divisors
primes = [2, 3, 5, 7, 11, 13, 17]
#
# Create new sequences 2 to 10 digits long
for i in range(2, 11):
#
# Examine each sequence from the last set (initially 1 to 9)
for prev_seq in sequences[i % 2]:
#
# For each possible next digit...
for next_digit in range(0, 10):
#
# ... check it isn't in the sequence already
if (str(prev_seq).find(str(next_digit)) == -1):
#
# If not, add to end of the sequence
new_seq = prev_seq * 10 + next_digit
#
# Check divisibility by prime if sequence at least 4 digits long
if (i < 4) or (int(str(new_seq)[(i - 3):]) % primes[i - 4] == 0):
#
# Add any valid longer sequences to the next sequence set
sequences[(i + 1) % 2].append(new_seq)
#
#print str(i) + "-digits: " + str(new_seq)
#
# Erase last sequence set, ready for next iteration
sequences[i % 2] = []
#
# Now add up the valid 10-digit pandigitals...
sum = 0
#
for each_seq in sequences[1]:
#
sum = sum + each_seq
#
# ... and print the result
print sum


Without all the comments, that’s quite a neat little 16-line script, which I was rather pleased with, but it turns out that, in Ruby, the same task can be programmed in less than half that.  Even if it’s not particularly well optimised for speed, it’s brought me one step closer to learning the language—I wonder what will finally get me to do so.

Monday, 18^th August 2008 03:43:25 UTC