RPCFN: Ruby**Fun (#4)

by on November 26, 2009

Ruby Programming Challenge For Newbies

RPCFN: Ruby**Fun (#4)

By Michael Kohl

About Michael Kohl

Michael KohlMichael Kohl (Twitter / blog) in his day job, works as an IT systems engineer in Vienna, Austria. He fell in love with Ruby in 2003 or so, maintained various Ruby-related packages for Gentoo Linux from 2004-2006 and started being an assistant teacher for RubyLearning.org in early 2009. Besides all things Ruby his interests include mathematics, literature, travelling, foreign languages, (functional) programming languages (e.g. Clojure, Haskell), chess and so much more that he really wishes he wouldn’t need to sleep.

Michael has this to say about the challenge:

The best way to learn programming is to write code! Ruby is fun because it’s easy to achieve results and I really believe that the RPCFN shows new Rubyists how much they can accomplish with relatively little Ruby. Thinking about a problem and then being able to compare your own solution to dozens of others is a lot of fun and a great opportunity for learning, so make sure to take part in these challenges! The reason that I picked this particular challenge is that it’s easy to solve, but requires a bit of thinking to get a somewhat attractive solution.

Sponsors

Chargify

This monthly programming challenge is sponsored by Chargify and O’Reilly Media.

Chargify simplifies recurring billing for Web 2.0 and SaaS companies. Build innovative web applications without worrying about how to bill your customers. Whether you’re a start up or an established business billing thousands of customers a month, Chargify works for you.

Access customer insight, revenue, signups, and cancellation trends right from your real-time dashboard, helping you focus on what’s important – your company’s growth. Get started for FREE to Chargify your business today.

O'Reilly Media

O’Reilly Media spreads the knowledge of innovators through its books, online services, magazine, and conferences. Since 1978, O’Reilly has been a chronicler and catalyst of leading-edge development, homing in on the technology trends that really matter and spurring their adoption by amplifying “faint signals” from the alpha geeks who are creating the future. An active participant in the technology community, the company has a long history of advocacy, meme-making, and evangelism.

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 O’Reilly Media’s Ebook bundle.
  • The person with the second 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 four persons who win, can’t win again in the next immediate challenge but can still participate.

The Ruby Challenge

RPCFN

You just started working for CoolNewCompany which is developing mathematics related software. Since you are new to the team, your boss gives you an easy task to test your abilities. Write a class that pretty-prints polynomials, following some simple rules:

  • if a coefficient is 1, it doesn’t get printed
  • if a coefficient is negative, you have to display something like “- 2x^3″, not “+ -2x^3″
  • if a coefficient is 0, nothing gets added to the output
  • for x^1 the ^1 part gets omitted
  • x^0 == 1, so we don’t need to display it

Here’s a couple of usage examples:

puts Polynomial.new([-3,-4,1,0,6]) # => -3x^4-4x^3+x^2+6
puts Polynomial.new([1,0,2]) # => x^2+2

Don’t concern yourself too much with error handling, but if somebody tries to create a polynomial with less than 2 elements, your program has to raise an ArgumentError with the message “Need at least 2 coefficients.”

Please check the provided unit tests for more examples and make sure to use them for verifying your solution!

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 Dec. 2009 (Indian Standard Time). No new solutions will be accepted from 21st Dec. onwards.
  • On 21st Dec. 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 Dec. 2009. 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. Gimi Liang, China – declared winner (randomly selected)
  2. William Yanez, Venezuela
  3. Christiaan Van den Poel, Belgium
  4. Tom Stuart, U.K.
  5. José Sazo, Chile
  6. James Daniels, USA
  7. Pedro Diogo, Portugal
  8. Felipe Elias Philipp, Brazil
  9. Fabio Kreusch, Brazil
  10. Milan Dobrota, Serbia
  11. Jefferson Mariano de Souza, Brazil
  12. Aldric Giacomoni, USA
  13. Michael Lang, USA
  14. Rohit Arondekar, India
  15. Bill Sullivan, USA
  16. Jorge Dias, Spain
  17. Alexander Klink, Germany
  18. Chris Jones, USA
  19. Aurélien Bottazzini, France
  20. Ali Al-Sahaf, Saudi Arabia – declared winner (randomly selected)
  21. John McDonald, USA
  22. Aleksey Gureiev, Ukraine – declared winner (best solution)
  23. Fred Fordham, Australia
  24. Tony Chen, USA
  25. Rohit Sasikumar, India
  26. Paul Harrington, USA
  27. Aashish Kiran Chittimilla, India
  28. Benoit Daloze, Belgium
  29. Steve Wilhelm, USA
  30. Marc Minneman, USA
  31. Othmane Benkirane, Morocco
  32. Oleksandr Manzyuk, Ukraine
  33. Pankaj Sisodiya, India
  34. Oliver, UK
  35. Sérgio Silva, Portugal
  36. Isley Aardvark, USA
  37. Rémy Coutable, France
  38. Brad O’Connor, Australia
  39. Suraj Dhakankar, India
  40. Sunny Dackie, India
  41. Philippe Antras, France
  42. Amr Tamimi, Palestine
  43. Sriram Varahan, India – declared winner (second best solution)

Just for Fun

  1. James Daniels, USA
  2. Phil, Germany

The Winners

Winners

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

Previous Challenge

RPCFN: Short Circuit (#3) by Gautam Rege.

Update

  • This challenge is now closed. Michael Kohl has a working solution to this problem. This is not a “perfect” or the sole “correct” solution, but just one way of doing it.
  • 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

{ 155 comments… read them below or add one }

Rainer November 26, 2009 at 7:53 am

Ouch! Polynomials… it was oh so long ago :)
Ok, so the input arguments is just a list of coefficients, and there is only one variable.
Can i assume the coefficient is always a constant whole number? No fractions?

Reply

Michael Kohl November 26, 2009 at 11:56 am

Yeah, only one variable and for simplicity’s sake coefficients are whole numbers.

Reply

James Daniels November 26, 2009 at 9:11 am

I’m curious about the behavior specified in the test_all_zero test, since such behavior was not specified in the challenge statement.

Reply

Michael Kohl November 26, 2009 at 12:01 pm

Good catch, that’s a mistake in the unit test and will be corrected ASAP, thanks!

Reply

Gimi Liang November 26, 2009 at 9:43 am

Solution (#1):

Original: git://github.com/243239.git
Forked: http://gist.github.com/243744
It’s been tested on both Ruby 1.9.1 and Ruby 1.8.7.

Reply

Michael Kohl December 20, 2009 at 2:54 pm

The code passes all my tests, but it’s not very elegant.

Reply

Peter Crawford December 20, 2009 at 2:56 pm

I liked this one for its simplicity – maybe not elegant, but you “get it” with just a glance.

Reply

Jeff Savin December 20, 2009 at 2:57 pm

I didn’t see anything wrong with this code, but then, maybe I’m not very elegant either, lol. Interesting use of the block on the to_s redefinition. Code passed everything I threw at it so I’m happy.

Reply

Gimi Liang December 21, 2009 at 9:20 am

I updated my code. http://gist.github.com/243239
How do you think about this new version? I mean if you guys have time to give it a glance.
I’m doing this just for fun. Attending this kind of contest gave me lots of fun! I watched, compared my resolution with others and thought about it. It’s simple but still I learnt a lot from it. Thanks for organizing this activity!
P.S. Maybe not elegant, but I still like my original resolution for its clarity and simplicity. :)

Reply

wyanez November 26, 2009 at 10:25 am

Solution (#2):

William Yanez, Venezuela
Original: https://gist.github.com/ee7c19625e97aa96a78f
Forked: https://gist.github.com/b6130293d147a859105d

Reply

Michael Kohl December 20, 2009 at 3:00 pm

This passes all my tests, but the code could be more elegant (it’s possible to solve this with less if’s). Not bad though! :-)

Reply

Jeff Savin December 20, 2009 at 3:02 pm

This code also passed everything I threw at it, although I do have to agree with Michael on this one about the lack of elegance. However, pretty concise code and it works!

Reply

Peter Crawford December 20, 2009 at 3:06 pm

Compact, easily understood, nothing tricky, does the job.

Reply

Michael Kohl November 26, 2009 at 12:06 pm

There is mistake in the unit tests which Satish will fix ASAP: test_all_zero should be “0″, not “0=0″. Don’t worry though, while evaluating the solutions I will take my mistake into consideration, so both are valid answers. Sorry for the confusion!

Reply

Christiaan November 26, 2009 at 5:15 pm

Solution (#3):

Christiaan Van den Poel, Belgium
Original: http://gist.github.com/243419
Forked: http://gist.github.com/243426
Code works with: Ruby1.8 (not tested with ruby1.9)

Reply

Peter Crawford December 20, 2009 at 3:07 pm

My favorite so far, easy to read, nicely commented.

Reply

Michael Kohl December 20, 2009 at 3:07 pm

A quite nice and idiomatic solution, although personally I find the hash a bit overkill.

Reply

Jeff Savin December 20, 2009 at 3:08 pm

I concur. Nice and readable code and passed it all.

Reply

Tom Stuart November 26, 2009 at 6:14 pm

Solution (#4):

Tom Stuart, U.K.
Original: https://gist.github.com/4fa0e8892c7fdc8b745c
Forked: https://gist.github.com/88c1bff42791d944104a
Code works with Ruby 1.8

Reply

Jeff Savin December 20, 2009 at 3:09 pm

There’s not just a lot in the initialization, there’s everything. So, no, it isn’t the most concise and prettiest solution, but it does work. Only thing I noticed in the tests was with this:

Polynomial.new([0, 0, 0, 0, 100]) returned: +100 expected: 100

Not a big deal, but different than some of the other results.

Reply

Michael Kohl December 20, 2009 at 3:09 pm

This is the most verbose solution so far. It’s not bad, but quite a bit of code for this simple challenge.

Reply

Peter Crawford December 20, 2009 at 3:10 pm

Agree with Michael. There’s an awful lot happening in the just the initialization…

Reply

José Sazo November 27, 2009 at 12:23 am

Solution (#5):

José Sazo, Chile
Original: https://gist.github.com/b568e5676518ee91d2a1
Forked: https://gist.github.com/b4f03272a3657357c25b
Code tested with 1.9.1. The code should work well with 1.8 (adapting the testing code though)

Reply

Jeff Savin December 20, 2009 at 3:11 pm

Not the shortest solution in the world but reads nicely. And, yet another solution that passes every one of my tests. Nice job overall.

Reply

James Daniels November 27, 2009 at 3:40 am

Solution (#6):

James Daniels, USA
Original: http://gist.github.com/243697 (added some additional tests)
Forked: http://gist.github.com/243742
Ruby 1.8.7 tested

Reply

Jeff Savin December 20, 2009 at 3:12 pm

Definitely the most compact code so far and very elegant. Passed all of my somewhat tricky tests except one as stated below:

Polynomial.new([1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0]) should result: x^15+x but instead gave: x5+x

Reply

Michael Kohl December 20, 2009 at 3:12 pm

The first solution that is going in the direction of what I hoped to see, my clear favorite so far. :-)

Reply

Peter Crawford December 20, 2009 at 3:12 pm

Wow! talk about compact. I like it too.

Reply

James Daniels December 21, 2009 at 12:31 pm

Damn, missed the multi-digit coefficients! Glad you guys like it, I wanted to steer as clear from conditional logic as possible.

Reply

Pedro Diogo November 27, 2009 at 4:05 am

Solution (#7):

Pedro Diogo, Portugal
Original: https://gist.github.com/e146009c5254054bf462
Forked: https://gist.github.com/34ed91c24fe6bb1b09d8
Code works on Ruby 1.8 and Ruby 1.9
Description: Iterates every coefficients on the input array and performs a different set of actions in a fixed order depending on the coefficient value. Saves every action to an output string

Reply

Peter Crawford December 20, 2009 at 3:13 pm

I like this one for its simplicity.

Reply

Michael Kohl December 20, 2009 at 3:13 pm

Short and to the point, not bad.

Reply

Jeff Savin December 20, 2009 at 3:14 pm

Passed each of my tests. Pedro wanted a simple and readable solution and he achieved his goal. While this isn’t the shortest solution we’ve seen, it still ranks in the concise category to me. Good job.

Reply

Felipe Elias Philipp November 27, 2009 at 6:26 am

Solution (#8):

Felipe Elias Philipp, Brazil
Original: https://gist.github.com/5a9a61b7577b9f649d19
Forked: https://gist.github.com/4a4faf8e984208025ac6
Code works with Ruby 1.8

Reply

Jeff Savin December 20, 2009 at 3:14 pm

Another easy to read approach that falls on the shorter side. Passed all of my tests except:

Polynomial.new([0, 0, 0, 0, 100]) where it yielded +100 instead of just 100. I liked this overall.

Reply

Peter Crawford December 20, 2009 at 3:18 pm

A similar approach to Pedro Diogo’s, but lacks the simplicity.

Reply

Rohit Arondekar November 27, 2009 at 12:35 pm

Should an input like [0,0,1,5,6] result in
x^2+5x+6 or +x^2+5x+6
?

Reply

Michael Kohl November 27, 2009 at 2:34 pm

Like in mathematics you wouldn’t display a leading + sign, only a leading minus. E.g.

[1,2,3] => x^2+2x+3
[-1,2,-3] => -x^2+2x-3

Reply

Fabio Kreusch November 27, 2009 at 5:36 pm

Solution (#9):

Fabio Kreusch, Brazil
Original: https://gist.github.com/83803a1e14e7837f6ab5
Forked: https://gist.github.com/6b417f881f7ab3094867
Code tested with 1.8

Reply

Peter Crawford December 20, 2009 at 3:18 pm

Well, each method does exactly one thing, but the overall approach seems to me overkill for this particular problem.

Reply

Jeff Savin December 20, 2009 at 3:19 pm

I agree with Peter on this. A lot of methods and in my opinion, a bit on the unnecessary side. Gets the job done though and passed all my tests except the questionable one that appears to trip some up:

Polynomial.new([0, 0, 0, 0, 100]) resulting in +100 instead of just 100.

Reply

Milan Dobrota November 27, 2009 at 5:59 pm

Solution (#10):

Milan Dobrota, Serbia
Original: git@gist.github.com:8d577949ebc21b06d9e7.git gist-8d577949
Forked: https://gist.github.com/5b8b7c511047805c9087
Code tested with ruby 1.8.6

Reply

Peter Crawford December 20, 2009 at 3:19 pm

Perhaps initialization should be separated out from the core method. The solution is simple, but inelegant with all the “elsifs”.

Reply

Jeff Savin December 20, 2009 at 3:20 pm

Again Peter is right on. The initialize method contains a clunky series of elsifs. The length of the code isn’t bad and it reads okay, but could be more elegant. Failed on one of my tests:

Polynomial.new([1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0]) resulted in x^15+1x and should’ve been x^15+x.

Reply

Aldric Giacomoni November 27, 2009 at 5:59 pm

You say…
“if a coefficient is negative, you have to display something like “- 2x^3?, not “+ -2x^3?”
But all your tests show “-2x^3+4x^2-x+5″
So does our pretty print include spaces or not?

Reply

Michael Kohl November 28, 2009 at 3:38 pm

The spaces were only the to emphasize what I mean, the output does not contain spaces. Questions like this one are very easy to answer by looking at the provided test cases by the way :-)

Reply

Aldric Giacomoni December 4, 2009 at 9:31 pm

I asked specifically BECAUSE the test cases and the description of the problem were in disagreement.
There was a mistake in your test cases before I wrote this. Who is to say there wasn’t another one?
Who am I to assume that I know which of the two explanations you wrote is correct?

Reply

Michael Kohl December 5, 2009 at 6:41 am

I’d say “when in doubt, make the test pass”. That’s why I said I will take the 0=0 vs. 0 into account for everybody who submitted before the test got corrected.

Reply

Jefferson Mariano de Souza November 27, 2009 at 6:30 pm

Solution (#11):

Jefferson Mariano de Souza, Brazil
Original: https://gist.github.com/1b708fbdaa60c199b870
Forked: https://gist.github.com/dda5b5a613653a44218e
Confirmed Ruby 1.9

Reply

Jeff Savin December 20, 2009 at 3:21 pm

Jefferson’s solution passed all my tests (with the exception of the nitpicky puts Polynomial.new([0, 0, 0, 0, 100]) which outputs a +100 instead of 100). Contains another clunky elsif construct similar to the previous entry but at least doesn’t have it in the initialize method. Code readability and comments could be elevated a bit more.

Reply

Aldric Giacomoni November 27, 2009 at 6:40 pm

Solution (#12):

Aldric Giacomoni, USA
Original: http://gist.github.com/244023
Forked: http://gist.github.com/244320
Passed all of the unit tests as of 8:40 am EST on Nov. 27.
Should work on 1.8 and 1.9, but untested on 1.9 .

Reply

Jeff Savin December 20, 2009 at 3:21 pm

Solution passed all tests except for my most nit picky one where the result in my mind should be 100 but yielded +100. Code could have been written to be a more concise solution, but overall a good job.

Reply

Peter Crawford December 20, 2009 at 3:21 pm

Could be more compact, but gets the job done.

Reply

Michael Lang November 28, 2009 at 3:02 am

Solution (#13):

Michael Lang, U.S.A.
Original: https://gist.github.com/229d5b7d68ae7c3ebe78
Forked: https://gist.github.com/01fe546d4e7e93323413
Code works with Ruby 1.8

Reply

Jeff Savin December 20, 2009 at 3:22 pm

Michael, thanks for the great introduction to your solution. You did indeed achieve your design goals of terseness and readability. I agree with you 100% on good commenting and enjoyed your solution, which passed every one of my tests, even a couple tricky ones. Well done, one of my favorites.

Reply

Peter Crawford December 22, 2009 at 6:52 am

Great commenting, great breakdown of the problem into methods, great solution.

Reply

Rohit Arondekar November 28, 2009 at 7:46 am

Solution (#14):

Rohit Arondekar, India
Original: http://gist.github.com/244051
Forked: http://gist.github.com/244356
Code works with Ruby 1.8

Reply

Jeff Savin December 20, 2009 at 3:23 pm

Rohit’s solution passed each of my tests with flying colors. So, well done. However, there was quite a lot of code used to achieve these results as such, was a little harder to follow. Would’ve been nice to see a more compact solution.

Reply

Rohit Arondekar December 20, 2009 at 5:35 pm

I was trying to make it extensible. I guess I over did it. :D

Reply

Peter Crawford December 22, 2009 at 6:53 am

Ditto Jeff’s comment about the compactness – if that can be achieved while keeping it easy to understand what the code is doing…

Reply

Bill Sullivan November 28, 2009 at 8:02 pm

Solution (#15):

Bill Sullivan, USA
Original: http://gist.github.com/244539
Forked: http://gist.github.com/244711
Code works with: Ruby 1.8 (not tested on 1.9)

Reply

Jeff Savin December 20, 2009 at 3:23 pm

With 8 if’s and 7 elsif || else’s, it wasn’t the most idiomatic or easy to follow solution. Having said that, the solution passed each and every one of my tests, which means the job got done. Going behind to make any changes might be a nightmare as I think I would get lost in the nested if’s and indents which looked like the map of a coastline. :)

Reply

William Sullivan December 24, 2009 at 5:46 am

I tried to take your points into account and rewrote a solution. Any other comments would be greatly appreciated. :)

http://gist.github.com/244539

Reply

Peter Crawford December 22, 2009 at 6:54 am

I’m afraid this didn’t read like Ruby to me – rather too… procedural? Nothing wrong with that, however if the problem were significantly longer, we might find ourselves in trouble fast…

Reply

William Sullivan December 24, 2009 at 5:47 am

I’d be happy to read any comments you have on this new solution I wrote. It’s much shorter, and hopefully easier to maintain. :)

http://gist.github.com/244539

Reply

Jorge Dias November 30, 2009 at 12:42 am

Solution (#16):

Jorge Dias, Spain
Original: http://gist.github.com/245025
Forked: http://gist.github.com/245163
The code works with ruby 1.8 and ruby 1.9, although I couldn’t run the unit tests on ruby1.9, but did the tests in the console.
The solution is very simple, I created a class so each term knows how to display itself. A class was created to handle the degree of each term.
Also added some unit tests for my own classes

Reply

Jeff Savin December 20, 2009 at 3:24 pm

Not sure what I’m doing wrong, but I get this error in 1.8:
polynomial.rb:14:in `to_s’: wrong argument type Symbol (expected Proc) (TypeError)

However, code again has an overused combination of case’s and if, elsif’s that make it not the easiest to read. Adding to the lack of readability is not one comment.

Reply

Peter Crawford December 22, 2009 at 6:54 am

An interesting exercise in nesting classes, but there are more straight-forward ways to solve this particular problem.

Reply

Alexander Klink November 30, 2009 at 1:57 am

Solution (#17):

Alexander Klink, Germany
Original: https://gist.github.com/51aba4f26a37a3c8207e
Forked: https://gist.github.com/2eb3e419c644fdf8814c
The code works with both Ruby 1.8 and 1.9.

Reply

Jeff Savin December 20, 2009 at 3:24 pm

Interesting. I liked the idea of adding the sign method to the Fixnum class. Solution passed all of my tests and was sprinkled with informative comments. Not the shortest solution, but a nice one.

Reply

Michael Kohl December 20, 2009 at 3:25 pm

A pretty nice solution, I like it :-)

Reply

Peter Crawford December 22, 2009 at 6:55 am

Original and out of the box.

Reply

Chris Jones November 30, 2009 at 4:39 am

Solution (#18):

Chris Jones, USA
Original: http://gist.github.com/243922
Forked: http://gist.github.com/245165
Code only tested with 1.8

Reply

Michael Kohl December 20, 2009 at 3:25 pm

Nice and concise, well done.

Reply

Jeff Savin December 20, 2009 at 3:25 pm

Very compact solution. Although there were no comments, the amount of code was so small and readable, this is one of the few times where adding comments wouldn’t have added a significant amount. One nitpick: solution produced a +100 instead of just 100 with the Polynomial.new([0, 0, 0, 0, 100]) test I ran.

Reply

Aurélien Bottazzini November 30, 2009 at 8:37 pm

Solution (#19):

Aurélien Bottazzini, France
Original: https://gist.github.com/fd3cbcf2f8296363cfb9
Forked: https://gist.github.com/363400bbb74423c054f1
Code works with Ruby 1.8 & 1.9

Reply

Jeff Savin December 20, 2009 at 3:27 pm

Tested it in Ruby 1.8 and got an error:
ruby polynomial.rb
polynomial.rb:5:in `initialize’: undefined method `count’ for [1, -2, 3, -4, 5, -6]:Array (NoMethodError)
from polynomial.rb:53:in `new’
from polynomial.rb:53
Exit code: 1

Changing coefficients.size to coefficients.count fixed that problem.

After that slight change, the code worked with the exception of producing a +100 instead of 100 when I passed it Polynomial.new([0, 0, 0, 0, 100]). A fairly compact solution and easily readable.

Reply

Aurelien December 21, 2009 at 3:21 pm

which version of ruby 1.8 are you using Jeff?

I am using ruby 1.8.7 (2009-06-12 patchlevel 174) [i486-linux]
and I don’t have the error you are talking about.
But I would be interested in knowing your version :)

Reply

Aurelien December 21, 2009 at 3:39 pm

and even strangier here is the official ruby documentation:
http://ruby-doc.org/core-1.8.7/classes/Array.html#M000333

:S

However looking at ruby 1.8.6 documentation I don’t see the count method for Array.
So I would guess you have an older version of ruby 1.8.7 than mine. And that older version does not have the count method for the Array class.

Reply

Jeff Savin December 21, 2009 at 10:44 pm

You were right on. I’m using 1.8.6. Nice sleuthing.

Reply

Ali Al-Sahaf December 1, 2009 at 3:36 am

Solution (#20):

Ali Al-Sahaf, Saudi Arabia
Original: https://gist.github.com/9ceb60fa43049089d3fd
Written and tested in 1.8 but should work fine in 1.9

Reply

Jeff Savin December 20, 2009 at 3:28 pm

Not the most concise, but I liked it. Nicely commented and passed all tests. Good solution.

Reply

John McDonald December 2, 2009 at 12:09 am

Solution (#21):

John McDonald, USA
Original: https://gist.github.com/fa4809213e9dc81a4861
Forked: https://gist.github.com/41a140d8e04206ba5221
Code works with Ruby 1.8 / 1.9

Reply

Jeff Savin December 20, 2009 at 3:28 pm

I really liked this solution. Very well commented and a small amount of code that I found to be logically constructed and therefore easy to read. Too bad failed one of my tests:
Polynomial.new([0, 0, 0, 0, 100]) produced 0+100 instead of just 100.

Reply

Aleksey Gureiev December 2, 2009 at 12:48 pm

Solution (#22):

Aleksey Gureiev, Ukraine
Original: http://gist.github.com/247026
Forked: http://gist.github.com/247055
Code works with Ruby 1.8 / 1.9 / Both: 1.8, should probably be “Both”
The idea is to map coefficients to the parts of polynomial and then join them with the plus sign, then fix the edge cases with negatives. There was no test for the case when there’s ’1′ at the position of the last coefficient, so I added it.

Reply

Jeff Savin December 20, 2009 at 3:29 pm

Definitely one of my favorite solutions. Well-written and easy to read, very concise. Passed all tests, even the nit-picky ones!

Reply

Michael Kohl December 20, 2009 at 3:29 pm

Nice, I liked this one!

Reply

James Daniels December 2, 2009 at 4:41 pm

Solution (#23):

James Daniels, USA
Original: http://gist.github.com/243697
(refined “second” submission for fun)
Felt inspired, cleaned out all conditional logic :0) All sprintf and regular expressions.

Reply

Michael Kohl December 20, 2009 at 3:30 pm

I’m surprised that this is the first RegEx-based solution, that’s bonus points for you ;-)

Reply

Jeff Savin December 20, 2009 at 3:30 pm

Short and sweet. Only problem is, similar to first solution, fails on coefficients larger than two digits:

Polynomial.new([1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0]) should produce x^15+x instead of x5+x. Probably a quick change with the sprintf formatting though. Nice solution.

Reply

Fred Fordham December 2, 2009 at 4:57 pm

Solution (#24):

Fred Fordham, Australia
Original: https://gist.github.com/f7cbbd4e3331a514091f
Forked: https://gist.github.com/7204619efdbaa411adb2
Code works with Ruby 1.8 / 1.9

Reply

Jeff Savin December 20, 2009 at 3:30 pm

Not the shortest solution, but passed all tests with the exception of:
Polynomial.new([0, 0, 0, 0, 100]) producing a +100 which seems to trip up some of the programs. Comments helped readability but code could’ve been more compact.

Reply

Jefferson Mariano de Souza December 3, 2009 at 1:20 am

Is it possible to send more than one solution?
For example, I sent one and then I changed my mind, on second thought I’d do it in another way. Is it possible?

Reply

Satish Talim December 3, 2009 at 6:20 am

You can submit more than one solution, but it will go into the “Submitted for Fun” category. The original solution is immediately forked and sent for evaluation to the panel.

Reply

Tony Chen December 3, 2009 at 6:34 am

Solution (#25):

Tony Chen, USA
Original: git@gist.github.com:e65c9d70c9bf2861726e.git
Forked: https://gist.github.com/231eb7fac57d36870d66
Ruby 1.8 (only tested on 1.8)

Reply

Jeff Savin December 20, 2009 at 3:31 pm

Not the most elegant or concise, but gets the job done. Failed only on the Polynomial.new([0, 0, 0, 0, 100]) which produced a +100 instead of 100.

Reply

Rohit Sasikumar December 3, 2009 at 4:58 pm

Solution (#26):

Rohit Sasikumar, India
Original: https://gist.github.com/b71ef391f2977f3e5796
Forked: https://gist.github.com/06de2f666ba01ef72d2a
Code works with Ruby 1.8

Reply

Jeff Savin December 20, 2009 at 3:31 pm

Perfectly passed all my tests, even some that tripped up a number of other solutions. Fairly well commented.

Reply

Paul Harrington December 4, 2009 at 11:33 am

Solution (#27):

Paul Harrington, USA
Original: https://gist.github.com/2a226c257e76f159f970, passes https://gist.github.com/280aa4797a580fb8ae75
Forked: https://gist.github.com/b80176579fb53fbce4a5
I use symbols probably too much, I hate Ruby’s garbage collection I guess (or I shouldn’t drink + code)
Works with 1.8 & 1.9

Reply

Jeff Savin December 20, 2009 at 3:32 pm

Had an issue trying to run this in 1.8. Got an error:

polynomial.rb:14: empty symbol literal
polynomial.rb:18: empty symbol literal
…eff_str = coeff.abs == 1 ? :”" : coeff.abs.to_s # don’t disp…
^
polynomial.rb:19: empty symbol literal
…tr = exp > 1 ? “^#{exp}” : :”" # don’t display the exponent …
^
polynomial.rb:20: empty symbol literal
… var = exp > 0 ? :x : :”" # the first term is a constan…
^
>Exit code: 1

Reply

phil December 4, 2009 at 2:21 pm

Solution (#28):

Phil, Germany
Original: git://gist.github.com/248921.git
Forked: http://gist.github.com/248929
Only tested with Ruby1.8
I don’t consider myself a newbie so this is a JUST FOR FUN submission.

Reply

Jeff Savin December 20, 2009 at 3:35 pm

Phil’s solution was short and sweet but needs a little work to provide the expected output. Too bad, a little testing and tightening up would’ve made this a definite contender.

The main error was not removing the “1″ coefficients. So:
Polynomial.new([1, -2, 3, -4, 5, -6]) produced 1x^5-2x^4+3x^3-4x^2+5x-6. So, the leading “1″ should have been removed. This same thing happened with each of my tests. Another minor failure was outputting a blank instead of 0 for Polynomial.new([0, 0, 0]).

Reply

aashish.kiran December 4, 2009 at 11:45 pm

Solution (#29):

Aashish Kiran Chittimilla, India
Original: git@gist.github.com:d061fc428e5f7fcdb66b.git
Forked: https://gist.github.com/c6e9418b5712e239be01
Code works with Ruby 1.8 and 1.9

Reply

Jeff Savin December 20, 2009 at 3:36 pm

Unfortunately, this entry had a number of flaws.
1) raise ArgumentError, ‘Need at least 2 coefficients.’ unless args.length > 2. This code raises an error with two coefficients. Should have been args.length > 1

2) Polynomial.new([6, 5]) outputs 6x^1+5 which should be 6x+5. Every other test case I ran, of course, failed in this same way.

3) Program output blank instead of 0 with Polynomial.new([0, 0, 0]).

4) Polynomial.new([0, 0, 0, 0, 100]) outputs +100 instead of 100.

Reply

Benoit Daloze December 5, 2009 at 11:52 pm

Solution (#30):

Benoit Daloze, Belgium
Original: https://gist.github.com/234ebf02c3d723913355
Forked: https://gist.github.com/400492a2e4a4a966497f
Works with both 1.8 and 1.9
My solution use Enumerable#inject to build the String,
with every “monomial” splitted in 3 parts : sign, coefficient and variable. Simple and elegant !

Reply

Jeff Savin December 20, 2009 at 3:36 pm

Benoit describes his program as simple and elegant and I must agree. Concise code and passed every one of my tests. My only complaint, is this program wasn’t as readable as some other ones and some comments would’ve helped.

Reply

Benoit Daloze December 22, 2009 at 12:55 am

Jeff Savin : “My only complaint, is this program wasn’t as readable as some other ones and some comments would’ve helped.”

I did comment very less, but I think my program is very readable anyway, maybe not at the first time you read it, you need to see it globally.
Each line is almost easy to translate in english:

return ’0′ if @coef.all? { |c| c == 0 } # that’s clear
(0…@coef.length).inject(“”) { |s, i| # let’s build a String
coef, pow = @coef[i], @coef.length-1-i # and let’s find our power and coef
if coef == 0
s # we don’t add anything
else
s +
(coef > 0 ? ‘+’ : ‘-’) + # sign # that’s clear
(coef.abs == 1 && pow != 0 ? ” : coef.abs.to_s) + # coef: print only if |coef| != 1 and power != 0(because we need then to print it)
(pow < 2 ? 'x'*pow : "x^#{pow}") # var # th's clear
end
}.sub(/^\+/, "") #remove the first + if any

Reply

Jeff Savin December 22, 2009 at 8:07 am

Hi Benoit. I do totally agree with you that your program was simple, elegant and best of all, it worked perfectly. I scored your program very high, which incidentally made it to my top three. When I said it wasn’t as readable as others, I was being very nit picky. If I were to look line by line at your code, of course, it makes sense and is readable. I guess going one step further, and this could just be my preference, would be a couple comments thrown in explaining things. Sometimes quickly glancing at a program, even though we know Ruby, reading comments helps.

Thanks for your great entry and hope to see your code in the future competitions.

Jeff

Reply

swilhelm December 6, 2009 at 6:52 am

Solution (#31):

Steve Wilhelm, USA
Original: https://gist.github.com/e2a0d08f8d620db9581a
Forked: https://gist.github.com/de5c8b0c34a06b9052ba
Code works with Ruby 1.8.7

Reply

Jeff Savin December 21, 2009 at 8:30 am

Running 1.8.7 I got the following error:

>ruby polynomial.rb
polynomial.rb:18:in `each_with_index': no block given (LocalJumpError)
from polynomial.rb:18:in `to_s'
from polynomial.rb:38:in `puts'
from polynomial.rb:38
>Exit code: 1

Not sure if its something that came over strange in the cut and paste?

Reply

Steve December 21, 2009 at 11:30 am

I downloaded the zip file from https://gist.github.com/de5c8b0c34a06b9052ba, and ran the contents on my iMac running Snow Leopard. Below is the result:

$ ruby -v
ruby 1.8.7 (2008-08-11 patchlevel 72) [universal-darwin10.0]
$ ruby gistfile2.rb
Loaded suite Polynomial_Test
Started
.....
Finished in 0.000663 seconds.

5 tests, 6 assertions, 0 failures, 0 errors

Reply

Jeff Savin December 21, 2009 at 11:09 pm

My mistake, I’m running Ruby 1.8.6. This seems to be the same problem I was running into with Oleksandr Manzyuk, as mentioned below. He states that each_with_index without a block returns an Enumerator and requires 1.9. I will look further into this.

Reply

Steve December 22, 2009 at 9:03 am

I know the winners have been chosen, but I would appreciate it if you could find the time to run your tests and review my submission. Thanks in advance.

Michael Kohl December 22, 2009 at 12:44 pm

Steve, I tested your solution, and it was pretty nice. Unfortunately there can only be one winner in such a competition, and this time around it was Aleksey.

Reply

mminneman1 December 7, 2009 at 12:33 am

Solution (#32):

Marc Minneman, USA
Original: https://gist.github.com/182e2568c4e8a920e5b1
Forked: https://gist.github.com/53da49329871173b3405
Code works with Ruby 1.8

Reply

Jeff Savin December 21, 2009 at 8:31 am

Marc created a number of simple one-line methods which all get called in one-line to output the final polynomial. I found this solution to be very easy to read and it passed each and every one of my tests. Nice job!!

Reply

Mariam December 7, 2009 at 6:26 pm

As a newbie :) I have a problem concerning ruby look @ this code

def initialize(coeff)
@coeff =coeff
end
n = @coeff.length

this error appears “undefined method `length’ for nil:NilClass (NoMethodError)”
I think this is cuz there is no indication that @coeff is an Array
how can I solve this problem ?
thanks in advance

Reply

Steve December 8, 2009 at 12:36 pm

The problem is the fact that the line ‘n = @coeff.length’ is not part of (or scoped to) a method. It is part of the class definition.

As as a result, it is being evaluated by Ruby before the initialize method is being called.

As a hint, you might want to look at section 7.1.4 ‘Defining a to_s Method’ in Flanagan & Matsumoto’s book ‘The Ruby Programming Language’

Reply

Rhyhann December 7, 2009 at 10:39 pm

Solution (#33):

Othmane Benkirane, Morocco
Original: http://gist.github.com/250920
Forked: http://gist.github.com/251335
Code works with Ruby 1.8

Reply

Jeff Savin December 21, 2009 at 8:32 am

Othmane’s solution passed each of my tests which is a great start. While he did provide initial comments at the beginning of the program, the code itself wasn’t commented which detracted from the overall readability. I could’ve used some comments as I found the code, which wasn’t that concise, to be a bit hard to follow. I did like Othmane’s addition of the sign method to the Integer class. Still love that facility in Ruby. :) Nice job over all.

Reply

Pankaj Sisodiya December 8, 2009 at 4:58 pm

Solution (#35):

#35 Pankaj Sisodiya, India
Forked: https://gist.github.com/c519fccdc1e6b2f7a3eb

Reply

Jeff Savin December 21, 2009 at 8:33 am

With only 17 lines of code and four of that being whitespace, I initially thought this was one of the more compact solutions. I was tricked though ;) Pankaj used a couple of semicolons and put whole if elsif then constructs on one line, in my opinion, making the code even harder to read. I encountered some problems with the output as well where in each case there was a leading “+” and the x^1 wasn’t displayed as just “x”. Example:

Polynomial.new(1, -2, 3, -4, 5, -6) yielded: + x^5 – 2x^4 + 3x^3 – 4x^2 + 5x^1 – 6.

Reply

Peter Crawford December 22, 2009 at 6:44 am

I agree with Jeff – best to split up those enormously long lines. Makes it hard to read and, worse, hard to write…

Reply

Oleksandr Manzyuk December 9, 2009 at 12:51 am

Solution (#34):

Oleksandr Manzyuk, Ukraine
Original: https://gist.github.com/f117a2a9671ba964e664
Forked: https://gist.github.com/7877d8c0e89049eae3ab
Tested with Ruby 1.9, but should work with Ruby 1.8, too.
Brief description: Given an array of coefficients [c_0, c_1, ..., c_n], form an array of pairs [[c_0, n], [c_1, n-1], …, [c_n, 0]] (using each_with_index), drop pairs [c_i, i] for which c_i is 0 (using reject). If there are no pairs left, the result is the zero polynomial; otherwise, format each term c_ix^i appropriately (dropping c_i if it is -1 or 1, but leaving it in the constant term), join all the terms interspersing them with “+” (using join), and replace every occurrence of “+-” with “+”.

Reply

Jeff Savin December 21, 2009 at 8:33 am

Unfortunately, I get error when running:

>ruby polynomial.rb
polynomial.rb:11:in `each_with_index': no block given (LocalJumpError)
from polynomial.rb:11:in `to_s'
from polynomial.rb:41:in `puts'
from polynomial.rb:41
>Exit code: 1

Reply

Oleksandr Manzyuk December 21, 2009 at 2:07 pm

My fault — it does require Ruby 1.9. each_with_index without a block returns an enumerator.

Reply

Jeff Savin December 21, 2009 at 11:05 pm

Yes, I’ve been running my tests in 1.8. Will make the switch one of these days. Some of the other evaluators I know are using 1.9.

Reply

Oliver December 9, 2009 at 9:37 pm
Jeff Savin December 21, 2009 at 8:34 am

Oliver’s solution passed all my tests except for outputting +100 (should be 100) when passed Polynomial.new([0, 0, 0, 0, 100]). It seemed a bit of overkill on the code with 2 classes and over 10 methods to achieve these results. A more compact solution would’ve been nicer.

Reply

Sérgio Silva December 11, 2009 at 12:24 pm

Solution (#37):

Sérgio Silva, Portugal
Original: https://gist.github.com/8a3c28f2907ccffb8cc8
Forked: https://gist.github.com/5cc1278b4b0da0d0b0e0
Code works with Ruby 1.9, didn’t test 1.8
Hopefully this works, I just got back on track, saw the contest a few hours ago and put this solution up. I haven’t used ruby for a looong time, so it’s probably not the cleanest way :p

Reply

Jeff Savin December 21, 2009 at 8:35 am

Sergio’s entry was nicely done. While maybe not the most idiomatic way of doing things, the code was very compact, nicely commented to where even I could follow the logic, and produced stellar results by passing each and every one of my tests. Definitely a contender!!

Reply

Isley Aardvark December 13, 2009 at 12:07 am

Solution (#38):

Isley Aardvark, USA
Original: https://gist.github.com/5902f4034b47a012665c
Forked: https://gist.github.com/a3b4aa8429fe1eb0f045
Code works with Ruby 1.8 definitely, 1.9 probably (I am a newbie, after all.)

Reply

Jeff Savin December 22, 2009 at 6:45 am

Nice solution Isley. Short, sweet, easy to read and well commented. But, gotchya! Failed one of my tests:

Polynomial.new([1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0]) yielded x5+x which should’ve been x^15+x

Reply

Isley Aardvark December 23, 2009 at 7:57 am

Thanks, this has been educational. I ended up redoing it once again to make things even clearer, and to assuage my SIWOTI syndrome. (It’s particularly bad when the “Someone” is yourself.) https://gist.github.com/7ed1ea920808eab59537

Reply

Rémy COUTABLE December 13, 2009 at 10:16 pm

Solution (#39):

Rémy Coutable, France
Original : https://gist.github.com/8ae81a95bce84f418258
Forked: https://gist.github.com/6312b883023893b671e1
Code works with Ruby 1.8 : Yes
1. Reversing the coefficients array to access it like that : coefficients[power] instead of : coefficients[coefficients.size - power - 1].
2. Building the string representing the polynomial with steps from the max power to the 0 power.

Reply

Jeff Savin December 22, 2009 at 6:47 am

Not as elegant as some of the solutions I’ve seen, but Remy’s code passed each of my tests. Good job.

Reply

Brad O'Connor December 15, 2009 at 5:34 am

Solution (#40):

Brad O’Connor, Australia
Original: http://gist.github.com/256590
Forked: http://gist.github.com/256620
Code works with Ruby 1.8 and Ruby 1.9 but your provided test is only valid for 1.8 as far as I can tell

Reply

Jeff Savin December 22, 2009 at 6:47 am

Program incorrectly spewed “Need at least 2 coefficients” when passed Polynomial.new([6, 5]). Quick change from if coeffs.length <= 2 to if coeffs.length < 2 fixed problem. Other than that, Brad's solution passed each of my tests and was one of the more readable compact solutions. Very nice job.

Reply

Suraj Dhakankar December 15, 2009 at 9:42 pm

Solution (#41:)

Suraj Dhakankar, India
Original : https://gist.github.com/7a6ea014f0dc5758068a
Forked: https://gist.github.com/a31231e48756ebe411dd
Code works with Ruby 1.8 / 1.9

Reply

Jeff Savin December 22, 2009 at 6:48 am

Suraj’s entry wasn’t bad. Ample comments helped the readability of the code, which otherwise was a tad on the harder side to follow. Suraj’s program passed all of my tests with the exception of one, where a reverse method got the better of him.

Polynomial.new(1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0) => x^51+x (should’ve been x^15+x)

Reply

Sunny Dackie December 17, 2009 at 11:58 am

Solution (#42):

Sunny Dackie, India
Original: http://gist.github.com/258571
Forked: http://gist.github.com/259888

Reply

Jeff Savin December 22, 2009 at 6:49 am

Sunny’s code was very readable and commented nicely. Passed all tests except one. Alas, another reverse method gone haywire.

Polynomial.new([1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0]) => x^51+x (should be x^15+x)

Reply

pantras December 18, 2009 at 1:04 am

Solution (#43):

Philippe Antras, France
Original: https://gist.github.com/43bdd25b93c2ac7f663b
Forked: https://gist.github.com/bff18a180fe17a731074
Code works with Ruby 1.8 / not tested on 1.9
Thx for the challenge, it’s a piece of fun.

Reply

Benoit Daloze December 22, 2009 at 12:27 am

Hi,
I worked to compare all the solutions with:
http://github.com/eregon/RPCFN4/blob/master/my_comparator.rb

LOC: lines of codes
LOL: average length of line
CHARS: basically all the chars without counting spaces (\s)
TESTS: see the files tests.rb, it’s all the tests I saw on this page. F = failure, E = Error
To see what number is which test, see tests.rb

The is the output: (sorting by tests and then chars(characters))
http://github.com/eregon/RPCFN4/blob/master/my_comparator.out.txt

I had to edit some of the files.
I made them 1.9 friendly,
removed the puts instead of the string returned
and some other strange stuffs to make everyone pass at least one test.

So, surprisingly, my solution is first^^
Well, I don’t pretend this is neutral, it’s clearly based on the length of the code. I Love small solutions (and if you want a really big one look at http://github.com/eregon/math/blob/master/math/polynomial.rb and http://github.com/eregon/math/blob/master/math/monomial.rb).

Anyway, I think than passing all tests is something good (some fail because of using Float.. well they should have define ‘sign’ on Numeric ;) and many because of too much signs/1)
So I think the best solution is one of:

LOC| LOL |CHARS | TESTS
20 | 19.6 | 333 | OK : Benoit Daloze
29 | 16.6 | 424 | OK : Oleksandr Manzyuk
23 | 28.4 | 511 | OK : Pedro Diogo
50 | 14.3 | 639 | OK : Philippe Antras
37 | 21.0 | 700 | OK : Remy Coutable
39 | 20.2 | 708 | OK : Jose Sazo
49 | 16.9 | 755 | OK : Ali Alsahaf
53 | 16.7 | 770 | OK : Rohit Arondekar

Reply

Jeff Savin December 22, 2009 at 6:50 am

Philippe, nice job. All tests passed cleanly, so that’s a great start. Code wise, a bit on the longer side and not the most beautiful I have seen for this contest, but I liked the flow and your comments. Keep it up.

Reply

Leave a Comment

{ 24 trackbacks }

Previous post:

Next post: