2011-03-17

Project Euler problem 186 - Solved

Comments

The statement for this problem can be found here.

The solution of this problem is quite straightforward. I will use a list which will hold sets, each of them will represent the nodes in a connected graph.

First of all a generator is needed in order to produce the caller and receiver of each phone call. For that I use a generator function implemented with the yield instruction.

The next thing to keep in mind is that once you know the caller and receiver, how can you efficiently find in which connected graphs are they in. To accomplish this, the set’s list will hold for position i the set where i is in or the position where it was moved to. If a number was moved several times you need to follow the chain of indexes until you find a set.

Having mentioned the two key techniques used it is easy to code the program that solves the problem. “While the connected graph that the president is in is less than 990000(99%): get the next phone call, find the graphs of each of the participants, if they differ then join both sets in one and in the other’s position set the corresponding reference.”

The python code is problem186.py:

from collections import deque

def generator():
    queue_55 = deque()
    queue_24 = deque()
    for k in range(1, 56):
        s_k = (100003 - 200003 * k + 300007 * (k ** 3)) % 1000000
        queue_55.append(s_k)
        if k >= 32:
            queue_24.append(s_k) 
        yield s_k
    while True:
        s_k = (queue_55.popleft() + queue_24.popleft()) % 1000000
        queue_55.append(s_k)
        queue_24.append(s_k) 
        yield s_k

graph_list = [set([i]) for i in range(1000000)]

def get_pos_of(i):
    while isinstance(graph_list[i], int):
        i = graph_list[i]
    return i

if __name__ == '__main__':
    gen = generator()
    res = 0
    while len(graph_list[get_pos_of(524287)]) < 990000:
        c1 = next(gen)
        c2 = next(gen)
        if c1 == c2:
            continue
        res += 1
        i1 = get_pos_of(c1)
        i2 = get_pos_of(c2)
        if i1 != i2:
            to_put_into = min(i1, i2)
            to_remove = max(i1, i2)
            graph_list[to_put_into] |= (graph_list[to_remove])
            graph_list[to_remove] = to_put_into        
    print("The result is:", res)
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))