RPCFN: Fair Distribution (#6)

by on January 26, 2010

Ruby Programming Challenge For Newbies

RPCFN: Fair Distribution (#6)

By John Trupiano

About John Trupiano

John TrupianoJohn Trupiano (twitter) is the co-founder of SmartLogic, the premiere Ruby development team in Baltimore, Maryland. He is an active member in the technology and business communities in the mid-Atlantic region. He is highly involved with the local Ruby user group (Bmore on Rails) and recently organized the first ever Maryland TechCrawl, a show and tell event showcasing the exciting and innovative technologies being developed in the region. He is also very active in the open source community having authored timecop and Rack::Rewrite and contributing to a slew of projects including rails, capistrano, shoulda, factory_girl, gemcutter and multitest.

John has this to say about the challenge:

I think the Ruby challenge is great because it instills from the very start the idea that you need to practice to become a great programmer. Even as a problem setter, I have found the exercise of defining a problem and iterating through various solutions to be extremely educational and beneficial. Satish has cultivated a fantastic program here that provides access for beginners to seasoned Ruby programmers. Furthermore, the Ruby challenge serves as a notice to the Ruby community that it is important for us to provide a welcoming and nurturing environment for newcomers.

Our Awesome Sponsors

This monthly programming challenge is co-sponsored by Backup My App and Caliper.

Backup My App

Backup My App is an automatic backup service for Ruby on Rails applications. You simply install the plugin to your Rails application and they handle the rest of the process. They store backup history for several weeks and you can restore any of them automatically. Try out their 1 GB plan for free. Backup My App has co-sponsored this challenge and is proud to make this contribution to the Ruby community.

Caliper

Caliper provides free, hosted metrics for Ruby programmers. Find duplication, code smells, complex code and more! Get set up with just one click!

Prizes

  • The participant 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 and a free 10 GB account for a year from Backup My App.
  • From the remaining working Ruby solutions, three participants would be selected randomly and each one would be awarded any one of Pragmatic’s The Ruby Object Model and Metaprogramming screencasts.
  • All the participants in this challenge (except the participant with the best Ruby solution) will get a free 5 GB account for 6 months from Backup My App.

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

The Ruby Challenge

RPCFN

The Challenge

Imagine that you manage a t-shirt printing company. Each morning you review all orders placed the prior day and determine how long each order will take to fulfill. On any given day, only a certain number of your printing machines are operational. Your job is to schedule each printing job with one of the operational printing machines in such a manner that (a) all t-shirts are printed in the least amount of time, and (b) the distribution of work across machines is as fair as possible (i.e. the standard deviation of the time each machine spends working is minimized).

Your objective is to write a FairDistribution class that satisfies the following test cases. The code in the test cases is sufficient to define the methods you must implement.

This is an NP complete problem, and as such I have only provided very small datasets in the test cases. Test case #3 takes the longest to solve (See **Notes below about how to run the Test Case #3) and you may find it easier to comment it out early in your development phase. On a MBP Pro with a 2.4 GHz dual core processor and 4GB RAM, it took just over 3 minutes to solve. The other three test cases took only a couple of seconds.

Note that test cases 2 and 4 define specific distributions against which you can verify. Test cases 1 and 3 have more than one acceptable distribution and as such I have not provided a specific distribution to test against.

Note also that there is a well known algorithm that provides a much faster though not optimal solution. It will pass all tests except for test case #3. If you are only able to determine this particular solution, please still consider submitting your solution for consideration.

** Notes: To accommodate the fact that Test Case #3 takes a long time to run, you can run the test normally, and TC#3 will not run. When you want the TC#3 to run, then you can run the following:

ruby test_solution_acceptance.rb full

The word “full” will signal it to run all the test cases.

The Test Suite

test_solution_acceptance.rb

Requirements

The solution to the challenge 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 Feb. 2010 (Indian Standard Time). No new solutions will be accepted from 21st Feb. onwards.
  • On 21st Feb. 2010 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 Feb. 2010. 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:

  • John Trupiano.
  • Sponsors Caliper and Backup My App.
  • GitHub, for giving us access to a private repository on GitHub to store all the submitted solutions.
  • The RubyLearning team, namely Jeff Savin (Canada), Mareike Hybsier (Germany), Peter Crawford (Italy) and Satoshi Asakawa (Japan).

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. Rajesh Tripathi, USA
  2. Aleksey Gureiev, Australia
  3. Aldric Giacomoni, USA
  4. Adam Lum, USA
  5. Brad O’Connor, Australia
  6. Martin Linkhorst, Germany
  7. Ilya Ermolin, Russia
  8. Elijah Miller, USA – declared winner (randomly selected)
  9. Guillaume Petit, France – declared winner (best solution)
  10. Marc Minneman, USA
  11. Cary Swoveland, Canada
  12. Aurélien Bottazzini, France
  13. Benoit Daloze, Belgium – declared winner (randomly selected)
  14. Jacob Hodes, USA – declared winner (randomly selected)

Just for Fun

  1. Dominik Masur, Germany

The Winners

Winners

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

Previous Challenge

RPCFN: Mazes (#5) by Peter Cooper.

Note: All the previous challenges, sponsors and winners can be seen on the Ruby Programming Challenge for Newbies page.

Update

  • This challenge is now closed.
  • The (#7) challenge by James Edward Gray II, USA is scheduled for 1st Mar. 2010.

Technorati Tags: , , , , ,

Posted by Satish Talim

Follow me on Twitter to communicate and stay connected

{ 95 comments… read them below or add one }

Rajesh January 26, 2010 at 1:41 pm

Solution (#1):

Rajesh Tripathi, USA
Original: https://gist.github.com/7c57dfb689c21ef43950 now forked
Code works with Ruby 1.8.7

Reply

Victor Goff February 21, 2010 at 9:41 am

Tested with Ruby 1.8.6, 1.8.7, and 1.9.1. Failure is pretty complete. Refer -
http://github.com/IndianGuru/RPCFN6/blob/master/01_RajeshTripathi/result.txt

Reply

Rajesh February 21, 2010 at 10:20 pm

As i said in comments, this is an approximate algorithm and not a brute force search algorithm. So, failures are expected.

Anyway, I saw following in test results
test_basic2(FairQueueTest) [test_solution_acceptance.rb:41]:
633.0 expected but was
510.0

3) Failure:
test_basic3(FairQueueTest) [test_solution_acceptance.rb:52]:
373.0 expected but was
222.0
Looks like these tests might to be wrong, as my code is giving better results than expectations.

Reply

John Trupiano February 22, 2010 at 6:32 am

Hi Rajesh,

Something is incorrect about the 1.8.6 results, not just for you but for everyone. I think the script we were using on the backend to run these has a bug. I do not believe there is a bug in the test cases themselves.

Refer to the 1.8.7 and 1.9.1 results for an accurate assessment of your solution.

-John

Reply

Victor Goff February 23, 2010 at 3:43 am

Rajesh, My apologies for sure on the results of the 1.8.6 test results (throughout, so really to all).

Hopefully we catch this type of problem sooner, in future contests.

(I accept the responsibility for the confusion caused, I should have cleared it better with John’s results.)

Reply

John Trupiano February 22, 2010 at 7:01 am

Hi Rajesh,

It’s clear you have a good handle on the programming language Ruby. Most of your methods are single purpose (good) and you use some of the enumerator functions cleanly.

Your solution, unfortunately, does not pass any of the test cases.

Thanks for participating!

Also, just to be clear, we re-ran your submission on 1.8.6 and got the following output. We just incorrectly uploaded the 1.8.6 part of your solution.

~/projects/rpcfn6 (master) $> ruby test_solution_acceptance.rb 01_RajeshTripathi full
***** FULL TEST REQUESTED *****
Loaded suite test_solution_acceptance
Started
FFFFF
Finished in 0.041508 seconds.

1) Failure:
test_basic1(FairQueueTest) [test_solution_acceptance.rb:21]:
expected but was
.

2) Failure:
test_basic2(FairQueueTest) [test_solution_acceptance.rb:41]:
expected but was
.

3) Failure:
test_basic3(FairQueueTest) [test_solution_acceptance.rb:52]:
expected but was
.

4) Failure:
test_basic4(FairQueueTest) [test_solution_acceptance.rb:72]:
expected but was
.

5) Failure:
test_basic5(FairQueueTest) [test_solution_acceptance.rb:78]:
expected but was
.

5 tests, 5 assertions, 5 failures, 0 errors

Reply

Rajesh February 22, 2010 at 10:16 am

Thanks for the clarification John, however this comment does not like anything between angular brackets < and > , so I cannot read expected results and output value

Reply

John Trupiano February 22, 2010 at 5:19 pm

Oh, ha. I didn’t notice that they were missing. In any case, I got the same output for 1.8.6 and 1.8.7.

Reply

Aleksey Gureiev January 26, 2010 at 5:15 pm

Hi guys,

I have a couple of questions.

1. I found that there’s a better solution (IMO) for the first test case: [[75, 30], [45, 24, 20, 15]]. As you can see, it loads the printers better (105 and 104 minutes), so the tasks will be completed faster and in a more balanced way. Am I missing something?

2. The distributions_are_equivalent method doesn’t account for situations when the result is equivalent, but not exactly the same. For example, (again) in the first case you can end up with either [[75, 24, 10], [45, 30, 20, 15]] or [[75, 20, 15], [45, 30, 24, 10]] (a quick hint is 75 = 45 + 30). So I modified the check to be dist1.map(&:total).sort == dist2.map(&:total).sort (where array.total is the sum of all elements) . Does it make sense?

Thanks.

Reply

Aleksey Gureiev January 26, 2010 at 5:51 pm

Pardon me my question #1. Lost that task with weight “10″ somewhere.

Reply

John Trupiano January 26, 2010 at 6:03 pm

Hi Aleksey,

I see you’ve answered your own query #1. As for your second question, you are correct. That is why test case #1 does not check for a specific distribution, only for a minimum time. Only tests cases 2, 4 and 5 check for specific distributions.

-John

Reply

Aldric Giacomoni January 27, 2010 at 1:48 am

Are we assuming that it takes no time whatsoever (or a negligible amount) to change from one job to another? Yes, yes, I know – I can read :) Clearly from the test spec, it looks like it.

Reply

John Trupiano January 27, 2010 at 5:35 am

Aldric, yes you are correct. We are assuming that it takes no time to change from one job to the next (though that would be a cool tweak to the problem).

Reply

Dominik Masur January 27, 2010 at 3:08 am

Solution (#2):

Dominik Masur, Germany
Works with Ruby 1.8
What i did:
1. Putting one big Job to all machines
2. Placing the small ones above
3. Trying to improve this solution
Please add me in the only for fun category.
Real nice task. Thank you!
Original: https://gist.github.com/0cab32802fbacd281b74 – now forked

Reply

Victor Goff February 21, 2010 at 9:42 am
John Trupiano February 22, 2010 at 7:02 am

Victor, this is another one that was affected by the strange 1.8.6 results. Re-running on my machine, the tests all pass.

Reply

John Trupiano February 22, 2010 at 7:39 am

Dominik,

While your submission does pass all tests provided, I find it difficult to navigate your code. I think it could benefit from a little method extraction. In any case, your submission is lightning fast. Congrats!

Thanks for participating.

Reply

Aleksey Gureiev January 27, 2010 at 1:16 pm

Solution (#3):

Aleksey Gureiev, Australia
Original: http://gist.github.com/287643 now forked
Code works with Ruby 1.8 and 1.9
A very simple algorithm based on incremental balancing of job queues. Initially, the first queue has all the jobs that are gradually distributed across available queues. The algorithm doesn’t take much memory since it does not involve the recursive traversing of the options tree and doesn’t store lots of intermediate data. Also, please note that it doesn’t take ages to calculate any of the examples. I believe it takes much less than a second to figure the solution for that heaviest sample.

Reply

Victor Goff February 21, 2010 at 9:42 am
Jeff Savin February 22, 2010 at 6:49 am

Code is logically organized and easy to read.

Reply

John Trupiano February 22, 2010 at 7:48 am

Aleksey, excellent solution. I see lots of clever bits here (notably the while loop in the initializer). I also like the logical organization of code into separate files.

It passes my undisclosed test cases. And it’s lightning fast!

Thanks for participating.

Reply

Aldric Giacomoni January 27, 2010 at 8:36 pm

Solution (#4):

Aldric Giacomoni, USA
Solution: http://gist.github.com/287179
Does not pass test case 4 – but it solves everything REALLY FAST.
Should work with >=1.8.7 and 1.9 but untested with 1.9 .

Reply

Victor Goff February 21, 2010 at 9:43 am
John Trupiano February 22, 2010 at 7:53 am

Aldric,

As you’ve noted, your submission is very fast but fails to solve test case number 4. I found your lighthearted code comments (and the exception raised when 0 presses are specified) enjoyable.

One note: you do not need to include Enumerable and Comparable into Press. The Array class already has included them for you.

Thank you for participating.

Reply

PhilK January 27, 2010 at 10:01 pm

Any idea what I’m doing wrong? My solution is currently running the test suite in 0.005915 seconds and passing everything.

I also tried it with a random set of 100 numbers between 0-99 and it still runs lightning quick (and comes out with all presses approx. equal). I’m sure I’m missing something but I’m not sure what it is.

Reply

John Trupiano January 28, 2010 at 7:20 am

Hi Phil, can you please create a gist with your solution? Without a reference point, I’m really not sure what the problem could be.

Additionally, providing a gist that shows your console session (running the test suite and the output) might be helpful for me.

Thanks.

Reply

Aleksey Gureiev January 28, 2010 at 8:35 am

Phil, you are not alone in this. :) Submitted my solution yesterday. Looks like it does the job and does it really fast.

Reply

John Trupiano January 28, 2010 at 8:44 am

Hi Phil, it looks like you’ve got a pretty clever solution. I think that I can write a test case that would fail, but am not positive. I’ll get back to you tomorrow after I’ve had a chance to review it more thoroughly.

Reply

Adam Lum January 28, 2010 at 2:03 am

Solution (#5):

Adam Lum, USA
Original: https://gist.github.com/8687e99c805775071738 (only used the test_solution_acceptance.rb test suite) now forked
Tested on both Ruby 1.8.7 and 1.9.1

Reply

Victor Goff February 21, 2010 at 9:44 am
Jeff Savin February 22, 2010 at 6:50 am

Nice try Adam. You are correct, it wasn’t the most elegant with the separate coding to handle different scenarios based on the number of presses the T-Shirt company owns, but you gave it a good shot and did accomplish the solutions.

Reply

John Trupiano February 22, 2010 at 7:57 am

Hi Adam,

While your submission does pass all provided test cases, it failed to pass my undisclosed test cases (which include some with more than 4 presses). Good to see you power through and meet the criteria as initially laid out though. You should check out the solutions for the folks that are selected as the winners. You’ll probably be able to learn a lot by reviewing their code.

Thank you for participating.

Reply

Brad O'Connor January 28, 2010 at 9:37 am

Solution (#6):

Brad O’Connor, Australia
Original: http://gist.github.com/288432 now forked
Code works with both Ruby 1.8 and 1.9 (but is about 3 times faster in 1.9!)

Wow, I think I’m learning. I didn’t expect to be coding problems like this when I started doing these RPCFNs. The first 2 were pretty easy but then #3 defeated me. I studied the solutions to #3 though and learned a lot about how to approach this sort of problem. #5 was difficult – took me days to produce a working solution. This seemed much easier to solve though – I managed it in a few hours while watching the tennis (on TV, not at the stadium!). Maybe it’s Roger Federer’s calming influence, or maybe I’m not only getting better at Ruby but actually learning a few things about computer science!

My solution takes about 60 seconds to run the tests on a 2.53GHz Macbook Pro with 4GB RAM (over 3 minutes if I use Ruby 1.8) so I suspect I have used an approach comparable to John Trupiano’s.

Thanks again for running these challenges. They are proving very worthwhile for me (and have given me enough Ruby-fu to get back to trying to make my Rails app work again).

Reply

Victor Goff February 21, 2010 at 9:44 am
Jeff Savin February 22, 2010 at 6:50 am

Brad, so glad to hear these RPCFNs are helping you. I feel the same way getting to read everybody’s unique solutions. Thanks for your entry which was documented to the point where I could understand your logic. You are one of a few who solved a fairly tough problem. :)

Reply

John Trupiano February 22, 2010 at 8:07 am

Hi Brad,

I’m also glad to hear that you’ve noticed improvement as you’ve completed each of the RPCFNs. I’m sure it feels great.

Your approach is pretty much exactly the same as the solution I came up with and it does in fact solve the undisclosed test cases that I had.

Great work! Thanks for participating. Good luck with that rails app :)

Reply

Cary Swoveland January 28, 2010 at 1:46 pm

Phil, you have given two objectives: #1) minimize the time required to print all the t-shirts; and #2) minimize the standard deviation of the times the presses are working. In general, no solution will be optimal for both objectives. Is #1 meant to be the primary objective, and #2 used only as a tie-breaker when there are multiple optima for #1? You said, “Test cases 1 and 3 have more than one acceptable distribution and as such I have not provided a specific distribution to test against.” By “acceptable” do you mean optimal for objective #1?

Reply

John Trupiano January 29, 2010 at 6:31 pm

Cary, yes #1 is the primary objective and #2 should be used as a tie-breaker. However, I’m not sure it matters. I’m of the belief that #1 is actually a byproduct of achieving #2. To be clear, the standard deviation is computed across the sums of the queues, not the individual jobs within the queues. And I would say “optimal” is a fine substitute for “acceptable.”

Reply

Cary Swoveland February 21, 2010 at 8:47 am

John,

I found an example that contradicts your suspicion that minimizing finish time (maximum job completion time) is equivalent to minimizing the variance (or standard deviation) of machine completion times:

jobs = [7.62,6.81,5.66,4.13,3.98,2.64,2.92,2.73]
number of presses = 5

If the objective is to minimize finish time (and, if there are multiple optima, select the one with minimum variance), we obtain the following optimal solution:

Optimal (smallest) maximum machine completion time = 8.29
Associated variance of job completion times = 0.933656
Machines->[jobs]
Machine 0->[0] time = 7.62
Machine 1->[1] time = 6.81
Machine 2->[2] time = 5.66
Machine 3->[3 4] time = 8.11
Machine 4->[5 6 7] time = 8.29

On the other hand, if the objective is to minimize variance, the optimal solution is:
Optimal (smallest) variance of job completion times = 0.339215
Associated maximum machine completion time = 8.3
Machines->[jobs]
Machine 0->[0] time = 7.62
Machine 1->[1] time = 6.81
Machine 2->[2 5] time = 8.3
Machine 3->[3 7] time = 6.86
Machine 4->[4 6] time = 6.9

The finish time is 0.01 better in the first case, but variance is smaller in the second.

The two objectives certainly tend to produce the same optimum. Indeed, I had to run quite a few problems before I found one that would provide the contradiction, and even then, the minimum variance solution’s finish time is only slightly worse than the minimum finish time.

Reply

John Trupiano February 21, 2010 at 5:50 pm

Great work Cary. When selecting the winner we will continue to use the original criteria (#1 is the objective, #2 is the tiebreaker).

Thanks for putting in so much effort!

Reply

Martin Linkhorst January 30, 2010 at 6:44 pm

Solution (#7):

Martin Linkhorst, Germany
Original: https://gist.github.com/9693f6996d461351437f now forked
Works with Ruby 1.8 and 1.9
Generates all possible distributions by splitting job list in distinct non empty subcollections with the help of Array’s combination method, then finds the best by comparing required time and standard deviation of each distribution

Reply

Victor Goff February 21, 2010 at 9:44 am
Jeff Savin February 22, 2010 at 6:51 am

Nicely commented and idiomatic code. Solid solution.

Reply

John Trupiano February 22, 2010 at 8:18 am

Martin,

Code is very well organized and idiomatic. The algorithm implemented is essentially the same as the one I did. Great work!

Thanks for participating.

Reply

CGI January 31, 2010 at 9:49 am

Solution (#8):

Ilya Ermolin, Russia
Original: https://gist.github.com/e7917cd523f3c1eddb32 now forked
Tested on Ruby 1.8.6
It’s realy my fist script in Ruby, was very interesting to solve it…

Reply

Victor Goff February 21, 2010 at 9:45 am
Jeff Savin February 22, 2010 at 6:51 am

Nice job. Code was a little hard to read, more meaningful variable names would help quite a bit. For first script though, you did an excellent job solving a tough problem.

Reply

John Trupiano February 22, 2010 at 8:27 am

Hi Ilya,

Do you come from a C background? The code reads like it :)

Anyway, lightning fast solution that passes all tests (including my undisclosed suite).

Thanks for participating.

Reply

Elijah Miller February 7, 2010 at 6:33 pm

Solution (#9):

Elijah Miller, USA
Original: http://gist.github.com/297449 now forked
Code works with Ruby 1.8 at least
Looks like I might have the same fast solution. It seem very likely that there are test cases it fails, but it passes all the the given tests in about about 0.005 seconds.

Reply

Victor Goff February 21, 2010 at 9:45 am
Jeff Savin February 22, 2010 at 6:52 am

Very nice solution. Short and sweet and very fast. Code was easy to read. Nice addition of sum to Enumerable.

Reply

John Trupiano February 22, 2010 at 8:34 am

Fastest solution I’ve seen thus far! Great work Elijah.

The code is extremely succinct and passes my undisclosed test cases as well.

Thank you for participating.

Reply

Guillaume Petit February 9, 2010 at 3:00 pm

Solution (#10):

Guillaume Petit, France
Original : https://gist.github.com/3e3b45010e8fae7c7d9b now forked
Works with ruby 1.8.7

Reply

Victor Goff February 21, 2010 at 9:45 am
Jeff Savin February 22, 2010 at 6:52 am

Codewise, solution was very short and simple and very easy to read. Great job.

Reply

John Trupiano February 22, 2010 at 8:38 am

Guillaume, this is the most straightforward solution I’ve seen yet. Definitely blows my solution out of the water. Great work!

Thanks for participating.

Reply

Benoit Daloze February 22, 2010 at 5:53 pm

Your solution looks really great, short and simple :)

I couldn’t resist to fork it and to make it on my way:
https://gist.github.com/a2ccccc0fbcfccd6d0f5

I mainly edited find_place_for to make it, I think, even more readable. I added also a ‘puts :ideal’ to see when the ideal is met.

Looks like you’ve got some feeling to use the @ideal_balance. In fact that wouldn’t work with small sets, but then adding jobs where there is the less is enough.

I’m curious if this would work for others examples, but as we don’t have and it’s not that easy to make, I would say you got the best (Rubyish) solution, according to me !

Reply

Guillaume Petit February 22, 2010 at 7:21 pm

Short and simple was an important objective for me with this problem, so I am glad you liked it ! Besides, this approach brought me some interresting learnings about Ruby.

Regarding the @ideal_balance, I did not start with it; my first attempts passed some tests but not the others. And this variable was the key to my struggle =)

Thanks for your feedback !

Reply

Rajesh February 22, 2010 at 9:39 pm

This is definitely a good solution, but it cant solve all cases. if it can then you can prove P = NP :)

here is a failing test case

jobs = [7, 7, 6, 6, 5, 5, 4, 4, 4, 1]
number_of_processes = 4

exp_max = 13

Reply

John Trupiano February 23, 2010 at 6:30 pm

Rajesh, you are correct. Despite passing all of our test cases, Guillame’s solution is incomplete.

I should have caught this during my review and unfortunately we have awarded the prizes already. It was my mistake that I missed this during the review.

I want to acknowledge Elijah as the runner up from my review. I believe that Satish will also be awarding him a prize (I’ll let him fill everyone in on the details).

My apologies for the mistake during review. Thanks again to all of the participants. I had a great time running the challenge.

Guillaume Petit February 23, 2010 at 8:09 pm

Well, that proves my approach was a bit too naive.

Beware of “simple” codes =)

Aurélien Bottazini February 23, 2010 at 8:26 pm

@John Trupiano

Here is an interesting test case:
jobs = [1.23, 2.23, 1.03, 0.57, 0.89, 0.1, 0.3, 1.23, 1.45, 1.7]
number_of_presses = 4

Elijah solution gives:
[[0.57, 2.23], [0.3, 1.23, 1.23], [0.1, 1.03, 1.45], [0.89, 1.7]]
with a time required of 2.8

but there are better solutions for example:
[[0.57, 0.89, 1.23], [0.1, 0.3, 2.23], [1.03, 1.7], [1.45, 1.23]]
with a time required of 2.73

Jacob Hodes February 22, 2010 at 11:52 pm

This is great, it’s so interesting to see all the varied approaches!

Guillaume, your solution is really elegant. However it seems it might fail for cases where the two largest elements belong in the same bucket. Unless I’m missing something, which is also possible/likely. :)

For example, if jobs=[10,9,6,6,6] and num_presses=2, the optimal distribution would be [[10,9], [6,6,6]], but this approach produces [[10,6], [9,6,6]].

Reply

Marc Minneman February 14, 2010 at 12:44 pm

Solution (#11):

Marc Minneman, USA
Original: git@gist.github.com:dd49a0d0a6a045602cb7.git Now forked
Optimal solution is discovered using a k-ary search tree that implements a greedy heuristic.
Code works with Ruby 1.8

Reply

Victor Goff February 21, 2010 at 9:46 am
Jeff Savin February 22, 2010 at 6:53 am

Marc implemented Korf’s Complete Greedy Algorithm which passed all tests. Code was commented appropriately. Were a couple things I was unsure of such as use of Marshal.load(Marshal.dump()). Nice job.

Reply

Marc Minneman February 22, 2010 at 8:46 am

Each child node in the search tree constructs a distribution of print jobs based on work accomplished by the parent. With the “clone” method, the child nodes were altering (unintended side-effect) the data passed to it by the parent causing the unit tests to fail.

I did some googling and found a similar problem documented here:

http://stackoverflow.com/questions/2039251/is-there-a-simple-way-to-duplicate-a-multi-dimensional-array-in-ruby

The solution was to use the “Marshal.load(Marshal.dump())” technique. I too felt this was a hack, but couldn’t figure out a better way to make a complete copy.

Any advice you can offer would be greatly appreciated!

Reply

Brad O'Connor February 22, 2010 at 2:12 pm

Hey, that was my stackoverflow question! I asked it to help with one of the previous challenges. Great to see it helped someone else out. I agree that it seems very hacky but I’ve been unable to find a better way. I think it’s just a consequence of Ruby not supporting multidimensional arrays natively.

Reply

Marc Minneman February 22, 2010 at 6:48 pm

Brad — I owe you a big thanks for posting the question in the first place. I was really stuck and the solution offered got me over the hump.

Victor, Jeff & John — Thank you for evaluating my code and offering your comments. These challenges have been a great learning experience!!!

John Trupiano February 22, 2010 at 8:43 am

Hi Marc,

The algorithm appears to be implemented correctly (passes undisclosed test cases). The aesthetics of your code could be much cleaner (and Ruby-esque). You might be able to pick up a few pointers from some of the other submissions. Lastly, the #dup method could replace your use of Marshal.load(Marshal.dump(partitions)).

Good job with the algorithm. Thanks for participating.

Reply

Cary Swoveland February 15, 2010 at 11:05 pm

Solution (#12):

Cary Swoveland, Canada
Original: https://gist.github.com/9ca2fb9922270bada4e7 now forked
I’m using Ruby 1.8.7, on a Mac.
Participants in this challenge might be interested to know that this problem can be formulated as an “mixed integer program”, and then solved with any of several MIP packages available (some free). (I think John had this in mind when he stipulated that no external GEMS are to be used, though, technically, one could work around that by communicating with a MIP package thorough files.) The MIP formulation has binary variables Xjm, which equal 1 if job j is assigned to machine m, and 0 otherwise, and one continuous variable, f, the completion time of all machines. The objective (function) is minimize f. If we define J as the set of jobs, M as the set of machines and Tj as the time required by job j, the (linear) constraints are as follows:
SUM(m in M) Xjm = 1, for each j in J (each job is assigned to one machine)
f >= SUM(j in J) TjXjm, for each m in M
My submission, incidentally, is a standard tree search.

Reply

Victor Goff February 21, 2010 at 9:46 am
Cary Swoveland February 21, 2010 at 12:21 pm

What a bonehead mistake I made!! My solutions were correct, but I (incorrectly) put the optimal job assignments, rather than the associated job times, in the distribution array. For test_basic2, for example, the test results error message was: “Distributions not equivalent: : [[1.0, 4.75], [2.83, 3.5], [1.1, 4.4], [5.8]] not equivalent to [[4], [0, 1], [3, 6], [2, 5]].” The former are the job times of the optimal job assignments; the latter are my optimal job assignments. Groan.

Reply

Jeff Savin February 22, 2010 at 6:53 am

I did like the statistical printout capabilities as well as the verbose comments describing your thought process. Nice try Cary.

Reply

John Trupiano February 22, 2010 at 8:53 am

Cary, clearly you’ve put a lot of work into this and it’s a shame that your output wasn’t of the required format.

It is clear that your solution is correct though because the minimum time is tested prior to the distributions in those particular tests. It runs lightning fast and solves all of my undisclosed test cases. Keep in mind that you have access to the test cases ahead of time. You could have been running the tests cases throughout the build of your solution.

Thanks for participating.

I look forward

Reply

Aurélien Bottazzini February 16, 2010 at 5:00 am

Solution (#13):

Aurélien Bottazzini, France
Original: http://gist.github.com/305120 now forked
Code tested with Ruby 1.8.6-p388, 1.8.7-p249 and 1.9.1-p378

Reply

Victor Goff February 21, 2010 at 9:46 am
Jeff Savin February 22, 2010 at 6:54 am

This solution did take a while to run on the third test — longer than most I tested. The solution was also code-verbose, but did do the job. Nice entry.

Reply

John Trupiano February 22, 2010 at 9:06 am

Aurelien,

Your solution did pass all tests (including my undisclosed suite). Nice work! If I’m not mistaken the dup_distrib function could have just been replaced will a call to #dup. I also found it somewhat unnatural to split the methods between class and instance methods considering there were no other intended external consumers of the FairDistribution class.

Thanks for participating.

Reply

Aurélien Bottazini February 22, 2010 at 2:50 pm

For the class methods, To be honest I hesitated but since for example my self.standard_deviation method does not depend on a particular instance to run, I find it clearer to declare it as a class method.
It is like a reminder for myself (and for readers I hope): Hey this is an utility method!

and no unfortunately the dup_distrib function can not be replaced with a simple #dup. Arrays deep copy tend to be tricky in ruby :(

Thanks a lot for taking the time to review my program :)

Reply

John Trupiano February 22, 2010 at 5:18 pm

Yeah, there’s nothing wrong with making those utility methods class methods. In fact, it could be argued that it’s more appropriate because they do not depend on any state. It might have been more idiomatic to place those methods into a module and then mix it into your FairDistribution class.

Reply

Aurélien Bottazini February 22, 2010 at 5:46 pm

ah yes, I like the module approach.

I will try that next time :)

Benoit Daloze February 20, 2010 at 1:18 am

Solution (#14):

Benoit Daloze, Belgium
Original: https://gist.github.com/43c82d5127d5d05ebe2e now forked.
Code works with Ruby 1.9 (because of with_object)

Reply

Victor Goff February 21, 2010 at 1:05 pm
Jeff Savin February 22, 2010 at 6:54 am

The code itself was nice. I liked Benoit’s extension of the Array class, adding a sum, standard deviation, time and times methods. Nice solution.

Reply

John Trupiano February 22, 2010 at 9:08 am

Benoit,

Great work, this solution runs very quickly and passes the entire test suite (including my undisclosed test cases). I liked your trick at the bottom of the file to run a test case if the file itself was invoked (I do this quite often).

Thank you for participating.

Reply

Jacob Hodes February 20, 2010 at 1:53 pm

Solution (#15):

Jacob Hodes, USA
Original: https://gist.github.com/a460231c78f2a90180ab
Works with Ruby 1.8; untested on 1.9

Reply

Victor Goff February 21, 2010 at 1:06 pm
Jeff Savin February 22, 2010 at 6:54 am

Nice solution. Great extension of the Array class allowing resulting fair distribution code to be fairly light. Easy to read with nice comments.

Reply

John Trupiano February 22, 2010 at 9:13 am

Jacob,

Good work. It’s great that you’re taking cues from someone like Jay (as noted in your comments). I also thought it was noteworthy that you thought to alias #time_required with #max_bucket_sum. Seems you have a good handle on general programming principles as well as some of the specifics of the Ruby language.

Thanks for participating.

Reply

Jacob Hodes February 22, 2010 at 11:31 pm

Hi John, thanks for the feedback! I really enjoyed the quiz and learned a ton.

I wonder if you’d agree with Jay’s recommendation to use attributes instead of instance variables throughout a class’s methods? At first my code looked like this:

num_usable_buckets = @num_buckets > @values.length ? @values.length : @num_buckets

but after coming across his argument for refactoring, I created methods that wrapped the instance variables, relegating them to the role of “implementation detail of an attribute”, if I understand this stuff correctly. So now the code is:

num_usable_buckets = num_buckets > values.length ? values.length : num_buckets

Very small difference, of course, but I’m curious what you and others think of this approach. Thanks again!

Reply

John Trupiano February 23, 2010 at 6:33 pm

Jacob, in my own experience I tend to follow Jay’s recommendation of using attributes for exactly that reason. When I first design a class, it might seem unlikely that my “implementation” of an attribute is accurate (as simply an instance variable). But as the class grows and becomes more complex, that definition may become less accurate. By having an attribute, it’s very easy to refactor without having to change any of your unit tests.

btw, this is the same pattern that attr_reader, attr_writer and attr_accessor encourage. They provide your traditional getter/setter methods that you see in other languages.

Reply

Cary Swoveland February 27, 2010 at 4:50 am

Jacob,

As someone new to both Ruby and OOP, I found your program interesting and instructive. I have a few questions. I was surprised to see “clone” (line 23) and “map” (37) with no arguments. I made what I thought was a reasonable assumption: if a method’s object is not specified, it is to be “self”. Sure enough, when I replaced “clone” with “self.clone” and “map” with “self.map”, your program ran no differently. Then I shortened “self.each” to “each” in line 46, and again, it made no difference. Am I correct that “self” is assumed when a method’s object is not specified, and if so, when, if ever, is it considered good practice to include “self.” before the method?

Secondly, I do not understand why you do not need “@values” (as in line 72), rather than “values” (and @num_buckets rather than “num_buckets”), in line 100. I thought “values” would be regarded as a local variable to average_bucket_sum (and there is no method, “values”). I tried it both ways, but the inclusion of “@” made on difference.

Though not a Ruby question, I was wondering why you chose an objective different than the one given in the challenge. Considering that you enumerated all solutions, it would have been just as easy to find the one with the smallest maximum machine time (and, if there were a tie, find the one among them with the smallest variance).

By constructing the set of all solutions, then finding the best among them, as you have done, you would quickly run out of memory for larger problems (that have M^J/M! combinations, for M machines and J jobs). Here’s a challenge (perhaps an NP-complete one): is there a way to loop through all the possible combinations without constructing all of them first (and without repeating permutations, e.g., if you’ve examined [[2,1], [4,3]] you would not examine [[4,3], [2,1]], [[2,1], [3,4]] and so on)?.

Reply

Jacob Hodes March 10, 2010 at 9:32 am

Hi Cary, sorry so long in reply, and thanks for your comments.

Yes, in most cases, self is the implicit receiver of a method call. I hesitate to say all cases, because I’m quite a newbie myself.

(Rubyists tend to use that word, “receiver,” which reflects the language’s Smalltalk influence, and its idea of “sending messages” rather than “invoking methods”. This threw me off for quite awhile.)

In general, it seems idiomatic Ruby prefers to have the receiver be implicit if it’s self. Private methods can’t have any explicit receiver, including an explicit self, so it makes a difference there. And when defining methods, adding self makes a big difference. Within MyClass, “def my_method” would define an instance method, while “def self.my_method” would define a class method.

The most helpful resource I’ve found on this stuff, covering all the fundamentals of Ruby’s object model, is Dave Thomas’s screencast series: http://www.pragprog.com/screencasts/v-dtrubyom/the-ruby-object-model-and-metaprogramming . Yehudah Katz’s blog posts are great, too.

Re: line 100, yes, I could have used the instance variables @values and @num_buckets, and in most intros to OOP I think that would be the recommended approach. But I chose to follow Jay Fields’s advice (link is in the code comments) to not make direct use of instance variables throughout a class’s methods. Rather, I’m wrapping these instance variables in getter methods. The getter is written out as a method in the case of @average_bucket_sum. For @values and @num_buckets, I’m using the shorthand declaration attr_reader :values, :num_buckets to get my getter methods on the cheap.

I didn’t give much thought to the issue of whether the two objectives might not be equivalent. I chose to go with the smallest variance option, as that seemed to reflect the spirit of “fair” distribution. The machines can go slightly longer as a whole, in the interests of solidarity. :)

I like the idea you pose at the end. I’ll give it a shot when I have some time.

Reply

Cary Swoveland March 10, 2010 at 11:30 pm

Jacob, thank you for answering my questions about method receivers and the use of “self”, and references to instance variables. With regard to the latter, I had thought “attr_reader” merely provided a getter for use outside the class definition (since the variable, preceded with “@”, is available within the class directly), but have since recognized the getter can be used within the class as well (and, as you point out, that may be preferred). I’ll have a look at Dave Thomas’ screencast series. I’m finding two books very helpful: Peter Cooper’s “Beginning Ruby” and the “Ruby Cookbook”. Getting there…

Reply

Leave a Comment

{ 24 trackbacks }

Previous post:

Next post: