RPCFN#3 Short-circuit
It was great to see so many solutions for the problem statement I had set. After an initial ‘shock’ from all electrical engineers, the problem was clearly understood as a variant of the ‘shortest path algorithm’. I hope I was able to derive a laugh from the cryptic clue ‘short-circuit’.
Speaking of ‘derive’, I did see most solutions going into a class implementation of ‘class Graph’ or ‘class Vector’. Though its pretty cool to see a complete packaged solution, I believe this was a slight overkill. This was NOT the basis of judging but I do feel that ruby has its essence in getting the job done in far lesser code. i.e. less LOC. So, I personally did not foresee 3-4 classes with inheritance in them.. I do totally agree its an excellent way to show-case one’s skills 😉
Djikstra’s algorithm seems to be the popular hit for solving this problem – however, I do feel a recursive solution than an iterative one is more appropriate for this. Again this is just an opinion but to get a sense of the power of ruby programing, a recursive program probably paints a better picture. Its also very concise and readable.
A lot of effort was spent in ‘initializing’ the data-structure. This was really nice to see — unlike me, who took a short-cut. The aim was to see the algorithm but I was really proud to see ‘complete’ solutions. Test cases were written in most solutions and it was a pleasure to see them run.
It was interesting to see various forms of Infinity:
Infinity = 1 << 64 Infinity = 1 << 32 Infinity = 1.0 / 0 # simple and ideal Infinity = 1000000 # incorrect
It was interesting to note that very few catered for multiple shortest paths, though the question was raised in the comments earlier. Not trying to be a hypocrite here, I should say that I too did not implement multiple shortest paths – LoL.
My solution to the problem is provided at http://github.com/gautamrege/short_circuit and its merely a representation of my style of programing. Creating a gem was for kicks but lib/short_circuit.rb has the core code. It was great fun AND learning while doing this and I realized that I will always be a student.
Cheers!
GautamRege's Blog - I have relocated to: blog.joshsoftware.com 
@all participants,
Thank you for joining and sharing your solutions. I run them with a tiny test snippet `auto_check.rb`.
http://github.com/gautamrege/short_circuit/tree/master/solutions/auto_eval/
It uses four test cases:
http://github.com/gautamrege/short_circuit/tree/master/solutions/auto_eval/imgs/
@Gautam,
Thank you for creating this great challenge ‘Short-circuit’.
I enjoyed and learnt a lot!
Cheers,
ashbb
ps. If you are interested in an another approach, look at my two cents.
I’m lousy at math, so I lean pc power. 😉
Hi all,
As a relative Ruby Newbie myself, I had a great time looking at all the solutions and definitely learned some interesting tricks. As Gautam mentioned, Dijkstra’s algorithm was used quite a few times. Even so, the implementation of that algorithm as well as some of the other completely inventive algorithms (some which worked better than others) was fascinating to see. I too was impressed with the few that went with recursion, which, at least code-wise, seemed to be the shortest route.
All in all, it was a whole lot of fun and thanks to Gautam for a thought-provoking puzzle and for Satish Talim and Ruby Learning for hosting it. 🙂
Cheers for the challenge Gautam, gave me a few hours respite from Java 😀
If anyone’s interested in a one off, unscientific recursive vs iterative performance analysis I’ve coded and run some benchmarks based on Todd’s winning submission: http://practicaldev.blogspot.com/2009/11/recursion-in-ruby.html
Short version is recursion is pretty but immeasurably slower.
Hi Andy,
Great analysis! The debate of recursive Vs iterative Approach has been going on for a long time and its always good to choose on a case-to-case basis.
As they say: “If those costs (the cost for programming time) are more important than the cost of having a slow program, then the advantages of using the recursive solution outweigh the disadvantage, and you should use it! “