PROBLEM STATEMENT
We are interested in how much biological diversity can be generated by very
simple life and death rules. The environment is a line of cells. Each cell
may either be alive or dead. Each cell has a left neighbor and a right
neighbor. In each successive generation, the status of each cell depends only
on the status of it and its two neighbors in the previous generation. A "rule"
for the propogation of life is the set of patterns that will produce a live
cell. A cell will be alive in the next generation if and only if in this
generation it and its two neighbors match one of the rule's patterns. For
example, a rule might be {ADD, AAD} meaning that a cell will be alive in the
next generation if and only if in this generation either (ADD means
alive-dead-dead) its left neighbor was alive and both it and its right neighbor
were dead or (AAD) it and its left neighbor were alive and its right neighbor
was dead. Since there are only 8 possible patterns, a rule will contain
between 0 and 8 patterns inclusive.
We will define the "diversity" in a generation to be the number of different
finite sizes of alive groups. An alive group is a contiguous set of alive
cells. So if some generation were ...AADADDDADDDAAAADDADDA... its diversity
would be equal to 2 since it contains an alive group of size 4 and several of
size 1. The groups on either end are infinite so they are not counted.
Create a class CellLine that contains the method diversity that takes an
initial configuration of cells and the desired generation as inputs and returns
the maximum amount of diversity that can be achieved on the desired generation
by using a simple life and death rule. Assume that dead cells extend
infinitely to both the left and the right of the input pattern.
DEFINITION
Class: CellLine
Method: diversity
Parameters: String, int
Returns: int
Method Signature (be sure your method is public): int diversity(String init,
int gen);
init will contain only A (alive) and D (dead). All cells on either end of init
are originally dead. gen is the number of the desired generation, where 0
refers to init.
TopCoder will ensure the validity of the inputs. Inputs are valid if all of the
following criteria are met:
- gen is between 0 and 300 inclusive
- init contains between 1 and 50 characters inclusive
- each character in init is uppercase A or D
EXAMPLES
(quotes shown for clarity only)
1) "ADDAADD",0: return 2
This initial generation has a group of size 1 and a group of size 2
2) "ADDAADD",3; return 3
One rule which will produce diversity of 3 is {ADD,AAD,DAA,DAD}:
generation 0 ...DDADDAADD....
generation 1 ..DDDAADAAADD...
generation 2 ...DDAADADAADD..
generation 3 ...DDAADADAAADD.
Generation 3 has groups of three different sizes (2,1, and 3).
3) "ADDAADD",300: return 8