Home > Ruby On Rails > RPCFN#3 Short-circuit

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!

About these ads
  1. November 22, 2009 at 3:34 am

    @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. ;-)

  2. Jeff Savin
    November 23, 2009 at 2:21 am

    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. :)

  3. Andy Newport
    November 24, 2009 at 12:55 am

    Cheers for the challenge Gautam, gave me a few hours respite from Java :D

    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.

    • November 25, 2009 at 8:36 am

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

  1. November 21, 2009 at 6:03 am

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

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: