CCC 2016: Circle of Life

8

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

HyperNeutrino

Posted 2017-05-30T03:06:32.747

Reputation: 26 575

2I 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. – Dennis – 2017-05-30T03:10:35.557

@Dennis Right, I will remove the tag. What do you suggest for tiebreaking then; earliest submission is another one of my ideas. – HyperNeutrino – 2017-05-30T03:12:02.323

A naive method can easily do 10^4 cells 10^4 times in 1 second. 10^8 bitwise operations is nothing. – feersum – 2017-05-30T03:42:23.677

2I'm voting as unclear for the moment since it's unknowable what is meant by complexity when there are multiple parameters. – feersum – 2017-05-30T03:43:38.817

I haven't really analyzed it but I suspect it's also too trivial for a [tag:fastest-algorithm]. – feersum – 2017-05-30T03:47:38.277

Does a cell count as its own neighbor? – Zgarb – 2017-05-30T03:56:42.007

@FryAmTheEggman Yes; sorry, I fixed that. I was having markdown troubles with such a long line. – HyperNeutrino – 2017-05-30T04:09:07.037

@Zgarb No, it does not. – HyperNeutrino – 2017-05-30T04:09:16.007

@feersum Thank you for your feedback. I decided to change it to a [tag:code-golf] instead because it doesn't have much room for optimizations. – HyperNeutrino – 2017-05-30T04:10:47.657

Your hastebin test case claims to give the MD5 hash with a trailing newline, but actually gives the MD5 hash without a trailing newline. I cannot figure out how to make the hash match either way on your firebaseapp test case. Can you check that again?

– Anders Kaseorg – 2017-05-30T04:41:28.810

@AndersKaseorg Oh, hm, that's strange. I'll update the description. And I'll need to get back to a computer (not this chromebook) for the insane test case because i can't update from my chromebook, so I'll get back to you on that one. Thanks! – HyperNeutrino – 2017-05-30T04:48:10.370

1@feersum, there is a tiny bit of play in [tag: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). – Peter Taylor – 2017-05-30T07:23:43.630

I've created a chatroom where we can discuss optimized algorithms further.

– HyperNeutrino – 2017-05-30T07:32:12.010

I think your description of alive/dead = 1/0 could do with improving. I had to read the pdf to fully understand the challenge, which is fine until the link dies. You should have all the info in your question. – Notts90 supports Monica – 2017-05-30T12:50:30.037

1@Notts90 I hope my latest edit clarifies it more. – HyperNeutrino – 2017-05-30T12:56:48.927

@HyperNeutrino yes much clearer :) – Notts90 supports Monica – 2017-05-30T12:58:53.937

@AndersKaseorg I think I've fixed it. – HyperNeutrino – 2017-05-30T13:07:54.603

Answers

6

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

Adám

Posted 2017-05-30T03:06:32.747

Reputation: 37 779

3

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)

fireflame241

Posted 2017-05-30T03:06:32.747

Reputation: 7 021

1

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

Emigna

Posted 2017-05-30T03:06:32.747

Reputation: 50 798

Asked: 2017-05-30T03:06:32.747

Viewed: 769 times

Active: 2017-05-30T13:08:26.527