RPCFN: Cycle Tracks (#12)

by Satish Talim on July 31, 2010

Ruby Programming Challenge For Newbies

RPCFN: Cycle Tracks (#12)

By David Griffiths

Today, we complete one year of Ruby Programming Challenge for Newbies. RubyLearning is grateful to all the Ruby experts and participants who have actively helped make these challenges interesting and popular.

About David Griffiths

David Griffiths In David’s own words: “I’m an agile developer, writer and trainer based in the UK. I used to write a monthly Java development column and I’ve used and taught agile methods to companies around the UK. But I’ve been writing code since I was 12 years old. I worked with Java from the alpha release in the 90s. A lot of things on the client side as well as a lot of enterprise stuff. But everything changed for me when I got an early copy of Bruce Tate’s Up and Running with Ruby on Rails. I found myself in Boston for 3 days with nothing else to do. And anyone who’s been to Boston knows that it’s famous for two things: coffee and book shops. So I got a copy of Tate’s book and a laptop and spent three days burying myself deep into Rails and consuming more caffeine than was probably wise. It was incredible. Here was a way of doing things with a few simple commands, that would have taken 19 classes, an enterprise container and 3-400 lines of XML in Java. An old professor once told me “The profound is always simple” – and Rails was the living embodiment of that. I was hooked. It really hasn’t been the same since.”

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.
  • 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.

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

The Ruby Challenge

RPCFN

The Challenge

The entire challenge details are available here.

Ensure that you submit both the solutions – see pages 2 and 3.

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 29th Aug. 2010 (Indian Standard Time). No new solutions will be accepted from 30th Aug. onwards.
  • On 30th Aug. 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 5th Sept. 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:

  • David Griffiths.
  • GitHub, for giving us access to a private repository on GitHub to store all the submitted solutions.
  • The RubyLearning team.

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. Alex Chateau, Latvia
  2. Kirill Shchepelin, Russia
  3. Sebastian Rabuini, Argentina
  4. Santosh Wadghule, India
  5. Juan Gomez, USA
  6. Julio C. Villasante, Cuba
  7. Paul McKibbin, UK
  8. Viktor Nemes, Hungary

Just for Fun

  1. Dmytrii Nagirniak, Australia
  2. Benoit Daloze, Belgium
  3. Cary Swoveland, Canada

The Winners

Winners

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

Previous Challenge

RPCFN: The Game of Life (#11) by Elise Huard.

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 (#13) challenge by Bruce Scharlau, U.K. is scheduled for Sept. 2010.

Technorati Tags: , , , , ,

Posted by Satish Talim

{ 37 comments… read them below or add one }

Alex Chateau July 31, 2010 at 4:48 pm

Solution (#1):

Alex Chateau, Latvia
http://gist.github.com/502083
Two versions (1.9 / Both)

Reply

David Griffiths August 30, 2010 at 2:34 pm

Two very nice solutions from Alex. I really can’t see how the 1.9 version could be any shorter. Because the guys from the Head First Lounge didn’t specify the version of Ruby they were using, Alex has wisely introduced a very neat and workable solution that also works with 1.8. Nice use of evaluation/assignment as well as double assignment.

I think we have a winner…. :-)

Reply

k1ller July 31, 2010 at 7:39 pm

Solution (#3):

Kirill Shchepelin, Russia
git@gist.github.com:9d7e0590c8b703eec2a7.git
Quite simple solution of the problem.

Reply

David Griffiths August 30, 2010 at 2:34 pm

Nice, short solution from Kirill. Like some other entrants he made use of the push/shift stack methods available in Ruby. Treating the array as a stack can drastically shorten the solution.

Unfortunately, it doesn’t deal with negative values, which will be a real bear for those nights in the lounge when the guys will want to replay the hits from Sinatra’s Coo-Coo Songbook…

Reply

Dmytrii Nagirniak July 31, 2010 at 9:01 pm

Solution (#4):

Dmytrii Nagirniak, Australia
https://gist.github.com/5839ce80ec96f4d38c84
Code works with Ruby 1.8.7.
Just for Fun category

Reply

David Griffiths August 30, 2010 at 2:35 pm

Very nice use of the methods that make Ruby arrays behave as stacks. These methods greatly reduce the amount of code you need to solve the problem. He also included code to ensure that people could skip backwards through a playlist. Something that not every entrant did. Sadly it wasn’t quite short enough to win, but nicely written code nevertheless.

Reply

Sebastian Rabuini August 1, 2010 at 12:14 am

Solution (#5):

Sebastian Rabuini, Argentina
https://gist.github.com/ce5754502af2f3976054
Code works with 1.8 (not tested in 1.9 yet)

Reply

David Griffiths August 30, 2010 at 2:36 pm

This was a great solution. I think the shortest solution that will work on 1.8. There are a couple of space optimizations I can see. You could handle the negative case with:


def skip_tracks(arr, i)
(i%arr.size).times {arr.push(arr.shift)}
end

The modulo-expression would turn those nasty negatives into a matching positive. And if you use a little syntactic sugar you can trim a little more off:


def skip_tracks(arr, i)
(i%arr.size).times {arr<<arr.shift}
end

Reply

Santosh Wadghule, India August 1, 2010 at 10:59 am

Solution (#6):

Santosh Wadghule, India
https://gist.github.com/87e8af9701674adf72e9

Reply

David Griffiths August 30, 2010 at 2:36 pm

Santosh, sadly I couldn’t get the code to work. When I pasted it in and ran it, it appeared to always return the original playlist.

Reply

Juan Gomez August 3, 2010 at 10:34 am

Solution (#7):

Juan Gomez, USA
http://gist.github.com/82a9d079380f2648bc0c
Code works with Ruby 1.9

Reply

David Griffiths August 31, 2010 at 6:17 am

Not sure what happened with this one. When I go to the link it just says “testing…” :-(

Reply

Juan Gomez August 31, 2010 at 7:06 am

I wrote my entry on the blog, but it never appeared and I checked the challenge a few days after I posted and my name was NOT on the challenge list, so I supposed you have rejected me or something and since I never received an email or anything (until late last night) I never uploaded any code

Reply

Satish Talim August 31, 2010 at 7:09 am

Juan, really sorry for this. Better luck next time.

Reply

Juan Gomez September 4, 2010 at 7:46 am

This challenge was nice because it made me realize that I really want to learn Python instead of Ruby, I got into this challenge to try to learn Ruby but unfortunately didn’t understand how it worked so I miss my chance to participate, but when I discovered that all you needed to solve this problem in python was this:
def skip_tracks(arr, i):
return arr[i:] + arr[:i]
I fell in love with the language.
PD: this code works even in the very old versions of Python ;-)

Cary Swoveland September 4, 2010 at 9:18 am

Juan,

It looks like Python solutions will be welcome for future programming challenges, so I hope you will continue to participate. As I recall, there was a problem with your submission because you provided the “Private Clone URL” (at gist.gethub ) when you submitted your solution. Be assured you are by no means the first to make that mistake. What is needed–as I expect you now know–is the URL you are taken to after clicking “Create Private Gist”.

Cary

Reply

Julio C. Villasante August 3, 2010 at 6:07 pm

Solution (#8):

Julio C. Villasante, Cuba
https://gist.github.com/b3cda446e3432e8cb34b
Tested in ruby 1.9, should work in 1.8
Not much to say about this one… (didn’t like it very much actually)

Reply

David Griffiths August 31, 2010 at 6:17 am

Yes – that works. Nice use of the stack-like methods of lists in Ruby. There were shorter versions, but this is a nice implementation.

Reply

Paul McKibbin August 9, 2010 at 3:30 pm

Solution (#9):

Paul McKibbin, UK
https://gist.github.com/de84d4a517c49ef1feac
Code tested with 1.8.7 and 1.9.1

Reply

Paul McKibbin August 30, 2010 at 2:24 pm

Oops. Just realised that my file names don’t quite match up, since I was fiddling with multiple versions and missed the fact I’d renamed a couple of files before uploading. Should be fairly obvious, but you may want to line 4 in “skip_tracks_favourite.rb” from

require ‘skip_tracks_favourite.rb”

to

require “skip_tracks”

Reply

Paul McKibbin August 30, 2010 at 2:25 pm

That will of course only change the tests, and not the code.

Reply

Paul McKibbin August 30, 2010 at 9:21 pm

although there is a bug in the code, since the test should be if o!=0 rather than just if o….

Reply

David Griffiths August 31, 2010 at 6:18 am

Doh! I had such great hopes for this one. It’s a really, really compact solution, optimizing for size in accordance with the challenge. Unfortunately it appears to fail in a few cases, such as:

a = ['a', 'b', 'c']
skip_tracks(a, 3)

Reply

Paul McKibbin August 31, 2010 at 1:25 pm

Yes. That’s why the o!=0 was required. Serves me right for coding on strong painkillers. :)

Reply

Cary Swoveland August 12, 2010 at 8:22 am

Cool challenge, David! I trust you don’t code like that in real life.

Reply

Benoit Daloze August 28, 2010 at 8:35 pm

Solution (#10):

Benoit Daloze, Belgium
Entered just for fun.
https://gist.github.com/3d33581c2e367168c335
Code works with: Both
I am simply using parallel assignment with Array slices (and some modulo stuff to accepts all integers as argument). My tests are not so good as they repeat a lot the logic of the method, but I did not want either to write 20 examples by hand. I could not figure out how to make the magnets version working.

Reply

David Griffiths August 31, 2010 at 6:18 am

Yes – that works quite nicely. With careful use of the modulo function and the indexes of the array, it could have been made quite a bit shorter.

Reply

nemesv August 29, 2010 at 12:31 pm

Solution (#11):

Viktor Nemes, Hungary
git@gist.github.com:4b87ad5e2e7ad303ffcd.git
Code works with Ruby 1.9

Reply

David Griffiths August 31, 2010 at 6:19 am

This was a really lovely solution. With a little trimming it actually comes down to the nicely condensed:

def skip_tracks(a,i)w=i%a.size;a.replace a[w..-1]+a[0..w-1] if w!=0;end

Reply

Cary Swoveland August 30, 2010 at 10:42 am

Solution (#12F):

Cary Swoveland, Canada
I had August 30 on the brain, so missed the deadline. Accordingly, please enter me in the “Just for Fun” category.
https://gist.github.com/fdca50c2ccd7348db597
My programs work with Ruby 1.9.2.
I’m retired. Learning Ruby is one of my hobbies.

Reply

David Griffiths August 31, 2010 at 6:19 am

Very impressive Cary :-) I particularly love the way you wrote a program to solve the program of how to write the program. It passes all the tests and it’s a good solution. :-)

Reply

Cary Swoveland August 30, 2010 at 2:46 pm

I thought there might be some interest in how the various proposed skip_tracks() replacements might compare in terms of executions times. The results of my tests are shown at: https://gist.github.com/93a9b912f4a211723ae3.

In all cases I assumed skip_tracks() looked like this:

def skip_tracks(tracks, skip)
skip = skip % (n = tracks.size)

end

where ‘…’ is the body proposed by the competition’s entrants. I had to translate submissions into this form, but that seemed to go pretty smoothly, expect for Paul McKibbin’s. (Paul: I translated yours as:
tracks.replace(tracks[skip..-1] + tracks[0..skip-1]) if skip
Did I make a mistake?) I wasn’t able to use Santosh Wadghule’s submission, as the new ‘tracks’ is not returned in the method’s argument. I will add Kirill Shchepelin’s proposal once the URL to his code is provided. Do let me know if I’ve made any mistakes.

I calculated total times to run 10 tests, for (each of) 10,000, 50,0000, 500,000 and 3,000,000 tracks. ‘skip’ was set equal to (n-1)*(nbr_tracks/10) for the nth test. For example, when nbr_tracks = 10,000, skip = 0 for the first test, = 1,000 for the 2nd test,…, and 9,000 for the 10th test. I tested them on a MacBook Pro, with Ruby 1.9.2, running from Textmate. Note the files at the gist may not be in order of increasing tracks.

The first test had 10,000 tracks. It is with deep regret that, for the next round of tests, I was obliged to remove the solutions offered by Dmytrii Nagirniak (#4) and Sebastian Rabuini (#5). Had I not done so, they would have been left in a cloud of dust.

The second test had 50,000 tracks. Alas, I must declare all three of my own submissions as uncompetitive, and remove them from further consideration, leaving but three contestants. (I didn’t even include two others I considered, as they were really slow.)

The third test has 500,000 tracks. All three are still extremely fast, but I’m afraid that when the music stopped, Julio was the one without a chair, so he must sit out the final round.

The fourth and final test had 3,000,000 tracks. The results were very ver close: Alex Chateau (#1) and Benoit Daloze (#10), at 2.93 and 3.65 seconds, respectively. Their methods are very similar, so it is not surprising they are close in performance.

Reply

David Griffiths August 30, 2010 at 7:45 pm

Hello Cary,

I have just this minute sent off the final results to Satish for the problem, so I’ve only just seen your comment. I will leave it to Satish to make the announcement but I was particularly interested in the final performance test. The challenge was to optimize for size rather than speed, but it is interesting how well some of the shorter solutions have performed. Ordinarily speed/size are a trade-off, but this is less true for interpreted languages. In a language like Ruby, the shorter the solution, the more your code is likely to depend more of the native underpinnings of the language, and less on interpretation.

Incidentally, I *love* your code that works out the code. Very cool :-)

DG

Reply

Paul McKibbin August 31, 2010 at 1:34 pm

Hi Cary,
That’s not quite right, but more due to my bug than yours. Try this as a candidate:

o=skip%tracks.size
tracks.replace(tracks[o..-1]+tracks[0..o-1]) if o!=0

I’d be interested to find out the performance and if they stand up under a large amount of data.

Reply

Cary Swoveland August 31, 2010 at 9:04 pm

Hello, Paul.

Too bad about that C-thinking bug. I knew your code would be fast before I ran it. The three fastest methods are very similar, and rely on underlying C code to shift blocks of values quickly. The other methods rely on element-by-element changes in Ruby, which of course is much slower. Re-running my test with three million tracks, execution times were as follows (all preceded by ‘n = tracks.size’):

Alex Chateau (#1):
tracks[0, n-skip], tracks[n-skip..n] = tracks[skip..n], tracks[0, skip]
Passed all 10 tests.
Elapsed time = 2.876141 seconds

Paul McKibbin (#9)
tracks.replace(tracks[skip..-1] + tracks[0..skip-1]) if skip != 0
Passed all 10 tests.
Elapsed time = 3.081262 seconds

Benoit Daloze (#10):
return if skip.zero?
if skip >= 0
skip %= n
tracks[0...n-skip], tracks[n-skip..-1] = tracks[skip..-1], tracks[0...skip]
else
skip = skip.abs % n
tracks[0...skip], tracks[skip..-1] = tracks[n-skip..-1], tracks[0...n-skip]
end
Passed all 10 tests.
Elapsed time = 3.62012 seconds

Reply

Cary Swoveland August 30, 2010 at 10:41 pm

David, I suppose we should give you equal time. Your coding style is a bit, er, unconventional, but, as is said, the proof is in the pudding. I ran your formulation (with inner loop ‘while (c+inc) % arr.size != start … end’) through the 10,000 tracks test. It took 0.33 seconds, which I am sorry to say, just does not cut the mustard.

Magnet reassemblies by Alex Chateau (#1), Sebastian Rabuini (#5) and Paul McKibbin (#9) did not pass my tests. Might I be wrong? I think Alex and Sebastian (with identical reconstructions) need to replace ‘c = c + 1′ with ‘c = (c + inc) % arr.size()’. Paul omitted the needed line ‘count = count + 1′ before or after ‘start = start – 1′. I suspect that was an oversight–that he actually meant to include the missing line–since leaving it out leaves one required line blank. The only correct solution I found was Julio Villasante’s (#8). His solution is also correct if his inner loop (‘begin … end while (c + inc) % arr.size() != start’) is replaced with ‘while (c + inc) % arr.size() != start … end’.

I’m glad you liked my attempt to sort out the magnets.

Reply

David Griffiths August 31, 2010 at 6:20 am

There were some very interesting solutions added. I think though the results are the same as when I looked before:

1st place: Alex Chateau, Latvia

Very, very close 2nd: Sebastian Rabuini, Argentina

As I said before I really feel that Sebastian and Alex are so darn close, that if you have some way of sending their addresses to me I will send them both some gift vouchers or Head First stuff or something.

DG

P.S. I think of the new solutions added, the “just for fun” solution from Cary Swoveland is worth a mention; he wrote a program to write the program, which appeals to the meta-programmer in me :-)

Reply

Leave a Comment

{ 14 trackbacks }

Previous post:

Next post: