Ruby Programming Challenge For Newbies
RPCFN: The Game of Life (#11)
By Elise Huard
About Elise Huard
Elise Huard is based in Brussels, Belgium and is the owner of Jabberwocky, a solutions company mostly focused on Rails. She has worked with a few other technologies before falling in love with Rails and Ruby about 3 years ago and going freelance to work with Ruby full time. She contributes to open source projects as much as she can, and has given talks at a few Ruby and Rails conferences. She’s a jack of all trades, loves reading, tinkering, food, travel, learning, and people out of the ordinary.
Elise has this to say about the challenge:
This challenge consists in implementing the game of life. This is a problem that is simple to understand, but requires some thought to implement correctly. Tests will help you spot your own reasoning fallacies. And of course, every hacker has to have implemented the game of life at least once
Our Awesome Sponsor
This monthly programming challenge is sponsored by 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 sponsored this challenge and is proud to make this contribution to the Ruby community.
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
The Challenge
The entire challenge details are available at: http://github.com/elisehuard/game_of_life
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:
- Your name:
- Country of Residence:
- GIST URL of your Solution (i.e. Ruby code) with explanation and / or test cases:
- Code works with Ruby 1.8 / 1.9 / Both:
- Email address (will not be published):
- 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 2nd Aug. 2010 (Indian Standard Time). No new solutions will be accepted from 3rd Aug. onwards.
- On 3rd 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 10th Aug. 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:
- What Is The Ruby Programming Challenge For Newbies (RPCFN)?
- How does RPCFN benefit you?
- Challenge Rules
- Best Solution
- Can I Submit A Ruby Programming Challenge Topic?
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.
Acknowledgements
Special thanks to:
- Elise Huard.
- Sponsors Backup My App.
- 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
- Dominik Masur, Germany
- Sergey Kruk, Russian Federation
- Mark Mba Wright, USA
- Andrew Cox, U.K.
- Julio C. Villasante, Cuba
- Nils Riedemann, USA
- Valério Farias, Brazil
- Christopher Fortenberry, USA
- Falk Pauser, Germany
- Sam Johnson, Australia
- Brad O’Connor, Australia
- Michael Klaus, Germany
- Dmytrii Nagirniak, Australia
- Milan Dobrota, USA
- Steve Hindmarch, UK
- Nithin Bekal, India
- Zachary Becker, USA
- Benoit Daloze, Belgium
- Tanzeeb Khalili, Canada
- Cary Swoveland, Canada
Just for Fun
- Trevor Fountain, U.K.
- William Crawford, USA
The Winners
Congratulations to the winners of this Ruby Challenge. They are:
- Benoit Daloze from Belgium (his Ruby Challenge solution) – the person with the best and most creative Ruby solution. He wins any one of PeepCode’s Ruby on Rails screencasts and a free 10 GB account for a year from Backup My App.
- Steve Hindmarch from UK, Leonardo Bessa from Brazil and Tanzeeb Khalili from Canada win any one of Pragmatic’s The Ruby Object Model and Metaprogramming screencasts.
- All the participants in this challenge (except Benoit Daloze who gets a free 10 GB account for a year) will get a free 5 GB account for 6 months from Backup My App.
Previous Challenge
RPCFN: Business Hours (#10) by Ryan Bates.
Note: All the previous challenges, sponsors and winners can be seen on the Ruby Programming Challenge for Newbies page.
- This challenge is now closed.
- The (#12) challenge by David Griffiths, USA is scheduled for Aug. 2010.
Technorati Tags: Ruby, The Ruby Programming Language, Ruby Programming Challenge For Newbies, Programming, RPCFN, Elise Huard
Posted by Satish Talim
{ 78 comments… read them below or add one }
Next Comments →
Solution (#1):
Dominik Masur, Germany
https://gist.github.com/d881c26151874021d4cf
Code works with Ruby 1.8
I changed the init line and gist new after elises comments (thx for that)
- lack of ambition in parameters (only one: size)
- could use some refactoring, and a little more cleverness in neighbor calculation
Solution (#2):
Trevor Fountain, U.K.
http://gist.github.com/456010
Tested with Ruby 1.8
I’m not in this for real, just for fun — I don’t think I can get away with claiming the “Ruby Newbie” title anymore. I’m a Cognitive Science graduate student in Scotland; I started using Ruby for casual projects a few years ago, but only seriously learned the language when I began using it to conduct my research.
In case the “brief description of what you do” was meant to be a “brief description of what your code does”, well, the code is somewhat documented — and the #evolve method is more-or-less readable, thanks to the ugly, ugly monkeypatch that precedes it.
- (as you know) the reopening of Array is clever, although overloading something as essential as [] can be dangerous in any larger projects (unintended side effects)
- the neighbour calculation is also pretty nicely done
- code is clear, names are sensible
- I don’t think the probability calculation is correct, a comparison between the result of rand and the probability would have made more sense. Creating a game of life with a low probability actually yields more cells than creating a game of life with high probability, unless that’s the purpose ?
Solution (#3):
Sergey Kruk
https://gist.github.com/451cfcbac82ba53059ef
GameOfLife is inherited from Array and replaces iteslf on evolve. Thus GameOfLife#inspect method shows current state. The field is folded onto itself.
You can initialize the field with parameters:
size
width, height
width, height, seeds
Or with options hash. Default is 5×5 with 10 seeds
If number of seeds exceeds field size, all field is filled.
- correct implementation.
- I think it’s better to have a well-defined set of parameters, like a hash in your case, this sends a clearer message to people using your class.
You say: I expect this and that, and then you test on that limited set whether you get the expected inputs.
- your initialization is interesting, you’re the only one who does the randomizing on the width and height. Your implementation is a bit complex (especially the bit with the while loop). Striving for simplicity will help you if you need to get back into your own code 6 months later
- also, I suspect the initialization is OK, but doesn’t produce too many viable configs: trying with a small matrix yields a matrix full of 1, trying with a larger number yields a very sparse matrix. But it allows to play with seeds, which is good.
- dup is not strictly necessary, you can just clone your state
I build this life simulator when I was very new to Ruby, so it’s probably pretty awful code:
https://gist.github.com/dee55426374e780a9870
It can generate PPM images though, in numerical sequence. Graphic Converter can then convert those into fun Quicktime movies. I have a good one of the “Puffer Train.”
Nice one ! As you are as far from newbie as one can get, I guess this is not an official entry
I still feel like a newbie most days at work and I was definitely a Ruby newbie when I wrote that code.
The Ruby 2D-gamelib Chingu [ http://github.com/ippa/chingu ] has a game of life example [ http://github.com/ippa/chingu/blob/master/examples/game_of_life.rb ] with OpenGL accelerated gfx, oh yeah
. Developed by R.Kawowski [ http://www.toastymofo.blogspot.com/ ]
I added some modifications and various common patterns (like the Gospel Glider Gun, Lightweight Spaceship and the Pulsar) which can be scrolled through with the mouse-wheel and put out on the screen with a click. Easy to add your own patterns in ascii-format too…
nice, one of the entries used your implementation I think
Solution (#4):
Mark Mba Wright, USA
I’m pretty new to Ruby so the code may not look too rubyish.
Proposed solution: https://gist.github.com/f6914344c2d1c5ae34ce
Test Case: https://gist.github.com/ad89eae9051c5a2c2c17
Visualization (ruby-processing): https://gist.github.com/4d52b08104468955fc6f
- error in initialization: is systematically initialized with 0 everywhere …
- evolve shouldn’t need to reinitialize the state, since it is defined when initializing the object.
- readability: clear variable names always help, refactoring in smaller, clearly named methods would help too
Solution (#5):
Andrew Cox, U.K.
https://gist.github.com/8dcb8d3365b5228fb7d6
- extra points for adding tests to the solution
- nicely OO approach with Cell, with neighbors of a cell being part of its properties
- naming for clarity, short methods
- maybe a bit heavy for the problem simplicity, but nicely done.
Solution (#6):
Julio C. Villasante, Cuba
https://gist.github.com/967c2235c85169f9673d
Tested in Ruby 1.9.1
With the solution I’m posting a README file that broadly explains how I do it.
Posted a modified test case for when the board is not folded with the same tests that were provided.
Anyway, enjoy a lot doing this, keep up the good work…
jvillasantegomez@gmail.com
- good point for adding a readme to explain reasoning
- bonus points for dialog, and number of variables used
- fold_board is not strictly necessary since it’s possible to calculate with ruby using negative indexes
- the implementation itself doesn’t seem to work that well
- no state accessors to get or set the state, which was asked
Please, being new to ruby I would like you to elaborate on “the implementation itself doesn’t seem to work that well”, actually I got into this to get some feedback.
)
About the fold_board method you are right, but I always strive for clear/readable code (using negative indexes and the like is like an abomination to me
Didn’t add any state accessors ’cause didn’t had the time to write tests, thought that they were needed for testing only.
Anyway, good challenge, enjoyed it a lot, thanks for sharing…
Jose: I mean by that that I tried to run a visualization of it, and it didn’t work.
But you’re right that going overboard with that is dangerous.
about the negative indexes: I see what you mean. I think that within bounds, a little cleverness is allowed
The accessors were for my tests as well.
Solution (#7):
Nils Riedemann, USA
Hey I am relatively new to ruby so there might be some things that could have been done better. And it was the first time i did tdd/bdd.
Did it in less than 40 lines (excluding comments) but tried to maintain readability.
https://gist.github.com/8709224425dd99034dda
- congratulations for your first specs
bonus points for adding them.
- a slight lack of ambition in features
- a correct, short implementation.
- adding the neighbours themselves to calculate the neighbours would have been possible, since they are 1 or 0
Solution (#8):
Valério Farias, Brazil
http://gist.github.com/460651
I ran the code using ruby 1.8.7
I used Shoes to see the graph
- bonus points for adding tests
- lack of ambition in features
- adding neighbours to each other would have worked, since we’re talking about 0 and 1 (no if required)
- cloning of the result of evolve is not necessary, assignment is enough – one state is enough for this problem
- correct implementation
Solution (#9):
Christopher Fortenberry, USA
https://gist.github.com/bff42e44d35ca554ac67
Works with 1.8 and 1.9
- bonus points for adding tests !
- initialization seems a bit heavy – assigning a rand(2) to every cell, or playing with a probability (rand > probability) could have worked too.
- creating an array with the correct size, and assigning live cells to it afterwards, may be a bit safer than constructing arrays from scratch. (although this works too)
- nice to implement access to the ‘matrix’ by making new getters. However, pushing this might have been more interesting, and more ‘OO’ (having a class for the state)
- correct implementation
Solution (#10):
Falk Pauser, Germany
I am a Webdeveloper from Germany (Koblenz/Rhein) and here is my solution: http://gist.github.com/461159
- bonus point for adding specs !
- the seeding is not going to be evenly spread over the cells – there’s always going to be a higher probability of upper left than lower right
- bonus for checking on inputs in state= and initialize
- clear naming for neighbors
- living_nb calculation is not as elegant as it could have been
What about the bonus point for the sinatra visualization?
hah, very cool
Hi,
How can we submit the solution if it would include the set of tests (Cucumber and RSpec), couple of files for the solution itself and possibly some other additions to the game.
It doesn’t seem it could be easily done using a Gist.
So maybe I could just submit the solution files only (no tests or other stuff) with gist and then add comment to link to the whole github project?
Or maybe the project itself from the github can be submitted?
Cheers.
Dmytriee, it is actually possible to add several files in one gist (‘add another file’ option).
however, if you prefer you could fork the project, do your thing and then submit that link.
Hope that helps ?
Solution (#11):
William Crawford, USA
git@gist.github.com:d643626f26d16c54591f.git
I only tested it on 1.8.
As I’m a professional developer in another language, I’m doing this just for fun. I’ve been meaning to learn more about Ruby for a while, and these challenges seemed like a good way. Any feedback on how my code can be more ‘Ruby-like’ is much appreciated.
- for flexibility, width and height could be made inputs – to have the defaults set to 5, you’d use initialize(widht=5, height=5)
- width and height are not really necessary as instance variables since they can be deduced from state
- bonus points for raising exceptions on wrong input on state. The usual ruby error would be ArgumentError (or a custom subclass of RuntimeException).
- in Ruby, you can go negative with Array indexes. So you could add arr[-1], and it would just take the last element of the array
- seems to be a correct implementation !
Thanks for the comments! They’ll definitely help me be more ruby-like in the future.
Can I ask how what you said about width and height being made inputs is different from what I did?
My Code:
def initialize width=5, height=5
@width = width
@height = height
@state = Array.new(@height).map! { Array.new(@width).map! { rand(2) } }
end
ehm, then I wonder if I have the correct URL
https://gist.github.com/d643626f26d16c54591f
In this version the initialize method takes no argument … but your code is correct, you can ignore the comment
Oh! My mistake! I added that after I submitted! I forgot I had made some more changes afterwards because I was playing around with it.
Thanks again for looking over it!
Elise,
The Gist allows adding many files but as far as I know it is not possible to organise them with folders. So if submitting a fork can work in this case I would take that option which sounds to be ok.
Thanks and cheers.
Solution (#12):
Sam Johnson, Australia
http://gist.github.com/466917
Code tested with 1.8.7
- bonus for adding tests !
- initialization is 0 …, evolve is correct
- apart from that, elegant and readable
Since the ncurses demo doesn’t run on Windows, I’ve made a visualisation of the game of life in WPF for those on the Microsoft platform that want to see stuff happening instead of shifting array elements
If you follow the outline of the challenge, it should work great with your solution (just put a callback to update() when your game evolves).
http://trquadrant.com/2010/7/8/48-ruby-game-of-life-in-wpf
It’s in IronRuby, so it’s still cool right?
wow, nice one
there is a working solution for Windows with Shoes in the github project, but yours looks pretty nice !
Solution (#13):
Brad O’Connor, Australia
http://gist.github.com/473578
Should work with Ruby 1.8 or 1.9. I’ve only tested it with 1.9.1
Thanks for this challenge. It was a nice bite-sized piece of coding to do. As always, I learnt many things doing it, including things I wasn’t expecting to learn.
- bonus for adding tests !
- concise and clear, and correct
- shorter way to create matrix: Array.new(n) { Array.new(n) { rand(2) }}
- another tip would be to make the internal methods private
Solution (#14):
Michael Klaus, Germany
I tried to roughly optimize the task for code complexity in terms of token count. This results in the #neighbours method just adding the numbers in the patch and subtracting the current cell’s value. The #evolve method was stripped down to the minimum necessary cases using minimal input data. Hope you like it.
https://gist.github.com/2fefaf84664908c32f41
Works with: Ruby 1.8 and 1.9
- bonus for adding specs !
- unfortunately, initialization is incorrect, the state is filled with Nil
- evolve is correct, the use of modulo is clever
Solution (#15):
Dmytrii Nagirniak, Australia
http://github.com/jameskayn/game_of_life
Code works with Ruby 1.8.7>:
- bonus for the specs !
- nicely OO structure, maybe a bit much for the simplicity of the problem
- initizialization parameter name leads to confusion – I guess it should be size – could have been nice to have width and height, since both are obviously planned for.
- implementation is correct
Hi Elise,
I agree about “a bit much for the simlicity”, but it really saved a lot of my time and brought to correct implementation
As for the initialization parameters, there are both initialization options available: size and width-heigh.
You can see that on this spec:
http://github.com/jameskayn/game_of_life/blob/master/spec/models/game_spec.rb
Probably one place of confusion may be in the fact the ‘size’ initialization does not require a ‘board’ to exist, where ‘width-height’ requires a board or array to be passed into Game.
Cheers,
Dmytrii.
You’re absolutely right, I should have looked at the specs more closely. Thanks for clearing this up !
Solution (#16):
Milan Dobrota, USA
https://gist.github.com/203b4d71e32794fd7a70
Code tested with Ruby 1.8.6
- could have worked with width and height as input parameters
- nice implementation with CircularRange
- just summing the neighbours could also have worked, since you use 0 and 1
Solution (#17):
Steve Hindmarch, UK
https://gist.github.com/0fdaaf7ea5340a22786c
Code works with Ruby 1.8
- bonus for added tests !
- nice to have more parameters
- also nice touch to have a form of persistence
- quite readable
- correct implementation
Solution (#18):
Nithin Bekal, India
https://gist.github.com/840815ba8f3579370853
The code works with ruby 1.8, but I haven’t checked it version 1.9.
- correct implementation
- avoid variable names like x and y (i and j as counters are acceptable)
- good neighbour calculation, with modulo and using the negative array index
- get_new_state is correct, but could be slightly more readable
Solution (#19):
Zachary Becker, USA
http://gist.github.com/501813
1.8 tested, should work in 1.9
- correct implementation
- the Marshal.load(Marshal.dump(@state)) is slightly weird – clone would have achieved the same result
- everything is named clearly, so readable
- for neighbour calculation, summing up the elements themselves achieves the same result, since we have 1 and 0
Clone was only copying the array one level deep, so if I changed the copy it was still changing the original.
Here is an example.
$ irb
irb(main):001:0> a = [[1,2,3],[4,5,6],[7,8,9]]
=> [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
irb(main):002:0> b = a.clone
=> [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
irb(main):003:0> b[1][1] = 0
=> 0
irb(main):004:0> a
=> [[1, 2, 3], [4, 0, 6], [7, 8, 9]]
irb(main):005:0> b
=> [[1, 2, 3], [4, 0, 6], [7, 8, 9]]
irb(main):006:0> a[1][1] = 5
=> 5
irb(main):007:0> b
=> [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
irb(main):008:0> b = Marshal.load(Marshal.dump(a))
=> [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
irb(main):009:0> b[1][1] = 0
=> 0
irb(main):010:0> a
=> [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
irb(main):011:0> b
=> [[1, 2, 3], [4, 0, 6], [7, 8, 9]]
Strange, when I try in irb (ruby enterprise 1.8.7)
a = [[1,2],[3,5,6]]
=> [[1, 2], [3, 5, 6]]
ree-1.8.7-2010.02 > b = a.clone
=> [[1, 2], [3, 5, 6]]
ree-1.8.7-2010.02 > b[0][1]
=> 2
ree-1.8.7-2010.02 > b[1][1]
=> 5
And same result in ruby 1.9.2
Marshal is still fairly unusual in this context … it’s certainly not incorrect.
The “rows/sub” Arrays need to be cloned/duped too:
new = old.map(&:dup)
Solution (#20):
Leonardo Bessa, Brazil
https://gist.github.com/36ea89b66956fdf3c6cb
Code works with Ruby 1.8.
My code iterates in each cell of an array of arrays a verifies if the cell should be alive or dead. I also made a sintra application where each cell is a radio button in a form, to visualize the game of life.
- cool visualization with sinatra
- bonus for adding tests
- clear and correct implementation
Solution (#21):
Benoit Daloze, Belgium
http://github.com/eregon/game_of_life
Code works with 1.9, some with 1.8 (and a little of JRuby 1.8)
This is a fairly big solution with 9 implementations and a few visualizations. I wanted to try a lot of different way of coding for the implementations, and try to make a visualization beautiful and fast.
More on the README
- very nice, full exploration of many variations on the game, and a good knowledge of ruby
- would have been even more impressive if every different (ruby) implementation could have been slotted in to one game class (although this is already great)
- pretty awesome visualizations
Thanks !
About the classes, it would have been much harder to compare and use them in visualizations, or I should have then alias GameOfLife to the implementation used.
I thought to that possible name collision, and it was a bit harder for the specs and benchmarks, but safer too.
In fact, I did not want to have more than one implementation loaded at runtime, as some use monkey-patching which would cause name clashes and method redefined.
Great challenge and many interesting solutions !
Solution (#22):
Tanzeeb Khalili, Canada
git://gist.github.com/504449.git
Should work with 1.8.7 and 1.9.2
Sorry, here’s a clickable URL: http://gist.github.com/504449
- correct implementation
- elegant and clever
- extensible, thanks to the use of rules, and seed can be input
- summing the neighbors would have worked instead of counting ’1′
Hi Elise,
Thanks for your comments
Quick question — I’m not sure how to do a sum with an array? Do you mean using inject?
Tanzeeb: yes, that’s what I meant.
I agree with WC below that your implementation was the most beautiful in terms of code.
Indeed, your implementation has many good/cool ideas.
I did add it in my repo (http://github.com/eregon/game_of_life/blob/master/lib/game_of_life_tanzeeb.rb)
I had to modify quite much #initialize to respect my API, so do not pay attention to the ugly “case”.
Please say if this is a problem to you (I mean including your code)
I find your entry to be really impressive. I keep looking at the code and finding things that just amaze me. Thank you for entering it.
Thanks WC
I agree. A look through the code has revealed just how much less Ruby I know than I thought I did. I really need to learn how to use blocks as method parameters.
Thanks Brad! I learned the trick from PragProg — http://ruby-doc.org/docs/ProgrammingRuby/html/tut_containers.html#UG.
Solution (#23):
Cary Swoveland, Canada
I’m crossing my fingers, as I didn’t have much time for testing.
https://gist.github.com/5f784cd6c9c5a4329d6b
- well researched, only implementation that explores possible topologies, nice
- passes tests for the torus topology
- unusual in that dimensions are not parameters but constants, only topology is variable
Thanks, Elise–great challenge! I assume you noticed I did chose the grid sizes randomly, though I hard-wired the ranges for those dimensions. Frankly, I wasn’t very interested in that part of the challenge, so didn’t spend much time on it. I instead focused on allowing for different topologies. I am new to OOP generally–not just Ruby–and thought allowing a choice of topology would improve my understanding of subclasses, inheritance and overriding methods. It did!
{ 36 trackbacks }