2011-03-08

Project Euler problem 139 - Solved

Comments

The problem statement is located here.

I used the same technique as in problem 75 to generate all the primitive triplets below the given limit.

If the remainder of the hypotenuse divided by the difference of the catheti equals 0 then in all the deriving triangles based on that triple the property will hold true. To determine how many triangles derived from that triplet exists below the limit, we just divide the limit by the perimeter of the base triangle.

The code in python is problem139.py:

from itertools import takewhile, count
from fractions import gcd

LIMIT = 100000000

if __name__ == '__main__':
    result = 0
    generator = ((n, m) for n in count(3, 2) for m in range(1, n, 2) if gcd(m,n) == 1)
    for n, m in generator:
        a = m * n
        b = (n ** 2 - m ** 2) // 2
        c = (n ** 2 + m ** 2) // 2
        perimeter = a + b + c
        if perimeter > LIMIT and m == 1:
            break

        if c % (b - a) == 0:
            result += LIMIT // (a + b + c)
    print("The result is", result)
2011-03-07

Project Euler problem 75 - Solved

Comments

The statement for this problem is here.

The solution is quite easy once you know how to generate Pythagorean triplets efficiently. To achieve this you need to know about Euclid’s formula to generate primitive Pythagorean triplets.

Using that formula is easy to generate all the triplets, we continue to do so until we find a triplet whose m is 1 and the perimeter exceeds the LIMIT.

For each of the primitive triplets we generate all the derivative ones multiplying them with 1, 2, .., x until it the perimeter exceeds the LIMIT.

With each of the perimeters generated I add them to a set and if found on that set, add them to another.

When all the generation is finished, the result is the elements in the difference between the first and the latter sets.

The solution in python is problem075.py:

rom itertools import takewhile, count
from fractions import gcd

LIMIT = 1500000

if __name__ == '__main__':
    found_per = set()
    rep_per = set()
    generator = ((n, m) for n in count(3, 2) for m in range(1, n, 2) if gcd(m,n) == 1)
    for n, m in generator:
        a = m * n
        b = (n ** 2 - m ** 2) // 2
        c = (n ** 2 + m ** 2) // 2
        perimeter = a + b + c
        if m == 1 and perimeter > LIMIT:
            break

        for per in takewhile(lambda x: x <= LIMIT, (perimeter * i for i in count(1))):
            if per in found_per:
                rep_per.add(per)
            else:
                found_per.add(per)

    print("The result is", len(found_per - rep_per))
2011-03-03

Project Euler problem 303 - Solved

Comments

The statement for this problem can be found here.

In order to solve this problem in a reasonable time you should:

  • Never repeat cases that will yield the same results.
  • The first solution that fits is the correct one.
  • Efficiently advance through the quest.

Let’s take each point separately.

Not repeating cases

To achieve this is important to notice that whenever you are multiplying 2 numbers the leftmost numbers of the results will only be affected by the n leftmost digits of the second argument where n equals to the number of digits of the first number plus 1.

So we should be collecting those digits, and before processing a possible multiplicand we check that its first n digits were not previously processed.

The first solution that fits is the correct one

This condition implies that the possible answers are processed in increasing order independently of how they are generated.

I made it possible by storing the possible answers in a min-heap, sorted by the length of the multiplier and then for the digits of the multiplier.

In each iteration I pop the first element, check if that is the solution and then if its not I push each of the possible solutions that can be diverted from that multiplier.

Efficiently advance through the quest

All the cases that are processed are based on previous possible solutions. Doing the multiplication each time is expensive. To gain processing time, I store in the tuple that goes into the min-heap the result of the multiplication for that multiplier.

When its processed and it is not the answer, instead of calculating each multiplication for the deriving cases I just add to the current multiplication the new digit * number being process * 10 ** (size of current multiplier - 1) which is a lot less expensive.

Final Solution

Putting together everything, I coded a Python program that solves the problem, the file is problem303.py:

import heapq

LIMIT = 10000

mult_digit = {}
for i in range(10):
    mult_digit[i] = {}
    for j in range(10):
        if (i * j) % 10 not in mult_digit[i]:
            mult_digit[i][(i * j) % 10] = []
        mult_digit[i][(i * j) % 10].append(j)

def find_mult(i):
    str_i = str(i)
    heap = []
    for r in range(3):
        heap.extend((2, [j], i * j) for j in mult_digit[int(str_i[-1])].get(r, []))
    heapq.heapify(heap)
    used_set = set()
    while True:
        next_affected, list_n, parcial_mult = heapq.heappop(heap)

        if list_n[0] != 0 and max(str(parcial_mult)) < '3':
            return int(''.join(map(str, list_n)))

        if tuple(list_n[:len(str_i)+1]) in used_set:
            continue
        used_set.add(tuple(list_n[:len(str_i)+1]))

        str_parcial_mult = str(parcial_mult)
        try:
            s = int(str_parcial_mult[-next_affected])
        except IndexError:
            s = 0
        for d in range(3):
            d -= s
            d %= 10
            for mult in mult_digit[int(str_i[-1])].get(d, []):
                new_list_n = [mult] + list_n
                heapq.heappush(heap, (next_affected + 1, new_list_n, parcial_mult + mult * i * (10 ** (next_affected - 1))))

if __name__ == '__main__':
    result = sum(find_mult(i) for i in range(1, LIMIT + 1))
    print("The result is:", result)