Before I begin, this challenge was not mine originally
Credits to The University of Waterloo. This came from the Canadian Computing Competition 2016, Senior Problem 5. Here is a clickable link to the contest PDF:
Here is a link to the site:
Given a wrapping array of two constant values, determine the configuration after
n evolutions for positive integer input
n. These two values represent a living cell and a dead cell. Evolutions work like this:
After each iteration, a cell is alive if it had exactly one living neighbor in the previous iteration. Any less and it dies of loneliness; any more and it dies of overcrowding. The neighbourhood is exclusive: i.e. each cell has two neighbours, not three.
For example, let's see how
1001011010 would evolve, where
1 is a living cell and
0 is a dead cell.
(0) 1 0 0 1 0 1 1 0 1 0 (1) * $ %
The cell at the
* has a dead cell on both sides of it so it dies of lonliness.
The cell at the
$ has a living cell on one side of it and a dead cell on the other. It becomes alive.
The cel at the
% has a living cell on both sides of it so it stays dead from overcrowding.
Shortest code wins.
Input will be a list of the cell states as two consistent values, and an integer representing the number of inputs, in some reasonable format. Output is to be a list of the cell states after the specified number of iterations.
start, iterations -> end 1001011010, 1000 -> 1100001100 100101011010000, 100 -> 000110101001010 0000000101011000010000010010001111110100110100000100011111111100111101011010100010110000100111111010, 1000 -> 1001111111100010010100000100100100111010010110001011001101010111011011011100110110100000100011011001
This test case froze hastebin and exceeded the size limit on pastebin
nis the length of the array and
tis the number of evolutions; a faster algorithm takes
Theta(n lg t). \$\endgroup\$