GameOfLife

TCI '02 Round 4 · 2002-10-30 · by lars2520

TCI '02 Round 4 · 2002-10-30 · by lars2520 · Simulation

Show categories

Class Name: GameOfLife

Return Type: int

Method Name: alive

Arg Types: (vector<string>, string, int)

Problem Statement

In 1970 John Conway published a paper outlining how very simple rules could lead to very interesting, complicated behavior. His game was based (very roughly) on how biological organisms work. In his game, Conway put a number of "living" organisms on a two dimensional grid. He then applied four rules to all locations on the grid a number of times. As these rules were repeatedly applied, complex behaviors emerged from these four simple rules.

The four rules were based on the number of "living" organisms that were adjacent to each space in the grid. In his game, he defined two grid spaces to be adjacent if they were immediately next to each other, or diagonal to each other. Thus every space in the grid has 8 other spaces in the grid which are adjacent to it.

The original four rules were as follows.
1) If a grid space is adjacent to less than 2 living organisms, any living organism there dies due to its isolation.
2) If a grid space is adjacent to exactly 2 living organisms, any living organism there stays alive if it was alive.
3) If a grid space is adjacent to exactly 3 living organisms, any living organism there stays alive if it was alive, and if there is no living organism, one is "born" there.
4) If a grid space is adjacent to more than 3 living organisms, any living organism there dies due to over crowding.

For this problem, we would like to be able to specify these rules, rather than hard coding them. Thus, part of the input will be a String which specifies the rules. Each character in the String will be one of three characters: 'D', 'S', 'B'. Each character will indicate the effect of the number of adjacent living organisms equal to its index in the String. Thus, the first character in the String (index = 0) will indicate what should happen to organisms on a grid space with 0 adjacent living organisms. In the String, 'D' indicates that organisms on grid spaces adjacent to the number of living organisms equal to the index of the character will die. 'S' indicates that organisms should remain alive, but not be born. 'B' indicates that an organism should be born if it is not already alive, and continue to live if it was already alive. Thus, the input String corresponding to the above 4 rules would be: "DDSBDDDDD" because organisms die whenever they are adjacent to 0, 1, 4, 5, 6, 7, or 8 other living organisms, remain alive when adjacent to exactly 2 other organisms, and are born when adjacent to exactly 3 other organisms.

Your task is, given an input String[], start, showing the initial locations of living organisms, and a String of rules determine how many living organisms there are after the rules have been applied generations times.

Notes

In the input String[], start, 'X' represents a live organism, and '.' represents an empty space or dead organism.
In calculating the number of living organisms adjacent to a grid location, you should "wrap around". Thus organisms on the far left are adjacent to organisms on the far right, and all four corners are adjacent to each other.
Each time the rules are applied, they are applied simultaneously to all grid spaces. Thus, we count how many adjacent organisms there are for every grid space before applying the rules.

Constraints

start contains between 1 and 50 elements inclusive, each of which contains between 1 and 50 characters, inclusive.
start contains only the characters 'X' and '.'
rules contains exactly 9 characters, each of which is 'D', 'S', or 'B'
generations is between 0 and 1000, inclusive
each element of start contains the same number of characters as each other element of start

Examples

{"...XXX....X.XX.XX.X..XXX...X........X.....X.X...X.",".XX..XX........X.........X...XXXXX.X..X.X....X...X","..XXXXX...XX.XX....XX.XXX.X.XXX.X.XXXXX.X....X....",".X....X...X.XX.X....XX.X..X....XX.XX.X...XX..X..XX","X..X.XXX.XXX...X.X..X.XX.X.X..XX..X...XXX....X..XX",".X..X.XX.X..X.XX..XXX....XXXX.XX..XXXX.X..X....XX.","X.X...XXXX.XX..X.XXX...XXXXXX.X.XXXX.X.X....X..X.X","....XX..X.X....XX.X.XXXX...XXXXX.XXX..X.XXXXXXX..X",".XXX.X.XX..XX.X.XX....X.X.XX.XXX........XX.X..XX..",".X...X.X.X.....X...X.X......XX.X.....X.XX.X.XX..X.","X.XX.XXX...X...X.....X..X.X..X..X...X.....XX....XX","X..X....X...X..XX.XXX..X.X...........X.XX....X.X..","XXXXX..X..XX.....X..X...X.....X.....X..XXX.X..X.XX","X....XXXX.X..........X..XX...X..X.X....XXX.XX.X...","....X...X.X.X.X..X....X.X..X.X..XX.X.XX....XXX.X..","...XX..XX.X.X..X....X..X.X..XX..X.......X...X..X..",".....XX.XX...XXX..X..XX.XX..X.X..X.X..X.....X...XX","....XXX......X.X.X.X.X.......XXXX.X....X...XXXX.XX",".XXX.X....XX.X.....X.X..X.X.X....XX.XXX...X..XX..X","X.XX..X..X.......XX....XX....X....X..X.XX..X.XX...","....X.X..X.X.X........XX.X.X...X.....X.....XX.X...","XX..XX..........X..X..X..X...X.XXX.X...XX...X.XX.X","XX.....XX.XX.XX....X.XX.X..XX.X......X.X.X.X.X..XX",".....X..XX.X...X....X...X..X...XX.X.XX.XX.X.XX....","X.X.....XX.XXX....XX.X.............XX.XXXXX...X...","X.X...X...X..XXX...XX...X...X.X.X.X...XX.X...X....","XXXX..XX.X.XXX........X...XX..X.....XX....X.XXX...","..X..X..X.X...XX.X..X.X..XX.XX.X...X.X.....X.XXX.X","..XX.XX....X.....X...X...XX.X.X.XX..X.XX.X..XXXX..","X....XX.X..XX..XX....XXXX...XX..X..X.XX..XXX....XX","X..X.....X.XX..X.XX.X.X....X.X.X..X..XXXXXX.XX.X.X","X....X.X.X.XXX.X...XXXX...X.XX.XXX....X....XX.XX.X",".X.XX....XX.....X.....X.X..XX...X......X....XX..XX","..XXXXX.X....X.XXX.X.XX.X.X.X.X....X......X....X.X","...X..X........XX..X.XX.X..X..XX.XX.X.X.X...X..X..","X.X....XX..XX..X..X..........X.X.X....X.XX..X.....","X.XX.XXX..XX.....X.X.XX.XX..X..X........XXXXX.....","..X.X.XX.X.X.XX..X...XX...X......X.X...X.XXX......","..XXXX.X..X.XX...XX.X...X.X.X...X.X.X......X...X..",".....X.XX.....X.XXX..XX.XXX...XX.XXX.X........XXX.",".XX.....XXXXXX.X...X.......XXXX.X..XX..XX.XX.....X","...X.X....X.XX.X....X.X...X.X.X.XX.XX.XX.....X.XXX","..X.X..XXXXX.X...X...X...X..XXX........X..X...X...","X.X..X.XXXX..X.X......X.XX.XXXX...........XX......",".X.XX.X.XXXXX.XX.......XX.X...X.....X...XXX..X..X.",".....XX..X..XXX...X...XX...X..XXXXXX......XX.XX.X.",".X.X.....X.X....X...X..X..XXX...X...X..XX...X....X","X..X...X...XX...XX..XX...X....X...X.X.X.XXXXX.....","XX.....X.....X.X........XX.X.XX.....X..X.XXX..X.XX","X....XX.X.XX.X.X.X..X..X..X...XXX.X.X..X........X."}
"DDSBDDDDD"
1000
Returns: 72

{"...XXX....X.XX.XX.X..XXX...X........X.....X.X...X.",".XX..XX........X.........X...XXXXX.X..X.X....X...X","..XXXXX...XX.XX....XX.XXX.X.XXX.X.XXXXX.X....X....",".X....X...X.XX.X....XX.X..X....XX.XX.X...XX..X..XX","X..X.XXX.XXX...X.X..X.XX.X.X..XX..X...XXX....X..XX",".X..X.XX.X..X.XX..XXX....XXXX.XX..XXXX.X..X....XX.","X.X...XXXX.XX..X.XXX...XXXXXX.X.XXXX.X.X....X..X.X","....XX..X.X....XX.X.XXXX...XXXXX.XXX..X.XXXXXXX..X",".XXX.X.XX..XX.X.XX....X.X.XX.XXX........XX.X..XX..",".X...X.X.X.....X...X.X......XX.X.....X.XX.X.XX..X.","X.XX.XXX...X...X.....X..X.X..X..X...X.....XX....XX","X..X....X...X..XX.XXX..X.X...........X.XX....X.X..","XXXXX..X..XX.....X..X...X.....X.....X..XXX.X..X.XX","X....XXXX.X..........X..XX...X..X.X....XXX.XX.X...","....X...X.X.X.X..X....X.X..X.X..XX.X.XX....XXX.X..","...XX..XX.X.X..X....X..X.X..XX..X.......X...X..X..",".....XX.XX...XXX..X..XX.XX..X.X..X.X..X.....X...XX","....XXX......X.X.X.X.X.......XXXX.X....X...XXXX.XX",".XXX.X....XX.X.....X.X..X.X.X....XX.XXX...X..XX..X","X.XX..X..X.......XX....XX....X....X..X.XX..X.XX...","....X.X..X.X.X........XX.X.X...X.....X.....XX.X...","XX..XX..........X..X..X..X...X.XXX.X...XX...X.XX.X","XX.....XX.XX.XX....X.XX.X..XX.X......X.X.X.X.X..XX",".....X..XX.X...X....X...X..X...XX.X.XX.XX.X.XX....","X.X.....XX.XXX....XX.X.............XX.XXXXX...X...","X.X...X...X..XXX...XX...X...X.X.X.X...XX.X...X....","XXXX..XX.X.XXX........X...XX..X.....XX....X.XXX...","..X..X..X.X...XX.X..X.X..XX.XX.X...X.X.....X.XXX.X","..XX.XX....X.....X...X...XX.X.X.XX..X.XX.X..XXXX..","X....XX.X..XX..XX....XXXX...XX..X..X.XX..XXX....XX","X..X.....X.XX..X.XX.X.X....X.X.X..X..XXXXXX.XX.X.X","X....X.X.X.XXX.X...XXXX...X.XX.XXX....X....XX.XX.X",".X.XX....XX.....X.....X.X..XX...X......X....XX..XX","..XXXXX.X....X.XXX.X.XX.X.X.X.X....X......X....X.X","...X..X........XX..X.XX.X..X..XX.XX.X.X.X...X..X..","X.X....XX..XX..X..X..........X.X.X....X.XX..X.....","X.XX.XXX..XX.....X.X.XX.XX..X..X........XXXXX.....","..X.X.XX.X.X.XX..X...XX...X......X.X...X.XXX......","..XXXX.X..X.XX...XX.X...X.X.X...X.X.X......X...X..",".....X.XX.....X.XXX..XX.XXX...XX.XXX.X........XXX.",".XX.....XXXXXX.X...X.......XXXX.X..XX..XX.XX.....X","...X.X....X.XX.X....X.X...X.X.X.XX.XX.XX.....X.XXX","..X.X..XXXXX.X...X...X...X..XXX........X..X...X...","X.X..X.XXXX..X.X......X.XX.XXXX...........XX......",".X.XX.X.XXXXX.XX.......XX.X...X.....X...XXX..X..X.",".....XX..X..XXX...X...XX...X..XXXXXX......XX.XX.X.",".X.X.....X.X....X...X..X..XXX...X...X..XX...X....X","X..X...X...XX...XX..XX...X....X...X.X.X.XXXXX.....","XX.....X.....X.X........XX.X.XX.....X..X.XXX..X.XX","X....XX.X.XX.X.X.X..X..X..X...XXX.X.X..X........X."}
"SSSBDDDDD"
1000
Returns: 916

{"...XXX....X.XX.XX.X..XXX...X........X.....X.X...X.",".XX..XX........X.........X...XXXXX.X..X.X....X...X","..XXXXX...XX.XX....XX.XXX.X.XXX.X.XXXXX.X....X....",".X....X...X.XX.X....XX.X..X....XX.XX.X...XX..X..XX","X..X.XXX.XXX...X.X..X.XX.X.X..XX..X...XXX....X..XX",".X..X.XX.X..X.XX..XXX....XXXX.XX..XXXX.X..X....XX.","X.X...XXXX.XX..X.XXX...XXXXXX.X.XXXX.X.X....X..X.X","....XX..X.X....XX.X.XXXX...XXXXX.XXX..X.XXXXXXX..X",".XXX.X.XX..XX.X.XX....X.X.XX.XXX........XX.X..XX..",".X...X.X.X.....X...X.X......XX.X.....X.XX.X.XX..X.","X.XX.XXX...X...X.....X..X.X..X..X...X.....XX....XX","X..X....X...X..XX.XXX..X.X...........X.XX....X.X..","XXXXX..X..XX.....X..X...X.....X.....X..XXX.X..X.XX","X....XXXX.X..........X..XX...X..X.X....XXX.XX.X...","....X...X.X.X.X..X....X.X..X.X..XX.X.XX....XXX.X..","...XX..XX.X.X..X....X..X.X..XX..X.......X...X..X..",".....XX.XX...XXX..X..XX.XX..X.X..X.X..X.....X...XX","....XXX......X.X.X.X.X.......XXXX.X....X...XXXX.XX",".XXX.X....XX.X.....X.X..X.X.X....XX.XXX...X..XX..X","X.XX..X..X.......XX....XX....X....X..X.XX..X.XX...","....X.X..X.X.X........XX.X.X...X.....X.....XX.X...","XX..XX..........X..X..X..X...X.XXX.X...XX...X.XX.X","XX.....XX.XX.XX....X.XX.X..XX.X......X.X.X.X.X..XX",".....X..XX.X...X....X...X..X...XX.X.XX.XX.X.XX....","X.X.....XX.XXX....XX.X.............XX.XXXXX...X...","X.X...X...X..XXX...XX...X...X.X.X.X...XX.X...X....","XXXX..XX.X.XXX........X...XX..X.....XX....X.XXX...","..X..X..X.X...XX.X..X.X..XX.XX.X...X.X.....X.XXX.X","..XX.XX....X.....X...X...XX.X.X.XX..X.XX.X..XXXX..","X....XX.X..XX..XX....XXXX...XX..X..X.XX..XXX....XX","X..X.....X.XX..X.XX.X.X....X.X.X..X..XXXXXX.XX.X.X","X....X.X.X.XXX.X...XXXX...X.XX.XXX....X....XX.XX.X",".X.XX....XX.....X.....X.X..XX...X......X....XX..XX","..XXXXX.X....X.XXX.X.XX.X.X.X.X....X......X....X.X","...X..X........XX..X.XX.X..X..XX.XX.X.X.X...X..X..","X.X....XX..XX..X..X..........X.X.X....X.XX..X.....","X.XX.XXX..XX.....X.X.XX.XX..X..X........XXXXX.....","..X.X.XX.X.X.XX..X...XX...X......X.X...X.XXX......","..XXXX.X..X.XX...XX.X...X.X.X...X.X.X......X...X..",".....X.XX.....X.XXX..XX.XXX...XX.XXX.X........XXX.",".XX.....XXXXXX.X...X.......XXXX.X..XX..XX.XX.....X","...X.X....X.XX.X....X.X...X.X.X.XX.XX.XX.....X.XXX","..X.X..XXXXX.X...X...X...X..XXX........X..X...X...","X.X..X.XXXX..X.X......X.XX.XXXX...........XX......",".X.XX.X.XXXXX.XX.......XX.X...X.....X...XXX..X..X.",".....XX..X..XXX...X...XX...X..XXXXXX......XX.XX.X.",".X.X.....X.X....X...X..X..XXX...X...X..XX...X....X","X..X...X...XX...XX..XX...X....X...X.X.X.XXXXX.....","XX.....X.....X.X........XX.X.XX.....X..X.XXX..X.XX","X....XX.X.XX.X.X.X..X..X..X...XXX.X.X..X........X."}
"DDDSSBDDD"
1000
Returns: 268

{"........................","........................","........................","........................","........................","........................","........................","........................",".........XXX.XX.........","..........X..X..........","..........X..XX.........","........................","........................","........................","........................","........................","........................","........................","........................"}
"DBDBDBDBD"
8
Returns: 80

The replicator

{"......"
,"......"
,".XXXX."
,"......"
,"......"}
"DDSBDDDDD"
2
Returns: 6

after 1 application of the rules we have: {"......", "..XX..", "..XX..", "..XX..", "......"} This is because the grid space that we changed from '.' to 'X' had 3 adjacent 'X's, and by our rules, an organism is born when there are 3 adjacent living organisms. The two 'X's at the ends of the line of 'X's are only adjacent to 1 other 'X', and thus, by the rules, they die. after 2 application of the rules we have: {"......", "..XX..", ".X..X.", "..XX..", "......"} Since there are 6 'X's, there are 6 living organisms, thus we return 6.

{"XX","XX"}
"DDSBDDDDD"
1
Returns: 0

Because we wrap around edges, every space in the grid is adjacent to 8 living organisms, thus they all die after the first application of the rules.

{"........XXX"
,"..........X"
,".........X."
,"..........."
,"..........."
,"..........."
,"..........."
,"..........."
,"..........."
,"..........."
,"..........."}
"DDSBDDDDD"
1000
Returns: 5

The well known glider moves up 1 sqaure and 1 sqaure to the right every 4 generations.

10)

{".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,"......................XXX.XX......................"
,".......................X..X......................."
,".......................X..XX......................"
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."}
"DBDBDBDBD"
16
Returns: 80

The famous replicator rule. If the grid extended infinitely, this rule would make an infinite number of copies of the original pattern! However, because our grid wraps around, the replicator no longer replicates the original pattern after about 16 generations.

14)

{
"........................................",
"........................................",
"..XX....................................",
"X....X..................................",
"......X.................................",
"X.....X.................................",
".XXXXXX.................................",
"........................................",
"........................................"
}
"DDSBDDDDD"
1000
Returns: 13

moves right 2 every 4 generations

15)

{"X"}
"BDDDDDDDD"
2
Returns: 1

Note that the 8 squares adjacent to (0,0) are all (0,0)

Submissions are judged against all 37 archived test cases, of which 10 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class GameOfLife with a public method int alive(vector<string> start, string rules, int generations) · 37 test cases · 2 s / 256 MB per case