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 d

_{1}be the 1st digit, d_{2}be the 2nd digit, and so on. In this way, we note the following:d

_{2}d_{3}d_{4}=406 is divisible by 2

d_{3}d_{4}d_{5}=063 is divisible by 3

d_{4}d_{5}d_{6}=635 is divisible by 5

d_{5}d_{6}d_{7}=357 is divisible by 7

d_{6}d_{7}d_{8}=572 is divisible by 11

d_{7}d_{8}d_{9}=728 is divisible by 13

d_{8}d_{9}d_{10}=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