Programming Challenge 17 - Implement Life

A British Mathematician John Horton Conway came up with an interesting idea in the early 1970s which he called Life. It's a cellular automaton where the contents of a two dimension grid are either set or clear according to three rules. From a starting position the entire grid is processed according to these rules:

1. A set point surrounded by 2 or 3 other set points carries on to the next generation.
2. A set point that is next to 0,1 or 4+ set points is cleared. (Dies of loneliness or overcrowding!)
3. A clear point surrounded by exactly 3 set points becomes a set point.

That's it. Three very simple rules that generate an amazing variety of patterns.

The Challenge

There is a configuration called an F-Pentomino. Just 5 set points but it lives a very long time. The empty point should be located at 500,500 as shown below.

       500-501-502
500    0    1    1
501    1    1    0
502    0    1    0

I've used 0 for a clear point and 1 for a set point.

You have to write code that processes this for 1,000 generations on a grid of 1,000 by 1,000. Please make it so that the grid is continuous in both east-west and north-south directions. If you have a point at 0,0 in the top left position then the 8 points around it in (x,y) notation are.

-1,-1    | 0,-1   |   1,-1
-----------------------------
-1,0      | 0,0     | 1,0
-----------------------------
-1,1      | 0,1     | 1,1

I know having a grid that wraps both east west and north south is unusual but if you have a point at an edge, say y = 0 and you wish to process the point at y-1 then do y = (y + 1000) ^ 1000; This works for any y in the range 0 to 999.

Results

We had five entries, that all got it right and the difference between 1st and 2nd place was 3.5/1000th of a second! Congratulations to Aliaksei Sanko of the Belarus for his winning entry in C++. Some very close results, all within a second or so.

1. Aliaksei Sanko(Belarus,) - C++ Time(secs) = 0.0654754
2. Joshua Warner (USA) - C Time(secs) = 0.068793
3. Peter Jansson (Sweden,36) - C++ Time(secs) = 0.58823 url
4. Chris Greth - C++ Time(secs) = 0.588253
5. Ehsan Khakifirooz (IRAN,22) - C# Time(secs) = 1.0003332

More Programming Challenges

• Link to Rock, Scissors and Paper Bot Ongoing Programming Challenge - Runs weekly.
• Link to Programming Challenge 2 - Count the Islands. (Finished)
• Link to Programming Challenge 3 - Manage Elevators. (Finished)
• Link to Programming Challenge 4 - Guess the Mastermind Code - (Finished)
• Link to Programming Challenge 5 - Squeeze words into a crossword grid - (Finished)
• Link to Programming Challenge 6 - Guess the Mastermind Code - (Finished)
• Link to Programming Challenge 7 - Validate Chess Positions - (Finished)
• Link to Programming Challenge 8 - Score Poker Hands - (Finished)
• Link to Programming Challenge 9 - Manage a Data structure - (Finished)
• Link to Programming Challenge 10 - Hide Text (Finished)
• Link to Programming Challenge 11 - Match Sets of Cards (Finished)
• Link to Programming Challenge 12 - Calculate Shortest Path - Completed)
• Link to Programming Challenge 13 - Play Battleships (Finished)
• Link to Programming Challenge 14 - Multiply Large Numbers(Completed)
• Link to Programming Challenge 15 - Generate a Dungeon (Completed)
• Link to Programming Challenge 16 - Solve 1,000 Sliding Puzzles. Finished
• Link to Programming Challenge 18 - Generate a Map. (Deadline November 30).