8
\$\begingroup\$

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:

http://cemc.uwaterloo.ca/contests/computing/2016/stage%201/seniorEn.pdf

Here is a link to the site:

http://cemc.uwaterloo.ca/contests/past_contests.html

Challenge

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:

Evolution!

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.

I/O

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

\$\endgroup\$
  • 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 '17 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\$ – HyperNeutrino May 30 '17 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 '17 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\$ – Peter Taylor May 30 '17 at 7:23
  • 1
    \$\begingroup\$ @Notts90 I hope my latest edit clarifies it more. \$\endgroup\$ – HyperNeutrino May 30 '17 at 12:56
6
\$\begingroup\$

APL (Dyalog),14 bytes

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

(1∘⌽≠¯1∘⌽)⍣⎕⊢⎕

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

\$\endgroup\$
3
\$\begingroup\$

Jelly, 7 bytes

ṙ2^ṙ-µ¡

Try it online!

Extra Test Case (footer for formatting).

Explanation

ṙ2^ṙ-µ¡
     µ¡  - 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)
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 6 bytes

FDÀÀ^Á

Try it online!

Explanation

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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