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.



About Gautam Rege

Rubyist, Entrepreneur and co-founder of Josh-Software - one of the leading Ruby development shops in India.
This entry was posted in Ruby on Rails and tagged , . Bookmark the permalink.

5 Responses to RPCFN#3 Short-circuit

  1. Pingback: RPCFN: Short Circuit (#3)

  2. ashbb says:

    @all participants,

    Thank you for joining and sharing your solutions. I run them with a tiny test snippet `auto_check.rb`.


    It uses four test cases:



    Thank you for creating this great challenge ‘Short-circuit’.
    I enjoyed and learnt a lot!


    ps. If you are interested in an another approach, look at my two cents.
    I’m lousy at math, so I lean pc power. 😉

  3. Jeff Savin says:

    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. 🙂

  4. Andy Newport says:

    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.

    • gautamrege says:

      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! “

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s