CCC 2016: Kreislauf des Lebens

8

Bevor ich anfange, war diese Herausforderung ursprünglich nicht meine

Credits an die Universität von Waterloo. Dies kam vom kanadischen Computerwettbewerb 2016, Senior Problem 5. Hier ist ein anklickbarer Link zum PDF des Wettbewerbs:

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

Hier ist ein Link zur Seite:

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

Herausforderung

Bestimmen Sie bei einem Wrapping-Array mit zwei konstanten Werten die Konfiguration nach der nEntwicklung für eine positive Ganzzahl-Eingabe n. Diese beiden Werte repräsentieren eine lebende Zelle und eine tote Zelle. Entwicklungen funktionieren so:

Evolution!

Nach jeder Iteration lebt eine Zelle, wenn sie in der vorherigen Iteration genau einen lebenden Nachbarn hatte. Noch weniger und es stirbt an Einsamkeit; mehr und es stirbt an Überfüllung. Die Nachbarschaft ist exklusiv: dh jede Zelle hat zwei Nachbarn, nicht drei.

Lassen Sie uns zum Beispiel sehen, wie 1001011010sich etwas entwickeln würde, wo 1sich eine lebende Zelle und 0eine tote Zelle befinden.

(0) 1 0 0 1 0 1 1 0 1 0 (1)
    *   $         %

Die Zelle an der *hat eine tote Zelle auf beiden Seiten, so dass sie an Einsamkeit stirbt.
Die Zelle an der $hat eine lebende Zelle auf der einen Seite und eine tote Zelle auf der anderen Seite. Es wird lebendig.
Das Cel im %hat eine lebende Zelle auf beiden Seiten, so dass es vor Überfüllung nicht geschützt ist.

Gewinnkriterien

Der kürzeste Code gewinnt.

I / O.

Die Eingabe ist eine Liste der Zellenzustände als zwei konsistente Werte und eine Ganzzahl, die die Anzahl der Eingaben in einem vernünftigen Format darstellt. Die Ausgabe soll eine Liste der Zellzustände nach der angegebenen Anzahl von Iterationen sein.

Testfälle

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

Test Case
Dieser Testfall gefror hastebin und die Größenbeschränkung auf Pastebin überschritten

HyperNeutrino
quelle
2
Ich denke nicht, dass dies als Code Golf markiert werden sollte, wenn die Byteanzahl nur ein Tiebreaker ist. Ich bin mir auch nicht sicher, ob es ein guter Tiebreaker ist, da der Wettbewerb zu einem Code-Golf-Wettbewerb ausarten wird, wenn Sie einfach Antworten auf eine präzisere Sprache portieren können, um zu gewinnen.
Dennis
@ Tennis Richtig, ich werde das Tag entfernen. Was schlagen Sie dann zum Tiebreaking vor? Die früheste Einreichung ist eine weitere meiner Ideen.
HyperNeutrino
2
Ich stimme momentan als unklar ab, da nicht bekannt ist, was unter Komplexität zu verstehen ist, wenn es mehrere Parameter gibt.
Feersum
1
@feersum, es gibt ein kleines bisschen Spiel im schnellsten Algorithmus . Der naive Algorithmus nimmt an, Theta(nt)wo ndie Länge des Arrays und tdie Anzahl der Entwicklungen ist; Ein schnellerer Algorithmus dauert Theta(n lg t).
Peter Taylor
1
@ Notts90 Ich hoffe, meine letzte Bearbeitung verdeutlicht es mehr.
HyperNeutrino

Antworten:

6

APL (Dyalog) , 14 Bytes

Fordert zum Startstatus als Boolesche Liste und dann zur Anzahl der Iterationen auf

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

Probieren Sie es online aus!

 numerische Eingabeaufforderung (für boolesche Liste des Startstatus)

 darauf bewerben

()⍣⎕ Die folgende stillschweigende Funktion, numerische Eingabeaufforderungszeiten

¯1∘⌽ Das Argument drehte sich einen Schritt nach rechts

 anders als (XOR)

1∘⌽ Das Argument drehte sich einen Schritt nach links

Adam
quelle
1

05AB1E , 6 Bytes

FDÀÀ^Á

Probieren Sie es online aus!

Erläuterung

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