Project Euler Problem 186 - Solved

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)