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.

Winning Criteria

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.

Test Cases

start, iterations -> end
1001011010, 1000 -> 1100001100
100101011010000, 100 -> 000110101001010
0000000101011000010000010010001111110100110100000100011111111100111101011010100010110000100111111010, 1000 -> 1001111111100010010100000100100100111010010110001011001101010111011011011100110110100000100011011001

Test Case
This test case froze hastebin and exceeded the size limit on pastebin

  • 2
    \$\begingroup\$ I don't think this should be tagged as code golf if byte count is merely a tiebreaker. I'm also not sure if it is a good tiebreaker, as the contest will degenerate to a code golf competition if you can simply port answers to a more concise language to win. \$\endgroup\$
    – Dennis
    May 30, 2017 at 3:10
  • \$\begingroup\$ @Dennis Right, I will remove the tag. What do you suggest for tiebreaking then; earliest submission is another one of my ideas. \$\endgroup\$
    – hyper-neutrino
    May 30, 2017 at 3:12
  • 2
    \$\begingroup\$ I'm voting as unclear for the moment since it's unknowable what is meant by complexity when there are multiple parameters. \$\endgroup\$
    – feersum
    May 30, 2017 at 3:43
  • 1
    \$\begingroup\$ @feersum, there is a tiny bit of play in fastest-algorithm. The naïve algorithm takes Theta(nt) where n is the length of the array and t is the number of evolutions; a faster algorithm takes Theta(n lg t). \$\endgroup\$ May 30, 2017 at 7:23
  • 1
    \$\begingroup\$ @Notts90 I hope my latest edit clarifies it more. \$\endgroup\$
    – hyper-neutrino
    May 30, 2017 at 12:56

3 Answers 3


APL (Dyalog),14 bytes

Prompts for start state as Boolean list and then for number of iterations


Try it online!

 numeric prompt (for Boolean list of start state)

 on that, apply

()⍣⎕ the following tacit function, numeric-prompt times

¯1∘⌽ the argument rotated one step right

 different from (XOR)

1∘⌽ the argument rotated one step left


Jelly, 7 bytes


Try it online!

Extra Test Case (footer for formatting).


     µ¡  - repeat a number of times equal to input 2:
ṙ2         - previous iteration rotated 2 to the left
  ^        - XOR-ed with:
           - (implicit) previous iteration
   ṙ-      - rotate back (by negative 1 to the left)

05AB1E, 6 bytes


Try it online!


F        # input_1 times do
 D       # duplicate last iteration (input_2 the first iteration)
  ÀÀ     # rotate left twice
    ^    # XOR
     Á   # rotate right

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.