# HackerRank ‘Journey To The Moon’ Solution

H
##### Short Problem Definition:

The member states of the UN are planning to send 2 people to the moon. They want them to be from different countries. You will be given a list of pairs of astronaut ID’s. Each pair is made of astronauts from the same country. Determine how many pairs of astronauts from different countries they can choose from.

Journey To The Moon

##### Complexity:

time complexity is O(a(N))

space complexity is O(N)

##### Execution:

The algorithm has two parts. Part one calculates the size of all countries with the use of Union-Find. Both operations on the data structure take O log-star time. The second part derives the number of all pairs based on country sizes. That algorithm is very similar to Handshakes.

I used the UF implementation from ActiveState. For more cool uses of Union-Find, see WireBurnouts.

##### Solution:
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 `#!/bin/python`   `import` `math` `import` `os` `import` `random` `import` `re` `import` `sys` `from` `collections ``import` `defaultdict`   `class` `UnionFind:` `'''http://code.activestate.com/recipes/215912-union-find-data-structure/'''` `    ``def` `__init__(``self``):` `        ``self``.num_weights ``=` `{}` `        ``self``.parent_pointers ``=` `{}` `        ``self``.num_to_objects ``=` `{}` `        ``self``.objects_to_num ``=` `{}` `        ``self``.__repr__ ``=` `self``.__str__`   `    ``def` `insert_objects(``self``, objects):` `        ``for` `object` `in` `objects:` `            ``self``.find(``object``);`   `    ``def` `find(``self``, ``object``):` `        ``if` `not` `object` `in` `self``.objects_to_num:` `            ``obj_num ``=` `len``(``self``.objects_to_num)` `            ``self``.num_weights[obj_num] ``=` `1` `            ``self``.objects_to_num[``object``] ``=` `obj_num` `            ``self``.num_to_objects[obj_num] ``=` `object` `            ``self``.parent_pointers[obj_num] ``=` `obj_num` `            ``return` `object` `        ``stk ``=` `[``self``.objects_to_num[``object``]]` `        ``par ``=` `self``.parent_pointers[stk[``-``1``]]` `        ``while` `par !``=` `stk[``-``1``]:` `            ``stk.append(par)` `            ``par ``=` `self``.parent_pointers[par]` `        ``for` `i ``in` `stk:` `            ``self``.parent_pointers[i] ``=` `par` `        ``return` `self``.num_to_objects[par]`   `    ``def` `union(``self``, object1, object2):` `        ``o1p ``=` `self``.find(object1)` `        ``o2p ``=` `self``.find(object2)` `        ``if` `o1p !``=` `o2p:` `            ``on1 ``=` `self``.objects_to_num[o1p]` `            ``on2 ``=` `self``.objects_to_num[o2p]` `            ``w1 ``=` `self``.num_weights[on1]` `            ``w2 ``=` `self``.num_weights[on2]` `            ``if` `w1 < w2:` `                ``o1p, o2p, on1, on2, w1, w2 ``=` `o2p, o1p, on2, on1, w2, w1` `            ``self``.num_weights[on1] ``=` `w1``+``w2` `            ``del` `self``.num_weights[on2]` `            ``self``.parent_pointers[on2] ``=` `on1`   `# Complete the journeyToMoon function below.` `def` `journeyToMoon(n, astronauts):` `    ``# generate disjoint sets` `    ``uf ``=` `UnionFind()` `    ``uf.insert_objects(``xrange``(n))`   `    ``for` `astronaut ``in` `astronauts:` `        ``uf.union(astronaut[``0``], astronaut[``1``])`   `    ``# calculate sizes of countries` `    ``country_sizes ``=` `defaultdict(``int``)` `    ``for` `i ``in` `xrange``(n):` `        ``country_sizes[uf.find(i)] ``+``=` `1`   `    ``# calculate number of viable pairs` `    ``sm ``=` `0` `    ``result ``=` `0` `    ``for` `size ``in` `country_sizes.values():` `        ``result ``+``=` `sm``*``size;` `        ``sm ``+``=` `size; `   `    ``return` `result`   `if` `__name__ ``=``=` `'__main__'``:` `    ``fptr ``=` `open``(os.environ[``'OUTPUT_PATH'``], ``'w'``)`   `    ``np ``=` `raw_input``().split()`   `    ``n ``=` `int``(np[``0``])`   `    ``p ``=` `int``(np[``1``])`   `    ``astronaut ``=` `[]`   `    ``for` `_ ``in` `xrange``(p):` `        ``astronaut.append(``map``(``int``, ``raw_input``().rstrip().split()))`   `    ``result ``=` `journeyToMoon(n, astronaut)`   `    ``fptr.write(``str``(result) ``+` `'n'``)`   `    ``fptr.close()`