RPCFN: Short Circuit (#3)

by on October 30, 2009

Ruby Programming Challenge For Newbies

RPCFN: Short Circuit (#3)

By Gautam Rege

About Gautam Rege

Gautam RegeGautam Rege (twitter / blog) is based in Pune, one of the busiest IT hubs in India. He has done his computer engineering from Pune Institute of Computer Technology (PICT) and passed out in the year 2000. After working for a few services based companies like Zensar and Cybage he got exposure to product companies like Veritas (now Symantec). It was always his aim to be self-employed and when he found the right partner in his friend Sethupathi Asokan, they both started Josh Software Pvt. Ltd..

Gautam has this to say about the challenge:

RPCFN is a unique idea on RubyLearning – and I wish I had some such help when I was starting to learn Ruby. This is learning and fun! Now that everyone seems to have got onto the challenger track, I think its time to raise the bar — very slightly ;) Short-circuit has a twist in the tail – its not just learning Ruby but also seeing how easy it is to implement well-known algorithms quickly and efficiently. Welcome newbies to this 3rd Challenge – all the best!

Sponsor

Josh Software Pvt. Ltd.

This monthly programming challenge is sponsored by Josh Software Pvt. Ltd. Josh Software is an upcoming Rails start-up in Pune, India. ‘Josh’ in Hindi (an Indian language), means ‘enthusiasm’. The Josh team builds state-of-the-art web based applications for various clients in various industry verticals with all the ‘josh’. The work culture at Josh involves fun at work, sincerity in coding and quality deliverables.

Prizes

  • The person with the best Ruby solution (if there is a tie between answers, then the one who posted first will be the winner) will be awarded any one of PeepCode’s Ruby on Rails screencasts.
  • The other two prizes, selected randomly amongst the remaining working Ruby solutions, would be any one of:

The three persons who win, can’t win again in the next immediate challenge but can still participate.

The Ruby Challenge

RPCFN

Given a closed electrical circuit, we need to identify the redundant elements. For the sake of simplicity, we shall assume only resistors between various points. Electricity will flow through the path of least resistance! Source of electricity is A and the end-point is G.

The idea of the program is to find the redundant resistors.

Short Circuit

As shown in the diagram we can ‘translate’ load between points into any simple data structures. For example:

[
   [ A, B, 50],
   [ A, D, 150],
   [ B, C, 250],
   [ B, E, 250],
   [ C, E, 350],
   [ C, D, 50],
   [ C, F, 100],
   [ D, F, 400],
   [ E, G, 200],
   [ F, G, 100],
]

Feel free to use ANY other data structure as long as assumptions are simple and understandable. The source and the end-point may be hard-coded in the script or can be taken as command line parameters, whichever you feel is convenient.

In the above example, the output expected MUST be the following array of arrays:

[
  [ 'A', 'B', 50 ],
  [ 'B', 'C', 250],
  [ 'B', 'E', 250],
  [ 'C', 'E', 350],
  [ 'D', 'F', 400],
  [ 'E', 'G', 200],
]

Hint

  • ‘Short Circuit’ is a cryptic clue to the solution for this challenge.

Requirements: This has to be a pure Ruby script, using only the Ruby Standard Libraries (meaning, no external Gems). You do not need to build a gem for this. Pure Ruby code is all that is needed.

How to Enter the Challenge

Read the Challenge Rules. By participating in this challenge, you agree to be bound by these Challenge Rules. It’s free and registration is optional. You can enter the challenge just by posting the following as a comment to this blog post:

  1. Your name:
  2. Country of Residence:
  3. GIST URL of your Solution (i.e. Ruby code) with explanation and / or test cases:
  4. Code works with Ruby 1.8 / 1.9 / Both:
  5. Email address (will not be published):
  6. Brief description of what you do (will not be published):

Note:

  • As soon as we receive your GIST URL, we will fork your submission. This means that your solution is frozen and accepted. Please be sure that is the solution you want, as it is now recorded in time and is the version that will be evaluated.
  • All solutions posted would be hidden to allow participants to come up with their own solutions.
  • You should post your entries before midnight of 20th Nov. 2009 (Indian Standard Time). No new solutions will be accepted from 21st Nov. onwards.
  • On 21st Nov. 2009 all the solutions will be thrown open for everyone to see and comment upon.
  • The winning entries will be announced on this blog before end of Nov. The winners will be sent their prizes by email.

More details on the RPCFN?

Please refer to the RPCFN FAQ for answers to the following questions:

Donations

RPCFN is entirely financed by RubyLearning and sometimes sponsors, so if you enjoy solving Ruby problems and would like to give something back by helping with the running costs then any donations are gratefully received.

Click here to lend your support to: Support RubyLearning With Some Love and make a donation at www.pledgie.com !

Acknowledgements

Special thanks to:

Questions?

Contact Satish Talim at satish [dot] talim [at] gmail.com OR if you have any doubts / questions about the challenge (the current problem statement), please post them as comments to this post and the author will reply asap.

The Participants

There are two categories of participants. Some are vying for the prizes and some are participating for the fun of it.

In the competition

  1. James Daniels, USA
  2. Harshad R Wankhede, India
  3. Ben Marini, USA
  4. Robison WR Santos, Brazil
  5. Mark, USA
  6. Valério Farias, Brazil
  7. Prakash Sejwani, India
  8. Paul Smith, England
  9. Himansu Desai, USA
  10. Rohit Sasikumar, India
  11. Pat Harty, USA
  12. Todd Huss, USA – declared winner (best solution)
  13. Tom, France – declared winner (randomly selected)
  14. Javier Blanco Gutiérrez, Spain
  15. Sogo Ohta, Japan
  16. Rainer Thiel, New Zealand
  17. Andy Newport, New Zealand
  18. Antonio, Canada
  19. Glenn Goodrich, USA
  20. Sam Johnson, Canada – declared winner (randomly selected)

Just for Fun

  1. Aldric Giacomoni, USA

The Winners

Winners

Congratulations to the winners of this Ruby Challenge. They are:

Previous Challenge

RPCFN: Average Arrival Time For A Flight (#2) by Chris Strom.

Update

This challenge is now closed. Gautam Rege has posted on his blog his observations on the code submitted for this challenge. Do have a look.

  • The (#4) challenge by Michael Kohl, Austria is scheduled for 1st Dec. 2009.
  • The (#5) challenge by Peter Cooper, UK is scheduled for 1st Jan. 2010.
  • The (#6) challenge by John Trupiano, USA is scheduled for 1st Feb. 2010.

Technorati Tags: , , , , ,

Posted by Satish Talim

Follow me on Twitter to communicate and stay connected

{ 81 comments… read them below or add one }

Rodrigo Rosenfeld Rosas October 30, 2009 at 3:10 pm

Just to clarify a bit for those that haven’t studied about electrical circuits.

This is the basic idea:

The electrical current that flows by a resistor is calculated as:

I = V/R, where V is the voltage around the resistor.

In any given node, the total currents that come into the node equals the total current that flows out of the node.

The redundant resistor between two nodes, are calculated, basically, by the following algorithm.

Short-circuit any DC sources. Imagine you are placing a new DC source between two points. Calculate the current that will be driven by the DC source. The redundant resistor is the one that when replacing all circuit would consume the same current as all circuit. That means that you could replace the entire circuit by one resistor and the source would drive the same current.

But I didn’t understand what exactly would be the expected array…

Reply

Gautam Rege October 30, 2009 at 3:33 pm

Hi Rodrigo,
In the given electrical circuit, as I have mentioned, the path of electric current would follow the path of least resistance — always. So, the remaining resistors would be redundant.

We are not supposed to re-design the circuit, simply identify the redundant resistors. We can display these resistors with [ start, end, resistance ].

Reply

Pankaj Sisodiya October 30, 2009 at 3:17 pm

Hi Gautam,

Can you please rephase you problem.
———————
The idea of the program is to find the redundant resistors.
———————

Thanks,
Pankaj Sisodiya

Reply

Gautam Rege October 30, 2009 at 3:39 pm

Hi Pankaj,
As I mentioned in my earlier comment, we need to identify the resistors through which the current will not flow. “Electricity will flow through the path of least resistance!” – so the remaining paths will not be used.
The expected output is an array of such paths as I have mentioned.

Hope this helps!

Reply

James Daniels October 30, 2009 at 4:01 pm

Solution (#1):

#1 James Daniels, USA
Original: http://gist.github.com/222262
Forked: http://gist.github.com/222836
Confirmed Ruby 1.8

Reply

Dave Lilley November 21, 2009 at 6:34 am

I liked his approach but documenting the code would have helped.

Reply

Paul Smith October 30, 2009 at 4:10 pm

I think the problem author has messed up here. In reality, electricity does not only follow the path of least resistance. It follows all paths of all resitances in proportion to their conductance.

What the problem author is looking for is the path of least resistance through the circuit. That path is ADCFG for a total resistance of 400 Ohms. Therefore the ‘redundant resistors’ are those connections which are not on the shortest path, i.e. AB, BC, BE, CE, DF, EG. Why the problem author wants the resistances of the reduntant resistors as part of the solution I don’t know, but it’s his problem :)

Reply

Gautam Rege October 30, 2009 at 4:24 pm

Hi Paul,
You guessed right – I am not an electrical engineer :) AND I have little interest in the electrical part of this problem statement.

I am however a programmer and the algorithm for the shortest path is of keen interest, as part of this challenge. Hence I clearly mentioned that electricity would flow in the path of least resistance — please bear with the terminology here.

You have correctly spotted the shortest path algorithm. The ‘twist’ is in getting the remaining resistors. As part of the ideology of the challenge, the fun and learning is in getting to the solution — not the solution itself :D

Regards,
Gautam

Reply

Paul Smith October 30, 2009 at 6:11 pm

I understand you Gautam – it’s just that electricity doesn’t do that, which is why I think your readers are having problems.

Reply

Rodrigo Rosenfeld Rosas October 30, 2009 at 6:23 pm

Exactly. Specially because I am an Electrical Engineering :)

Talking about routers would make more sense though :)

And I believe that finding the equivalent resistor would be too much for beginners also :)

Reply

Jim October 30, 2009 at 6:55 pm

NOW i understand the problem. Thank you.

Reply

Yossef Mendelssohn October 30, 2009 at 9:32 pm

I think the challenge also suffers from a disconnect between the apparently intended goal and the stated goal. To solve the problem, you need to go through the effort of finding the shortest path; rather than return this path as the solution, you need to indicate which segments are *not* part of the path.

Reply

Martin DeMello October 30, 2009 at 9:36 pm

That’s actually a pretty good test of your datastructure.

Reply

Gautam Rege October 30, 2009 at 9:46 pm

@Yossef What Martin said is exactly what is interesting. Twisting the problem around a little actually encourages more use of data structures and I guess that is what the challenge is all about.

Reply

Gautam Rege October 30, 2009 at 6:26 pm

@Paul, @Rodrigo – thanks for the clarifications regarding the flow of electricity. Its is really appreciated. The premise ‘electricity flows in the path of least resistance’ is indeed a death trap in today’s world but was an accepted premise earlier.

Again: The aim of the problem is not to understand electricity but to basic programmatic algorithms. Hence my assumption stated in the problem: electricity flows in the path of least resistance.

With no offense to any electrically literate people, I hope the problem statement is clear from the point of view of the algorithm :)

Reply

Paul Smith October 30, 2009 at 7:09 pm

Are we to assume that there is a single path of least resistance?

Reply

Gautam Rege October 30, 2009 at 7:23 pm

Hi Paul,
For the sake of simplicity, you may assume this in your program. However, if you can take into consideration multiple shortest paths and hence different ‘redundant resistors’ it is more than expected.

I guess the term is ‘extra brownie points’ ;)
Glad to see your keen interest in the challenge.

Reply

Sam Johnson November 12, 2009 at 6:10 am

I have two questions:

1) should the output of the script be the array object itself, or should we write the contents out to stdout and format like your example?

i.e. the difference between ending the script with
@RedudantPaths

vs something like:

@RedundantPaths.each {|path| “\[ \'#{path[0]}\’, \’#{path[1]}\’, #{path[2]}\],”

and 2) If we do include support for finding multiple paths, how should we format the output

(Maybe both of these can be answered by letting us know if you’re visually verifying our entries, or using an automated process)

Thanks!

Sam

Reply

Gautam Rege November 12, 2009 at 10:54 pm

Hi Sam,
We are using automated scripts for verifying and using an array of arrays as input for testing. We are expecting the array of arrays as output as mentioned. This could be printed on console or in an instance variable – no worries, as we have scripts which manage both.

Regarding multiple shortest path, you may choose the first one you have encountered.

+100 brownie points already for considering this ;)
Cheers!

Reply

Rainer November 1, 2009 at 3:27 am

Nice question!
Otherwise I’m glad I hung around a little and took note of all the comments so far. They have certainly clarified the requirement for me. Thanks to you all.

Reply

Pete Campbell October 30, 2009 at 9:24 pm

Seems to me that you can think of this as a traveling-salesman type of problem. You need to figure out the “shortest” route (eg least resistance, no pun intended) from point A to point B. All paths that are not on this route are considered “redundant”.

While you did say that “electricity flows through the path of least resistance”, the electrical circuit metaphor is pretty misleading for EEs since electricity is like water and flows through multiple paths depending upon their resistance.

Reply

Gautam Rege October 30, 2009 at 9:48 pm

Hi Pete,
Probably lucky not to be crucified by all EEs because I have made a clear assumption in my problem statement that ‘electricity flows through the path of least resistance’. Though this may be wrong (as has already been pointed out earlier) I guess, its ok from the program point of view!

I hope you agree with me — you have the logic spot on!
- Gautam

Reply

Pete Campbell October 30, 2009 at 9:58 pm

You are right that you clearly stated the assumption, we EE’s definitely overlooked that statement and drew upon our EE background. Its good that this is being clarified very early (and shows the enthusiasm for the contest). Thanks for creating the challenge, I appreciate it.

Reply

harshad October 30, 2009 at 9:25 pm

Solution (#2):

#2 Harshad R Wankhede, India
Original: https://gist.github.com/932dda6ee34590624df8
Forked: https://gist.github.com/33a2fc37cd23c9a163ec
Code works with: Ruby 1.9.1p0

Reply

Dave Lilley November 21, 2009 at 6:36 am

I like the comments at the start as it will help ANY one following to quickly understand the use of variables etc.

Reply

Jeff Savin November 21, 2009 at 6:37 am

While the code may not be super readable, I didn’t think it was bad. The comments really help as Harshad explains a bit of what he is doing. Recursion always excites me.

Reply

Harshad November 23, 2009 at 10:13 am

Thanks Dave and Jeff for your comments,
I thought implementing Djikstra’s algorithm is the correct way, but I wanted to have a solution of my own. Something which I will enjoy and is quite new. I didn’t expect it to be a correct approach btw :)
- Harshad

Reply

Tom Voltz November 1, 2009 at 1:54 am

Small typo in the expected output. The last element of the array should not be followed by a comma and the element E has a closing double rather than single quote. It should probably read:

[ 'E', 'G', 200]

It might make evaluating the entries easier if you did specify some input format… so testing each persons code against a few test cases will be easier.

Cheers! Looks like a fun one.

Reply

Satish Talim November 1, 2009 at 7:37 am

Thanks Tom. Typo corrected. BTW a trailing comma is ignored by Ruby, as shown in this example:

a = [
  [ 'A', 'B', 50 ],
  [ 'B', 'C', 250],
  [ 'B', 'E', 250],
  [ 'C', 'E', 350],
  [ 'D', 'F', 400],
  [ 'E', 'G', 200],
]

b = [
  [ 'A', 'B', 50 ],
  [ 'B', 'C', 250],
  [ 'B', 'E', 250],
  [ 'C', 'E', 350],
  [ 'D', 'F', 400],
  [ 'E', 'G', 200]
]

puts a.class # Array
puts b.class # Array

Reply

Gautam Rege November 1, 2009 at 10:37 am

Thanks Tom for pointing this out.. this is much appreciated.
I checked solutions test code and it was corrected there already. Guess I forgot to update the problem statement.

Regards,
Gautam

Reply

Himansu Desai November 1, 2009 at 6:52 am

Hi – Would like a clarification before I try to solve this. The suggested data structure ([ B, E, 250], [ C, E, 350] etc.) implies that the “direction” heading from closer to Source (first element) to closer to Earth (second element), is already known. The flow of current for this particular exercise (A->D->C->F->G) also hints that current (always) flows from ‘closer to Source’ to ‘closer to Earth’. This is not true – strictly speaking – and I wanted to clarify if our solutions are expected to solve the more general case. For example, for certain values of the resistors, the shortest resistance path can be A->B ->E->C->F->G. Note that for the E->C segment, current is moving from ‘closer to Earth’ to ‘closer to Source’ i.e. away from the normal or intuitive direction. Data structures that assume the direction of flow “before” calculating the shortest path will be incorrect for some values of the resistances. Thanks

Reply

Gautam Rege November 1, 2009 at 9:34 am

Wow Himanshu!
Thanks for the insight on flow of electricity — this one new to me. For this particular program, I had not taking the earth into consideration. :) Nevertheless, assuming the assumption in the problem statement ‘Electricity flows in the path of least resistance’, I think its all about algorithm and programing and NOT really about electricity and resistance.

Hope this makes sense and the program easier to understand !
Regards,
Gautam

Reply

Himansu Desai November 1, 2009 at 11:54 am

Sorry Gautam – Long winded and confusing verbiage. Didn’t mean to talk about the science of electricity. Just trying to talk through something that may be obvious to all but a source of confusion for me. The algorithm should analyze both directions of a particular segment right?. In the above example, if we had [ A, B, 1], [ A, D, 3], [ B, C, 3], [ B, E, 1], [C, E, 1], [ C, D, 3], [ C, F, 1], [ D, F, 3] [ E, G, 4], [ F, G, 1], the path of least resistance is A -> B -> E -> C -> F -> G (with other resistors being redundant) i.e. when going from source to target, trace from C to E or from E to C, whichever one leads to the least total resistance.

Reply

Gautam Rege November 1, 2009 at 4:03 pm

Hi Himnashu,

Both directions should be considered. The array is simply a translation of nodes and resistance between them. So, trace can flow from C to E or E to C.

Reply

Ben Marini November 2, 2009 at 4:22 am

Solution (#3):

#3 Ben Marini, USA
Original: http://gist.github.com/223789
Forked: http://gist.github.com/239907
Code tested on Ruby 1.8

Reply

Jeff Savin November 21, 2009 at 6:40 am

I thought the code to be a bit long. Over use of Classes – Edge, Vertex, Graph. The program did accomplish what was asked of it, and quite well.

Reply

Robison WR Santos November 2, 2009 at 10:31 pm

Solution (#4):

#4 Robison WR Santos, Brazil
Original: https://gist.github.com/7563ec4042497f4ecf52
Forked: https://gist.github.com/81c44daaa747e1fcbf4c
Code works with Ruby 1.8

Reply

Jeff Savin November 21, 2009 at 6:41 am

What I liked best about Robison’s, is his very clear and detailed explanation about how he went to solve the problem. Too bad he got one failure in the tests , I thought he had a pretty good algorithm and method for solving.

Reply

Mark November 3, 2009 at 12:39 am

Solution (#5):

Mark, United States
Original: http://gist.github.com/224398
Forked: http://gist.github.com/239918

Reply

Jeff Savin November 21, 2009 at 6:43 am

The code works well. A little recursion might be a shorter and more elegant solution. Oh, and I love commented code. Too bad this program had zero comments.

Reply

Valério Farias November 3, 2009 at 10:13 am

Solution (#6):

Valério Farias, Brazil.
Original: https://gist.github.com/ebea6c81253e73f32986/0c7eaf2b3c8196077149b2e2df727e51ae6b086e
Forked: https://gist.github.com/f4085dff1e241dc3e098
I created a class Graph. This class contain a method dijkstra
to find the smallest path in the graph.
The code works with Ruby 1.8

Reply

Jeff Savin November 21, 2009 at 8:49 am

I liked this solution. One of the shortest of the non-recursive entries, so far. The code was well commented and therefore more readable than if it had been left alone. What I love about this job, if you can call it that, is you learn new things all the time. The 1 << 32 was a new one for me, but pretty slick. I'll remember that one!

Reply

prakash sejwani November 3, 2009 at 12:23 pm

Solution (#7):

Prakash Sejwani, India
The code is in ruby 1.8.7
Original: git@gist.github.com:02194fa01ba59132e128.git
Forked: https://gist.github.com/b3a39b13e07a13ad4055

Reply

Jeff Savin November 21, 2009 at 8:53 am

Hmmm, this didn’t seem like a solution to solve the problem in general, but specifically the exact circuit given to it. This of course makes the program inflexible and in general, not much use.

Reply

Paul Smith November 4, 2009 at 5:17 am

Solution (#8):

Paul Smith, England
Original: https://gist.github.com/1b12e9187b5060c28c2e
Forked: https://gist.github.com/602034e12a217dff7c0e
Code Tested with Ruby 1.9

Reply

Jeff Savin November 21, 2009 at 8:53 am

I liked this code, although not recursive. Was very well commented and readable. At least, it seemed to make sense. Also performed well on the tests.

Reply

Himansu Desai November 4, 2009 at 9:25 am

Solution (#9):

Himansu Desai, USA
Original Gist URL: git@gist.github.com:ef455ce56ed80ff73f5e.git
Pastie: http://pastie.org/682803

Reply

Jeff Savin November 21, 2009 at 8:54 am

Recursive, nice. Very well commented, nice. Passed all tests, nice. However, it seemed like more code than necessary to accomplish the desired results, but maybe that’s just me. Overall, a pretty strong solution.

Reply

Rohit Sasikumar November 4, 2009 at 5:18 pm

Solution (#10):

Rohit Sasikumar, India
Original: https://gist.github.com/0ff485999bc8be8f7fc4
Forked: https://gist.github.com/2419497a5f573a691d69
Code works with Ruby 1.8

Reply

Jeff Savin November 21, 2009 at 8:55 am

The algorithm is the one made famous by Dijkstra, but the implementation has an issue as it failed one of the auto_check tests. The other thing I wasn’t sure about was Rohit’s comment that the flow of the current making a difference. I’m not sure it should?

Reply

Pat Harty November 5, 2009 at 8:44 pm

Solution (#11):

Pat Harty, USA
Original: https://gist.github.com/651744c264a87e91ad56
Forked: https://gist.github.com/26c9753a8b5fb4acee4d
Description of Code: Objects were created for each resistor and the end points that it connected (e.g. A B 50). These objects were kept in an Array. Traversed the circuit by taken the start point of A searching for ResistorLink objects that contained that value as one of the links then traveling to the other point and doing the search for that point adding the value of the resistors along the way. These points would be searched and traversed until either the endpoint ‘G’ was reached or there were no more valid points to travel to. At that point the route taken would be added to a deadend list so it would not be followed again. Also, a list was kept so the same point would not be traversed more than once. When a successful start to finish route was found it was added to an array of successful paths that would be searched through to find the path of least resistance after all possible routes had been taken. Then when the path of least resistance was found, the array of ResistorLink objects was searched and if they were found to be a part of the least resistant path they were marked as Used. Going through the array one last time searching for Unused ResistorLink objects gave us our list of redundant resistors.

In the description of the challenge it mentioned the results for the example must be an array of arrays. Wasn’t sure if output for all solutions was wanted in an array of array’s format or if that was specific to that example, but I don’t have the output in that format so hopefully that isn’t the case :)

Thanks for creating this challenge I had a really fun time working on it.

Reply

Jeff Savin November 21, 2009 at 8:56 am

Well, this guy is a self-described Ruby newbie, which I guess is who we are targeting the challenge too. He tackled the problem, but used a fair amount of code to do so. Unfortunately, according to the auto_check, his program short-circuited a bit. On the positive side, Pat’s code was well commented.

Reply

Todd Huss November 7, 2009 at 12:20 pm

Solution (#12):

Todd Huss, USA
Original: http://gist.github.com/228577
Forked: http://gist.github.com/228612
Code works with Ruby 1.8 and 1.9

Reply

Jeff Savin November 21, 2009 at 8:57 am

Wow. Excellent solution. Todd went about solving this problem by meeting his intended goals of not using Dijkstra’s well-known shortest-path algorithm, but instead creating his own recursive algorithm. The results, simple, easy to read, and with a 100% pass-rate. This, so far, is hands-down, my favorite. The added bonus was solid RSpec code to match.

Reply

Michael Kohl November 23, 2009 at 5:32 am

This solution is way ahead of the competition in terms of readability and elegance. Very, very nice!

Reply

Tom November 8, 2009 at 8:45 pm

Solution (#13):

Tom, France.
Original: https://gist.github.com/8a70b216514ab5edab5d
Forked: https://gist.github.com/31f3f0dd0b9533277e92
Code works with Ruby 1.9 (not tested with 1.8).
Code explanation:
The main part if the PathFinder which tells the path going from the specified start to the end. Then the Electricity (hehe real bad name :-) ) find the least resistance path and return the unused edges.

Possible improvements:
- Use a closure to run the recursive stuff (I think the closure can retain the context [the list of node] instead of having a method parameter)
- Create an “Edge” class (start, end, resistance)
- Rename the Electricity class for a better name

Reply

Jeff Savin November 21, 2009 at 8:57 am

Good implementation and passed all tests. Seemed like a lengthy solution, but not hard to read and included test cases. Solid and well done.

Reply

Javier Blanco Gutiérrez November 9, 2009 at 12:17 am

Solution (#14):

Javier Blanco Gutiérrez, Spain
Original: http://gist.github.com/223826
Forked: http://gist.github.com/232911
Works with both

Reply

Jeff Savin November 21, 2009 at 8:58 am

Another solution using Dijkstra’s algorithm and again, a bit lengthy. Seems like results are good with Satoshi Asakawa’s slight code massage. Code could be commented a bit more, but not bad. Overall, another solid solution.

Reply

Aldric Giacomoni November 9, 2009 at 6:04 pm

How are you going to handle the input of various test cases?
Are you going to make a YAML file? Or maybe, as your example suggests, a text file with an array of arrays?
I’d like to make your life -a little- easier.

Reply

Gautam Rege November 12, 2009 at 8:04 pm

Hi Aldric,
Our team has already written some autoeval script to automated testing. The input for these are the arrays as I have mentioned in the problem statement.

However, if you are using some different data structures, it would greatly help if you would also write some test cases using Test::Unit. So, you can evaluate your own results.

Your interest in making our life easier is much appreciated :)

Reply

Aldric Giacomoni November 10, 2009 at 3:03 am

Solution (#15):

Aldric Giacomoni, USA
Original: http://gist.github.com/226079
Forked: http://gist.github.com/235140
I am submitting this code for fun, not for the prize :)

Reply

Jeff Savin November 21, 2009 at 8:59 am

Pretty clean solution. Worked on all our test cases. Uses Dijkstra’s algorithm. Decent comments and code readability. Overall, very nice.

Reply

Brad O'Connor November 10, 2009 at 3:44 pm

I’m keen to get on and solve this problem but I’ve got to say it’s unlike any I’ve tried before. It seems a bit more computer-sciencey and a bit less web-scripty than what I’m used to. Can someone suggest a good source of information on the way to approach a problem like this? I can think of a few ways but I suspect they are unnecessarily complicated.
Thanks.

Reply

Aldric Giacomoni November 10, 2009 at 11:50 pm

Brad, the comments so far have indicated that “shortest-path”, along with keywords like ‘algorithm’ might help you. Google will be your friend, and wikipedia will be as well :)

Reply

Gautam Rege November 12, 2009 at 8:05 pm

Thanks Aldric (again) for helping out!

@Brad, As has been hinted, the problem statement may look ‘electrical’ in nature but is in the end a standard algorithm that is freely available. A quick read of the comments earlier would give you enough clues on how to solve this problem and what the expectation is.

Reply

Sogo Ohta November 14, 2009 at 9:26 pm
Jeff Savin November 21, 2009 at 9:00 am

Small code footprint, but unfortunately, doesn’t seem to work in all cases. The code is not commented at all, decreasing the readability a bit. I like that he went about this trying to come up with his own solution rather than the already well-overused Dijkstra’s algorithm. Too bad it didn’t quite work as planned. ;)

Reply

Rainer November 15, 2009 at 1:08 pm

Solution (#17):

Rainer Thiel, New Zealand
Original: https://gist.github.com/5bc670cb26ca89ae7f3a
Forked: https://gist.github.com/b19a4f95fd09e2a5bed3

Reply

Jeff Savin November 21, 2009 at 9:01 am

Wow ! A lot of time was spent on this solution and working or not, there was a lot of thought put into this as evident by the amount of code and extremely thorough documentation. Too bad this didn’t work, as I would’ve liked to have seen how it handled the auto_check test cases.

Reply

Rainer November 22, 2009 at 9:50 am

Hi Jeff,
Thanks for your look at my solution. What is the auto_check test that my solution failed? I thought i had something ok going there…

Reply

Jeff Savin November 23, 2009 at 5:30 am

Sensei Satoshi Asakawa has a series of test cases that all solutions go thro’ and auto_check test was one of them.

Reply

Andy Newport November 18, 2009 at 4:01 am

Solution (#18):

Andy Newport, New Zealand
Original: http://gist.github.com/237354
Forked: http://gist.github.com/239937
Code tested with Ruby 1.8 on Windows

Reply

Jeff Savin November 24, 2009 at 7:09 am

Once again, looks like a whole lot of code to achieve the results. At least, according to auto_check, no failures, so that’s a plus. Code is well-commented and not too hard to read. Algorithm is again, the Dijkstra algorithm.

Reply

kainage November 19, 2009 at 9:34 pm

Solution (#19):

Antonio, Canada
Original: git@gist.github.com:75968c5b5a0f0f8f7a83.git
Forked: https://gist.github.com/5f939c6052e0401d5b92
Tested extensively during writing, no test cases included.
Written on 1.8.6 tested on 1.8.6

Reply

Jeff Savin November 24, 2009 at 7:08 am

Dijkstra’s algorithm. Well commented, yet again, a good amount of code to achieve the results.

Reply

Glenn Goodrich November 19, 2009 at 9:40 pm

Solution (#20):

Glenn Goodrich, Charlotte, NC, USA
Original: http://gist.github.com/222855
Forked: http://gist.github.com/239940

Reply

Jeff Savin November 24, 2009 at 7:08 am

Glenn says above, “Don’t laugh too hard.” Well, I didn’t laugh. I thought his solution was well thought out and the code was nice to read. Its too bad the code was dependent on the data structure and failed the auto_check test in a few spots.

Reply

Sam Johnson November 21, 2009 at 3:07 am

Solution (#21):

#21 Sam Johnson, Canada
Original: https://gist.github.com/5ed31a447fb4c03a40fc
Forked: https://gist.github.com/f26ca1ef60cef80ca9a7
Simple recursive solution that moves through all paths, and saves the cost for each path. This algorithm only works in a reasonable amount of time because there are so few nodes in this network.

Reply

Jeff Savin November 24, 2009 at 7:07 am

Cool. Real short and sweet recursive solution. One of the better ones and passes all tests. :)

Reply

Gautam Rege November 25, 2009 at 1:39 pm

Andy Newport posted some interesting comments regarding the winning solutions – the debate of Recursive Vs Iterative approach :)

Very interesting read:
http://gautamrege.wordpress.com/2009/11/20/rpcfn3-short-circuit/

Reply

Leave a Comment

{ 18 trackbacks }

Previous post:

Next post: