2011-03-22

Project Euler problem 329 - Solved

Comments

You can find the statement of this problem here.

The solution to this problem is really an easy one. It’s just straightforward dynamic programming.

The DP approach I used is top-down with memoization. The DP dictionary will be indexed by a 2-tuple of the starting cell and the string of the expected sequence. And it’s initialized for all the numbers for the strings ‘N’ and ‘P’.

The function which calculates the probability of a sequence from a determined cell first checks if it’s already in the DP dictionary, if it’s not there are three cases:

  1. The cell is number 1: in that case the probability of the sequence is the probability of hearing the first letter of the string in that position multiplied by listening the rest of the string from cell 2.
  2. The cell is number 500: in that case the probability of the sequence is the probability of hearing the first letter of the string in that position multiplied by listening the rest of the string from cell 499.
  3. Rest of the cells: the probability of listening a sequence is: the probability of hearing the first letter of the string in that position multiplied by (p + q) where p stands for the probability of listening to the rest of the string from the previous cell divided by 2 (the probability of choosing the previous cell is 0.5) and q stands for the probability of listening to the rest of the string from the next cell divided by 2 (the probability of choosing the next cell is 0.5).

The result is the sum of the probability of listening to the sequence from each cell and then divided by 500. There’s a probability of 1/500 to start in each cell.

The python code is available problem329.py:

from CommonFunctions import find_primes_less_than
from fractions import Fraction

d = {}

primes = set(find_primes_less_than(501))
for i in range(1, 501):
    if i in primes:
        d[(i, 'P')] = Fraction(2, 3)
        d[(i, 'N')] = Fraction(1, 3)
    else:
        d[(i, 'P')] = Fraction(1, 3)
        d[(i, 'N')] = Fraction(2, 3)

def calc_prob(i, string):
    if (i, string) in d:
        return d[(i, string)]

    if (i == 1):
        prob = d[(i, string[0])] * calc_prob(i + 1, string[1:])
    elif (i == 500):
        prob = d[(i, string[0])] * calc_prob(i - 1, string[1:])
    else:
        prob = d[(i, string[0])] * (calc_prob(i + 1, string[1:]) * Fraction(1, 2) + calc_prob(i - 1, string[1:]) * Fraction(1, 2))

    d[(i, string)] = prob
    return prob

if __name__ == '__main__':
 result = Fraction(0, 1)
 for i in range(1, 501):
  result += calc_prob(i, 'PPPPNNPPPNPPNPN')
 print("The result is:", result / 500)
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)