Prim and Proper…

So HackerRank ‘tricked’ me with an email, and I ended up gettung into their algorithm section before I felt I was ready for it. (Keep in mind, this was not a mean trick, or something dishonest or shady on their part – they just sent an email that said ‘You should try our Algorithm domain’, and like a dummy, I did.)

So to get the first badge under Algorithms, I had to complete something on graph theory (which I haven’t gone over since high school geometry – 30-ish years ago), and in a new language (python)… but I’m nothing if not dedicated, so I take the plunge and give it a try…

Here is the problem I had to work on:

Given a graph which consists of several edges connecting the nodes in it. It is required to find a subgraph of the given graph with the following properties:

  • The subgraph contains all the nodes present in the original graph.
  • The subgraph is of minimum overall weight (sum of all edges) among all such subgraphs.
  • It is also required that there is exactly one, exclusive path between any two nodes of the subgraph.

One specific node is fixed as the starting point of finding the subgraph. Find the total weight of such a subgraph (sum of all edges in the subgraph)

So, given that, I came up with a basic solution… First Solution and the thing about this is that it worked. The catch was for a test case that had 10000 vertices, it took almost 3 minutes to run, so the test case timed out, and it failed me!! 🙁

So, cracking my knuckles, and rising to the challenge, I employed my google-fu and began to track down some more efficient solutions. Since this discussed Prim in the title, I researched Prim and MST’s and came up with this algorithm to do this calculation, and after some more searching found a python version. After reviewing, I noticed that it wasn’t all that different from my solution, just that it used some python imports that I didn’t know about (mainly heapq and using dictionaries from collections) – apparently using the dictionary stuff from collections speeds that process up, and heapq speeds vertex jumping up significantly… my new solution basically did the same thing, but much more efficiently. Thus solving the problem in a few seconds.

What I take from this is that my original solution was right (and it worked, just not as efficient), and the only real changes the new solution made were to use python modules that were basically unknown to me to make what I was doing more efficient.

So all in all, I’m happy with the results.

I got me 3rd Percentile algorithm (which I’ve since increased to the 4th Percentile) – so I’ve got a ways to go in the Algorithms domain. But I’m going back to the python domain to finish it before i wander off into any of the other domains!

Under Pressure – David Bowie & Queen
Never B Flat, Sometimes B Sharp, Always B Natural