Journey to the moon
It has been so long since I wrote an article! Probably around 10 years, a remarkable period full of void and nothingness! For the first post in my new blog I decided to pick a subject that always fascinated me, despite its apparent simplicity and “stapleness” in a developer’s toolbox. I am talking about graph theory! Yes, that very boring class you took ages ago, that one you always suspected was stolen from the mathematicians and shoved down your throat because y’know… someone said graphs are kinda important and blah blah blah
Well, brace yourselves because I’m going to propose a quite trivial solution to this HackerRank problem, named “Journey to the moon”. As experience tells us, computer scientists are always there when some self-important manager screws up with documents and forgets papers about astronauts’ nationalities. That’s serious business. Take your time to read the problem carefully and meet me here in 5 minutes.
Done? Great! So, there are surely several trivial solutions to the problem; however the best in my opinion is based on a kind of data structured called union/find forests or disjoint sets. They came to my mind right away because this problem basically is yelling their name out load: it’s the most flamboyant and immediate application of disjoint sets, since we are required to answer the query “do these elements belong to the same set?” in a very short time. Union/find forests support the following operations:
- create a new tree;
- merge two trees;
- find the tree containing a given element.
In principle, both find and merge have a worst-case time complexity O(n). However, with some smart optimizations, namely path compression and union by rank, they can be reduced to O(α(n)). Since α is an extremely slowly increasing function - the inverse of the exploding Ackermann function - the final average case amortized time complexity is reduced to O(1) for any possible value of n that can be valid in the physical universe. Pretty cool huh?
The basic idea behind my solution is simple. Each astronaut will be a vertex in the forest. When we get a pair of astronauts, we know that they belong to the same country, therefore we can add an edge between their vertices and join the trees they belong to. Thus a tree in the forest will represent all astronauts from the same country. By counting the number of disjoint trees and their size we get the exact subdivision of all our participants! From that it’s trivial to compute the total amount of possible combinations.
Before proposing the (hurried and quite messy) implementation that I used to solve the problem, I’d like to point out a rather important fact that is essential to reach a correct solution. Look at the second example. They motivate their own answer with the following sentence:
Persons numbered 0 and 2 belong to the same country, and persons 1 and 3 don’t share countries with anyone else, so they belong to unique countries on their own.
I highlighted the logical connection between the two statements because it contains some core information. It tells us that all astronauts that do not appear in the given dataset belong to their own country. This is a direct consequence of the premises fixed in the prologue but it is nonetheless quite easy to miss. In fact we are allowed to make such an assumption:
Assume that you are provided enough pairs to let you identify the groups of astronauts even though you might not know their country directly.
Now it’s time to code!