Sunday, April 8, 2012

Project Euler 33

Problem 33 of project euler is a problem that concerns it's self with odd ways of canceling fractions. The example they give is 49/98. If you 'cancel' the 9s you will still get the same number: 4/8 = 49/98. So basically we want to see, first if there is a digit that appears in both the numerator and the denominator. I decided to do this in python like so:
#a, the numerator, b the denominator.
def curious(a,b):
    try:
        c = float(a)/b
        if a/10 == b/10: #(4)9 & (9)8
            if float(a%10)/(b%10) == c:
                return 1
        if a/10 == b%10: #(4)9 & 9(8)
            if float(a%10)/(b/10) == c:
                return 1
        if a%10 == b/10: #4(9) & (9)8
            if float(a/10)/(b%10) == c:
                return 1
        if a%10 == b%10: #4(9) & 9(8)
            if float(a/10)/(b/10) == c:
                return 1
    except: #handles cases where b%10 results in 0
        return 0
    return 0
So hopefully either you know the modular arithmetic or it is clear from context, but basically taking any number %10 will knock off everything but the single digit (11%10 -> 1, 72%10 -> 2, 89%10 -> 9, etc). The second potentially confusing part of the 'curious' function is integer division. Basically this is division where you simply never keep track of anything below a whole number (21/10 -> 2, 53/10 -> 5, etc). This way given any pair of two digits numbers I try every combination where they could have two of the same digits. Then I check to see if the other two digits, the ones that would be remaining if the co-occurring digits were removed equal the original fraction. For example I take in 49 and 98 The third if statement would be triggered and 4/8 would be checked against 49/98. They would have the same result and the function would return 1. So now all we need to do is filter out all of the times that the numbers are both multiple of tens and find all of the fractions that are 'curious'.
list = []            
for a in range(10,99):
    for b in range(a + 1,99):
        if curious(a,b):
            if a%10 and b%10:
                 list.append(reduce_fract(a,b))
This code works because for any number like 30 (a multiple of 10) is a or b then 30%10 will equal 0. 0 is always evaluated to mean False so the if statement is never triggered when either of the numbers are divisable by ten. This removes all of the numbers that are not needed by the problem. Now all we have to do is complete the final piece of the puzzle. They want the product of the four fractions that are 'curious' in their lowest common terms. So we will need to write a function that reduces fractions to their lowest common terms. We can do that by iterating over every number from 2 to the numerator and whenever both of the numbers are divisible by that number we simply divide them both and them keep on checking every digit. This function is as follows:
def reduce_fract(a,b):
    for i in range(2,a + 1):
        if a%i == 0 and b%i == 0:
            a /= i
            b /= i
            return reduce_fract(a,b)
    return (a,b)
So putting it all together we get a run time of just 0.019 seconds, no need to even attempt to optimize this code anymore so here is my first attempt at solving this problem.
def curious(a,b):
    try:
        c = float(a)/b
        if a/10 == b/10:
            if float(a%10)/(b%10) == c:
                return 1
        if a/10 == b%10:
            if float(a%10)/(b/10) == c:
                return 1
        if a%10 == b/10:
            if float(a/10)/(b%10) == c:
                return 1
        if a%10 == b%10:
            if float(a/10)/(b/10) == c:
                return 1
    except:
        return 0
    return 0

def reduce_fract(a,b):
    for i in range(2,a + 1):
        if a%i == 0 and b%i == 0:
            a /= i
            b /= i
            return reduce_fract(a,b)
    return (a,b)

list = []            
for a in range(10,99):
    for b in range(a + 1,99):
        if curious(a,b):
            if a%10 and b%10:
                 list.append(reduce_fract(a,b))

print list
print reduce_fract(reduce(lambda x,y: x*y,map(lambda x: x[0], list)),reduce(lambda x,y: x*y,map(lambda x: x[1], list)))
The last line of this map be a little confusing. Each of the reduce statements's functions are simply multiplying the numerators and denominators together using both lambda calculus and reduce. If you do not understand how these work don't worry too much about them for now. I will be describing them more in depth in a future blog post.

Monday, April 2, 2012

Project Euler 43

Problem 43 of project euler is a strange problem, at least in my eyes. First off it starts talking about pandigital numbers. Pan, of course, means across so we can think of it as across digit numbers, which they define as a number that contains every digit (0-9) once and only once. Given that there are 10 digits here and any permutation of them would be a pandigital number there are 10! (thats 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1) different combinations, about 3 million.

So that is the size of our search space, not incredibly large, but the problem gets trickier. They only want pandigitals which small portions of are divisible by prime numbers. I believe that their example makes it clear exactly what they want.

Take the pandigital 1406357289. Then lets look at a small section of it 3 digits at a time:


  • 1406357289 is divisible by 2
  • 1406357289 is divisible by 3
  • 1406357289 is divisible by 5
  • 1406357289 is divisible by 7
  • 1406357289 is divisible by 11
  • 1406357289 is divisible by 13
  • 1406357289 is divisible by 17
So its clear that this will yield a great deal fewer numbers than 3 million.

So as usual I coded a naive approach to see how it performs and to make sure I can answer the question. I implemented a function that takes in a 10 digit number and checks to see if the digits in index 2 through 4 are divisible by 2, then the digits 3 through 5 are divisible by 3 then.... etc
. Then I simply generated every single permutation of the digits 0-9 and threw away any that did not pass the function, from there you can simply sum up all of the remaining ones and you have your answer.
Hopefully the python makes this clear.


from itertools import permutations

def wtf_problem_43(number):
    primes = [2,3,5,7,11,13,17]
    for i in range(len(primes)):
        if int(number[1 + i:4 + i])%primes[i] != 0:
            return False
    return True

print sum(map(int,filter(wtf_problem_43,map(''.join,permutations("1234568790")))))


This code does indeed work, but it takes 47.6 seconds to execute. Surely we can do better!


First off there is no need to generate every permutation of the digits 0-9. Surely we can cut a large amount of those out of the search space very quickly. Right off the bat what we could do is simply focus on generating only a 3 digit chunk that is divisible by its relevant prime number. It would be like instead of generating 1406357289 we only generate 406, because it is divisible by 2. Then we would only need to try every remaining number (1,2,3,5,7,8,9) in the last slot of 06_ and see if it is divisible by 3.


This turns the problem into a constraint satisfaction problem (sudoku is a famous CSP) and a nice trick for solving these very quickly is to first make choices where it cuts out the large number of potentials. For instance there are 360 diffent ways to start if we start with the ones divisible by 2, but if we start backwards, with different ways to make numbers that are divisible by 17 we only have 44 of them.

So I created a recursive generator that will yield all of the relevant numbers.

This code is significantly more complex, I left some comments, but recursive generators are a little hard to understand. I personally recommend adding the decorator that prints out the arguments that a function gets when it is called. (add this by putting @dump_args before the function declaration).

from itertools import permutations

def generator(divisors,remaining, previous=""):
    if divisors: #if divisors is empty, then only one digit remains
        if previous == "": #This iteration is the starting iteration, it simply recalls its self with every permutation of the last two digits
            for permutation in permutations(remaining,2):
                permutation = ''.join(permutation) #('1','2') -> "12"
                for i in generator(divisors,remaining.translate(None,permutation),permutation):
     #translate strips the used digits, ensuring pandigitality
                    yield i + permutation
        else:
            for permutation in permutations(remaining,1): #unnecessarily complex, I just wanted it to look consistent
                permutation = ''.join(permutation) + previous[:2]
                if int(permutation)%divisors[0] == 0:#
                    for i in generator(divisors[1:],remaining.translate(None,permutation),permutation):
                        yield i + permutation[0]
    else:
        yield remaining

            
print sum(map(int,generator([17,13,11,7,5,3,2],"1234568790")))
Even though this code could still be speed up it solves the problem in just 0.008 seconds! Again, if after looking at the code with the dump_args decorator you still do not understand it, please leave me a comment.