Project Euler Problem 186 - Solved
Solution to ProjectEuler's problem 186 in Python using a generator function and efficient group inclusion search
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
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)
Comments powered by Talkyard.