This is a small post to prepare for the google code jam and the small data set. Some coding questions can be solved (in short time) by iterating over all variants. I solved some problems of project euler with the python itertools.
Coding fast and solve it with the brute force variant.
The method permutations gegerate all variants of a given iterable (or a limited subset).
from itertools import permutations
print permutations('ABCD', 2)
#will produce: AB AC AD BA BC BD CA CB CD DA DB DC
Problem 41
Problem description from project euler:
We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once. For example, 2143 is a 4-digit pandigital and is also prime.
What is the largest n-digit pandigital prime that exists?
And with itertools (and a pre-coded isPrim-function) the solution is easy. I start with n=10 digits and search the biggest pandigital.
import itertools
m = 0
n = 10
while m==0:
#generate all iteration from digits 1..n (starting with 1..9)
for variant in itertools.permutations(range(1,n)):
#calculate from list the decimal number t
t = reduce(lambda a,b: a*10+b, variant)
#search the maximum number (if prim)
m = isPrim(t) and max(t,m) or m
n -= 1
return m
Ok, I could start with n=7 digits …
Problem 43
Problem description from project euler:
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 d1 be the 1st digit, d2 be the 2nd digit, and so on. In this way, we note the following:
d2d3d4=406 is divisible by 2
d3d4d5=063 is divisible by 3
d4d5d6=635 is divisible by 5
d5d6d7=357 is divisible by 7
d6d7d8=572 is divisible by 11
d7d8d9=728 is divisible by 13
d8d9d10=289 is divisible by 17Find the sum of all 0 to 9 pandigital numbers with this property.
Ok, let’s generate all combinations of the 10 digits and test the conditions directly. I shortend only the division by 2 and 5 …
import itertools
s = 0
for v in itertools.permutations(range(10)):
if ( v[3] % 2 == 0 and
(v[2]*100+v[3]*10+v[4]) % 3 == 0 and
v[5] % 5 == 0 and
(v[4]*100+v[5]*10+v[6]) % 7 == 0 and
(v[5]*100+v[6]*10+v[7]) %11 == 0 and
(v[6]*100+v[7]*10+v[8]) %13 == 0 and
(v[7]*100+v[8]*10+v[9]) %17 == 0 ):
s += int("".join([str(x) for x in v]))
return s
And here is my more indirect and pythonic version (but it’s not faster):
import itertools
s = 0
for v in itertools.permutations(range(10)):
if v[5]==0 or v[5]==5 and v[3]%2==0: # optimze the division by 2/5
hit = True
for n, p in enumerate([2, 3, 5, 7, 11, 13, 17]):
hit = hit and (v[n+1]*100+v[n+2]*10+v[n+3])%p==0
if hit:
s += reduce(lambda a,b: a*10+b, v)
return s
This brute force method can be coded in short time, a better solution will use the problem conditions and decrease the count of permutations. In the euler project forums exists a paper-variant of solving this problem.
Links for permutations
- Fine article on wikipedia to generate permutations
- java code examples on stackoverflow.com
- official documentation of python itertools with the permutations method
Christian Harms
Latest posts by Christian Harms (see all)
- google code jam 2013 – tic-tac-toe-Tomek solution - April 16, 2013
- Google code jam 2013 – the lawnmower - April 14, 2013
- code puzzles and permutations - April 11, 2013