Archive

Posts Tagged ‘RubyLearning’

RPCFN#3 Short-circuit

November 20, 2009 5 comments

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!

Follow

Get every new post delivered to your Inbox.