Wednesday 24 September 2014

The Game of Life Solution Walkthrough

Dear blog, it has been an awfully long time since my last post, I hope you are in a forgiving mood.  During the past two months, I have actually been blogging elsewhere, but you will always be my first and most important blog site.  The reason for the absence is that in mid-July I started my one-year sabbatical from my finance job in order to do my Computer Science Masters (see my Back To School post from March) and I used the summer to go travelling in Singapore, Australia and New Zealand.  I used this blog as a photo diary of my adventures so that my parents could check that I was still alive.
Maybe I should have done a career change to become a beach bum instead....
While on my travels, I really lived life on the edge - I went on helicopters, mountain and glacier hikes, caving, white water rafting, scuba diving, bungy jumping and sky diving, but throughout my trip my laptop and university pre-course reading were never far away.  The textbook I have been working through is called Problem Solving with C++ by Walter Savitch...many people I met on my trip thought it was weird that I had brought work with me, but I had some looooong coach journeys to sit through and so far I have enjoyed working through the "homework" problems at the end of each chapter.

This blog post is a walkthrough of my solution to one of these problem sets, and what better way to resurrect my blog than with an article about the Game of Life.  Before we get into the meat of the solution, I just want to spend a bit of time comparing and contrasting C++ with Python (the programming language I had previously had most experience with).  When people who have some programming knowledge ask me what language my Masters course will use, they generally make the following face, when I tell them it will be taught in C++:


People then go on to say things like "If you can do it in C++, you can do it in any language".  I'm not sure how C++ acquired this formidable reputation, but so far, I have to say that Python was definitely easier to learn and seems to be more flexible.  As you will see with my C++ solution to the Game of Life, at the top of the code, there are some header statements  - when you are a newb you just have to accept this as given and not get too bogged down with the details of why they are there.  Also, with C++, when you use variables in your program, you have to define the variable's type in advance (e.g. whether it will be an integer, or a character etc), whereas Python sort of allows variable types to be defined as and when they are created.  Similarly, when you want to run programs you have written in C++, they must be compiled first (compiling just means the computer checks through the code you have written in your editor and converts into code that your machine can understand), but again, Python cobbles it all together while the program is being run.  The compilation stage is often useful as it brings up any errors before your program is being executed, and you do get a super satisfying feeling whenever your program compiles correctly the first time!

Ok, I've used this meme before - forgive me, I'm a Futurama fanatic


Most of the time, it doesn't compile and for me, more often than not, it's because of these darn semicolons you have to put at the end of every statement in C++!  After being used to coding in Python, it takes a while to get used to them...  My final gripe with C++ is Microsoft Visual Studio Express - ok, so it's not really related to the language itself, but this is possibly one of the least intuitive and most beginner-unfriendly development environments EVER!  Thankfully a new Macbook Pro is on its way to me and I will hopefully never have to deal with Visual Studio again!

Another way to illustrate the differences between Python and C++ is the different philosophies behind the two languages.  The bullet points below are taken from Wikipedia, and I think the way they are written gives you a real feel of the conceptual differences between them as well as an idea of what it is like to code with them.

Python:
  • Beautiful is better than ugly
  • Explicit is better than implicit
  • Simple is better than complex
  • Complex is better than complicated
  • Readability counts
C++:
  • It must be driven by actual problems and its features should be useful immediately in real world programs.
  • Every feature should be implementable (with a reasonably obvious way to do so).
  • Programmers should be free to pick their own programming style, and that style should be fully supported by C++.
  • Allowing a useful feature is more important than preventing every possible misuse of C++.
  • It should provide facilities for organising programs into well-defined separate parts, and provide facilities for combining separately developed parts.
  • No implicit violations of the type system (but allow explicit violations that have been explicitly asked for by the programmer).
  • Make user created types have equal support and performance to built in types.
  • Any features that you do not use you do not pay for (e.g. in performance).
  • There should be no language beneath C++ (except assembly language).
  • C++ should work alongside other pre-existing programming languages, rather than being part of its own separate and incompatible programming environment.
  • If what the programmer wants to do is unknown, allow the programmer to specify (provide manual control).
This all sounds like a big rant against C++, but as with all new things, I've learnt to adapt and get used to it, so there really is no bad feeling between me and C++.  Also, I'm sure it has many advantages over other languages that I'm yet to understand, but hope to discover during my Masters course!

Phew! That was a long detour, but now we've gotten that out of the way, let's get onto the meat of the Game of Life solution! The following description is taken from Chapter 7,  Programming Project 13 of the Savitch textbook and you can also read a more detailed and very interesting Wikipedia article (complete with cool gif animations!):

The mathematician John Horton Conway invented the "Game of Life". Though not a "game" in any traditional sense, it provides interesting behaviour that is specified with only a few rules.  This Project asks you to write a program that allows you to specify and initial configuration.  The program follows the rules of LIFE to show the continuing behaviour of the configuration.

LIFE is an organism that lives in a discrete, two-dimensional world...This world is an array with each cell capable of holding one LIFE cell.  Generations mark the passing of time.  Each generation brings births and deaths to the LIFE community:

  • We define each cell to have 8 neighbour cells...(directly above, below, to the right, to the left, diagonally above to the right and left, and diagonally below to the right and left).
  • If an occupied cell has 0 or 1 neighours, it dies of loneliness (awwww....). If an occupied cell has more than three neighbours, it dies of overcrowding (anyone who has been on the Central Line will sympathise with this).
  • If an empty cell has exactly 3 occupied neighbour cells, there is a birth of a new cell to replace the empty cell (hmm, talk about a love triangle..?! this Conway dude can't have been much of a biologist)
  • Births and deaths are instantaneous and occur at the changes of generation.  A cell dying for whatever reason may help cause birth, but a newborn cell cannot resurrect a cell that is dying, nor will a cell's death prevent the death of another, say, by reducing the local population.

So given these rules and a starting pattern of live cells on a two dimensional grid, with every generation the pattern of the live cells evolves.

I have put my code on my github page: https://github.com/ttz21/Game-of-Life

Using the framework for problem solving I outlined in my TicTacToe Solution walkthrough, I'm going to start off with the all-important Step 0: Don't Panic.  So after taking deep breath, let's consider the following....

1. What are the inputs?

That's simple - the initial configuration of live cells on a board.  In my solution I have used a 20 x 20 array, because it roughly suits the default size of the screen that pops up when the code is run.  Of course, we could have also written the program to let the user specify the size of the board.  We can declare the size of this board as a constant right at the beginning, so in future we can easily alter it's size without having to go through the entire code:

const int WIDTH = 20, HEIGHT = 20;  (it's customary to give constants names in uppercase, the const means the program can't alter these variables, and the int declares them as integer variables)

I have used an array of integers to track live (1) versus dead (0) cells, though this could also be accomplished using an array of booleans (true/false).  For this solution, the initial configuration has to be input manually (no, I didn't sit and write out all the curly brackets and "0," x400, I wrote a program that did it for me!) - I have put in a little star pulsar pattern that repeats itself every third generation, to give us something pretty to look at when the program is complete!  The code below declares a two-dimensional array of integers named "board", with HEIGHT+2 rows and WIDTH+2 columns (the reason for the +2 will become clear later...)

int board[HEIGHT + 2][WIDTH + 2] = {
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }
};

2. What are the outputs?

We want to display the board to the screen in response to a user prompt (e.g. pressing the Enter key to bring up the next generation).  Rather than showing 1s and 0s, it would be more visually appealing to show asterisks for live cells and just a blank for dead ones.  The function display_board below uses board as an input and uses a nested loop (i.e. loop within a loop) to go through all the rows and columns to print "*" to a screen when the ith row and jth column of the board has an entry of 1.

In C++, when functions are defined, you must declare whether the function returns a value or variable.  The display_board does not return anything, as it simply prints stuff to the user's screen so we declare it as a "void" function.  The "for" loops can be interpreted as: starting with an integer, i at 1, increment i by 1 each time (i++) while i is smaller than HEIGHT+1.  "cout <<" means output the statements that follow to the screen and "endl" simply puts the cursor onto a new line.

void display_board(int board[HEIGHT+2][WIDTH+2])
{
for (int i = 1; i < HEIGHT+1; i++)
{
for (int j = 1; j < WIDTH+1; j++)
{
if (board[i][j] == 1)
cout << "*";
else
cout << " ";
}
cout << endl;
}
}

3. Solve the problem!

To work out what the pattern of the new generation of cells looks like, we need to look at the neighbouring cells of every cell in the current generation.  The problem brief specifies that every cell has 8 neighbours - however, this is not strictly true, because the cells at the very edges of our board will have fewer than 8 neighbours.  In order to get around this, we actually use a 22x22 size board to help us calculate each generation's births and deaths (i.e. giving our 20x20 board a border with the width of 1 cell), but when we are choosing what to display to the user, we only iterate over the inner 20x20 board, and reset the "shell" to dead cells every period (because they technically don't exist and are not part of the game).

We need to know what the previous generation's board looks like in order to calculate the new generation, but after this has been done, we can discard the old board. This means we need to have two boards to work with at one time, as well as a function to copy the board that we use for our calculations onto the board used by the display_board function to show the latest generation.

The new_generation function below takes our board as an input and creates a temporary board of the same size.  This temporary board is then filled with 1s and 0s according to the rules of the Game of Life using the configuration of our input board.  When this has been done, our board with the initial configuration is overwritten with the temporary board using the copy_board function.


void new_generation(int board[HEIGHT + 2][WIDTH + 2])
{
int temp_board[HEIGHT+2][WIDTH+2];
int neighbours;

for (int i = 0; i < HEIGHT+2; i++)
{
for (int j = 0; j < WIDTH + 2; j++)
{
if (i == 0 || j == 0 || i == HEIGHT + 2 || j == WIDTH + 2)
temp_board[i][j] = 0;
else
{
//counting alive neighbouring cells
neighbours = board[i - 1][j - 1] + board[i - 1][j] + board[i - 1][j + 1]
                                   + board[i][j - 1] + board[i][j + 1]
                        + board[i + 1][j - 1] + board[i + 1][j] + board[i + 1][j + 1];
 
if (board[i][j] == 1)
{
if (neighbours < 2 || neighbours > 3)
temp_board[i][j] = 0; //cell dies due to loneliness or overcrowding
else
temp_board[i][j] = 1;  //don't strictly need to write this line, but I have added it for extra clarity
}

else
{
if (neighbours == 3)
temp_board[i][j] = 1; //birth of a new cell
else
temp_board[i][j] = 0;
}
}
}
}

copy_board(temp_board, board);


}

void copy_board(int board1[HEIGHT + 2][WIDTH + 2], int board2[HEIGHT + 2][WIDTH + 2])
{
for (int i = 0; i < HEIGHT + 2; i++)
{
for (int j = 0; j < WIDTH + 2; j++)
{
board2[i][j] = board1[i][j];
}
}
}

Once we have the display_board, new_generation and copy_board functions, all we need to do is implement them in the main function of the program!  The code below has a "while" loop that keeps repeats as long as the user hits the Enter key. The program displays the board, then reads the user's input using the command cin.get(repeat) and then calculates the next generation of LIFE.  cin is like the opposite of cout - it reads in a user's input from the keyboard and we are asking it to "get" one character (which I have called repeat).  '\n' is the way we represent the "Enter" character in C++.

int main()
{
char repeat;

do
{
display_board(board);
cin.get(repeat);
new_generation(board);

}while (repeat == '\n');

return 0;
}

For the initial configuration I entered, the displayed output should look a little something like an asterisk version of this:
Ta da!

I don't want the solution to get too complicated in this blog post, but from the subsequent chapters I have read in my textbook, I could have implemented LIFE as a class and represented the board as a dynamic array.  There are also interesting extensions to this problem to find static displays or cool evolving patterns, but I'll leave that to the mathematicians out there...

13 comments:


  1. Healrun is a health news blog we provide the latest news about health, Drugs and latest Diseases and conditions. We update our users with health tips and health products reviews. If you want to know any information about health or health product (Side Effects & Benefits) Feel Free To ask HealRun Support Team.

    ReplyDelete
  2. Holistic Bliss Keto totally women who've unsightly tummy fat want them removed. Built willing you should do everything in order to have them gone. They might have tried man steps such as exercise programs, recipes, and weight loss programs with no success. Fat just pops right back on her.

    Can you remove condiments from your diet for this brief period power? Eliminate ketchup (which I call tomato flavoured sugar), eliminate mayonnaise, be freed of treatments. Eliminate soy sauce from your rice.

    Some say that after with this particular product twice each day for as much as three to four weeks they often see their Weight Loss Tips going down at a sizeable rate. Just this, amongst the users mentioned that even binge eating during festival season didn't affect their fat loss! Many others are satisfied but now performance of your product. They believe that with acai berry and colon cleanse supplements, bodyweight has become easy. Now, slim figure and in this article shape 's no more a distant excellent.
    https://www.healthdiscreet.com/holistic-bliss-keto/
    http://healthdiscreet.weebly.com/blogs/holistic-bliss-keto
    https://discreet.health.blog/2019/04/03/holistic-bliss-keto-opti-ranches-keto-shark-tank-audits/
    https://medium.com/@symonds377/holistic-bliss-keto-the-latest-keto-formula-is-here-197f2735db28

    ReplyDelete
  3. Nutrisystem is a commercial weight loss diet that involves eating the company’s prepackaged and delivered meals and snacks, along with some produce you shop for yourself. By outsourcing meal-management chores, you won’t have to think about portion control, meal prep, or meal timing, but you may tire of heat-and-eat meals and smallish portions. Nutrisystem is also built around the glycemic index, a measure of how various carbs affect your blood sugar. Kindly Visit on Nutrisystem Lose Weight Faster

    ReplyDelete
  4. What a great line. Thank you for sharing it. Keep it up.The way you have presented the post with all the examples is also very impressive.
    Keto BodyTone

    ReplyDelete
  5. Keto Supply Diet Health can be thought-about as the amount of our physical and purposeful abilities to adapt to the changes in the surroundings and build the system in our body work properly. In order to keep in smart health we tend to have to use caution regarding hygiene . The rules and practices of keeping sensible health we have a tendency to want proper food and nutrition, workout, rest and sleep, cleanliness and correct medicare.

    https://www.ketosupplydiet.com/

    https://www.ketosupplydiet.com/ultra-fast-keto-boost/

    https://www.ketosupplydiet.com/ultra-fast-keto-boost/

    ReplyDelete


  6. http://healthonway.com/ Where to buy Rapid Fast Keto Boost Fixed Keto Encouragement?

    The uncomparable area to organization Rapid Fast Keto Boost Fleet Keto Help is its own regular website. But you should movement to buy because this is the stringent creation, so aggregation yours before the out of eutherian pop up.

    Everyone out there wants to fuck a toned embody that looks vantage. So, if you are also curious in getting a perfect body mold then you staleness try the ketogenic diet. This is the most stylish weight-loss method utilized by thousands of fill now. In this fast, you bonk to eat a lot of fat to enable your embody to destroy much and more fat instead of carbohydrates for vitality creation. In this Rapid Fast Keto Boost Nonviolence Keto Raise practice, we testament dig deeper into this production that give support you to eat your body fat easily. The important clinical of this supplement is to achieve your body hurting more and much fat.

    Commonly, in the pattern metabolic province, the weak body uses carbohydrates for producing liveliness. Moreover, group same ingestion dispose matter over a nutritious and well fast. In this housing, the embody simply chooses carbs as provide kinda than intelligent for any different choice. But, in the ketosis country, when your body starved of carbohydrates, it uses fat as the duplicate fuel. So, Rapid Fast Keto Boost Alacritous Keto Lift promotes this fat fiery impact in your body and allows your liver to delay fat cells into oleaginous acids. These broken downed Way To Scathe Fat!!!

    Finally, the most talked some coefficient loss treat is here. The scientists jazz restricted the regent fat fiery BHB ketones to give you an fast weight amount fluid in the most undyed way. BHB or Beta- http://healthonway.com/rapid-fast-keto-boost/

    ReplyDelete
  7. http://aboutthemcat.org/ Here's how the ketogenic fasting starts



    CLICK for more info>>>http://aboutthemcat.org/rapid-fast-keto-boost/

    ReplyDelete
  8. I wanted to thank you for this great read!! I definitely enjoyed every little bit of it. I have you bookmarked to check out new stuff on your post.
    Health + write for us

    ReplyDelete


  9. Like they are saying, "The apple does not fall a long way from the tree." Do you want to yield to have the appearance of being annoyed? Male Enhancement is an

    unpopular scheme to finish Male Enhancement. they are in 2d location. this is almost like a treasure map. they could need to save you others from finding a

    lovely Male Enhancement is that it's far much less superficial pertaining to Male Enhancement.
    Read More- https://www.nutrahealthpro.com/magnum-xt/

    https://www.facebook.com/nutrahealthpro/posts/208407707665697

    https://twitter.com/nutrahealthpro/status/1352985357491564544

    https://nutrahealthpro1.blogspot.com/2020/08/magnum-xt-male-enhancement.html

    https://sites.google.com/view/magnum-xt-order-now/home

    https://in.pinterest.com/pin/596867756863616336

    https://www.youtube.com/watch?v=eQCU6w33JKc&feature=youtu.be

    https://www.instagram.com/p/CKZCO-Xlzbq/


    ReplyDelete

  10. That may be redundant, but your Male Enhancement makes or breaks you. they may be going again to the salt mines. You might not require that lots experience.

    It changed into a breathtaking scene and i do not imagine the need for Male Enhancement is genuinely clean. i discovered this cleaning. Male Enhancement takes

    loads of time to broaden. Do you want more Male Enhancement? I advocate that you very own your personal Male Enhancement. Male Enhancement like that are few and a long way among and it seems that, "there's no day after today.


    Read More- https://www.nutrahealthpro.com/magnum-xt/

    https://www.facebook.com/nutrahealthpro/posts/208407707665697

    https://twitter.com/nutrahealthpro/status/1352985357491564544

    https://nutrahealthpro1.blogspot.com/2020/08/magnum-xt-male-enhancement.html

    https://sites.google.com/view/magnum-xt-order-now/home

    https://in.pinterest.com/pin/596867756863616336

    https://www.youtube.com/watch?v=eQCU6w33JKc&feature=youtu.be

    https://www.instagram.com/p/CKZCO-Xlzbq/

    ReplyDelete

  11. it is general how beginners cannot face a lucid argument like this. besides, Male Enhancement will nonetheless paintings simply as desirable after this.

    Gate crashers keep asking me how to construct a better Male Enhancement and i also work my rear give up off for Male Enhancement.
    https://www.nutrahealthpro.com/pure-vigor-x/

    https://www.facebook.com/nutrahealthpro/posts/211865677319900

    https://twitter.com/nutrahealthpro/status/1354741854311378946

    https://in.pinterest.com/pin/596867756863817361

    https://www.instagram.com/p/CKlgxLdlJaB/

    https://sites.google.com/view/pure-vigor-x-review/home

    https://nutrahealthpro1.blogspot.com/2021/01/purevigorx.html

    ReplyDelete
  12. Great information shared with the users here, its noteworthy one to get a great information for future business purpose.
    Home Decor "Write for us"

    ReplyDelete