Stellen Sie sich einen "Draht" mit nLeerzeichen vor. Stellen Sie sich weiter vor, dass sich in diesem Draht "Elektronen" befinden. Diese Elektronen leben nur eine Zeiteinheit. Alle Räume im Draht, die genau einem Elektron benachbart sind, werden zu einem Elektron. In der Game of Life-Terminologie ist dies B1/S.

Dies ist beispielsweise ein Draht der Länge 10 mit der Periode 62.

Regeln

• Input,, nist eine einzelne positive ganze Zahl.
• Die Ausgabe muss eine einzelne Ganzzahl sein, die die Periode eines Drahtes der Länge n angibt.
• Der Ausgangszustand ist ein einzelnes Elektron an einem Ende des Drahtes.
• Der Zeitraum enthält nicht unbedingt den Ausgangszustand. Einige Längen kehren nie in den Ausgangszustand zurück, aber alle sind periodisch.
• Ein statischer Draht (dh einer ohne Elektronen) hat die Periode 1.
• Randbedingungen sind nicht periodisch. Das heißt, der Draht ist in keiner Weise toroidal.

Testfälle

Besonderer Dank geht an orlp für die Erstellung dieser Liste. (Ich habe es bis zu n = 27 überprüft.)

1 1
2 2
3 1
4 6
5 4
6 14
7 1
8 14
9 12
10 62
11 8
12 126
13 28
14 30
15 1
16 30
17 28
18 1022
19 24
20 126
21 124
22 4094
23 16
24 2046
25 252
26 1022
27 56
28 32766
29 60
30 62
31 1
32 62
33 60
34 8190
35 56
36 174762
37 2044
38 8190
39 48
40 2046
41 252
42 254
43 248
44 8190
45 8188

Sie können hier mit meinem Game-of-Life-ähnlichen Simulator Testfälle für n = 2 bis 21 sehen: Variationen des Lebens .

EDIT: die Sequenz hier wurde als A268754 veröffentlicht !

Python 2, 148 142 87 Bytes

n=input()
p=l=1
t=1
h=2
while t!=h:
 if p==l:t,l,p=h,0,p*2
 h=h/2^h*2%2**n;l+=1
print l

Verwendet den Zykluserkennungsalgorithmus von Brent und läuft somit tatsächlich schnell.

Ich habe auch eine Animation in Python geschrieben (beide 2 & 3 Arbeit). Es muss pygletrennen. Sie können die Animation anzeigen, indem Sie Folgendes ausführen:

python -m pip install --user pyglet
curl -s https://gist.githubusercontent.com/orlp/f32d158130259cbae0b0/raw/ | python

(Laden Sie den Inhalt herunter und überprüfen Sie den Code, bevor Sie ihn ausführen.) Sie können die Tasten + und - drücken, um das angezeigte n zu erhöhen / zu verringern .

Und für diejenigen, die diese Zahlenfolge weiter erforschen möchten, ist hier eine lesbare Version (diese wurde verwendet, um die obigen Testfälle zu generieren):

# Brent's cycle detection, modified from wikipedia.
def electron_period(n):
    wire_mask = (1 << n) - 1
    power = lam = 1
    tortoise, hare = 1, 2
    while tortoise != hare:
        if power == lam:
            tortoise = hare
            power *= 2
            lam = 0
        hare = ((hare << 1) ^ (hare >> 1)) & wire_mask
        lam += 1
    return lam

Mathematica, 127 Bytes

p@n_:=Tr[#2-#]&@@Position[#,Last@#]&@NestWhileList[1~Table~n~ArrayPad~1*18~CellularAutomaton~#&,{1}~ArrayPad~{1,n},Unequal,All]

Erläuterung

Regel 18 :

{0,0,0} -> 0
{0,0,1} -> 1
{0,1,0} -> 0
{0,1,1} -> 0
{1,0,0} -> 1
{1,0,1} -> 0
{1,1,0} -> 0
{1,1,1} -> 0

Testfälle

p/@Range[10]
(* {1,2,1,6,4,14,1,14,12,62} *)

Python 2, 68 Bytes

f=lambda n,k=1,l=[]:k in l and-~l.index(k)or f(n,k/2^k*2%2**n,[k]+l)

Die Zykluserkennung könnte besser sein, aber der iterative Schritt ist schön.

k -> k/2^k*2%2**n

Indem das Array als Binärzahl dargestellt wird k, kann die Aktualisierung durchgeführt werden, indem das XOR kum eins nach links /2und eins nach rechts verschoben und *2dann auf nBytes wie abgeschnitten wird %2**n.

Python 3 2, 134 121 118 Bytes

Q=input()
h=[]
n=[0,1]+Q*[0]
while n not in h:h+=[n];n=[0]+[n[d]^n[d+2] for d in range(Q)]+[0]
print len(h)-h.index(n)

Grundsätzlich das Gleiche wie meine Pyth-Antwort , jedoch etwas angepasst, da bestimmte integrierte Funktionen in Python fehlen.

Ungolfed-Version:

length = input()
history = []
new = [0] + [1] + length*[0]
while new not in history:
    history += [new]
    new = [0] + [new[cell]^new[cell+2] for cell in range(length)] + [0]
print len(history) - history.index(new)

Pyth, 39 36 Bytes

L++Zmx@[email protected].[,Z1ZQ)xJyeJ

Verwendet die Funktion "kumulativer Festpunkt", um bis kurz vor der Wiederholung einer Konfiguration zu iterieren, und gibt alle Zwischenkonfigurationen als Liste von Listen zurück. Dies funktioniert, weil die Regeln deterministisch sind und die Konfiguration der nächsten Generation eine Funktion der aktuellen Konfiguration ist. Dies bedeutet, dass die Automaten einen Zyklus abgeschlossen haben, sobald dieselbe Konfiguration wieder erscheint.

Nach Erreichen dieser (der letzten Iteration des Zyklus) ruft er die Funktion next-gen ein letztes Mal für das letzte Element der Liste "history" auf, um die nächste Konfiguration (die Startkonfiguration eines Zyklus) zu erhalten Finden Sie seinen Index in der Geschichte. Jetzt ist die Periode einfach die Länge (1 + Index des Zyklusendes) minus dem Index des Zyklusbeginns.

Im pythonischen Pseudocode:

                  Z = 0
                  Q = eval(input())
L                 def y(b):                # generates next-gen from current(param)
  ++Zm                return [Z] + map(    # adds head zero padding
    x@bd@bhhd             lambda d: b[d] ^ b[1+ 1+ d],  # xor the states of adjacent cells
    Q                     range(Q))        # implicit range in map
    Z                     + [Z]            # adds end zero padding
-lJ.uyN.[,Z1ZQ)   J = repeatTilRecur(lambda N,Y:y(N), padRight([Z,1],Z,Q)); print( len(J) -
                  # N:value; Y:iteration count
  JxJyeJ              J.index( y( J[-1] ) ) )

Die Testsuite benötigt zu viel Zeit, um vom Server beendet zu werden. Daher müssen Sie das reguläre Programm verwenden und einzeln testen oder Pyth installieren (falls nicht) und mithilfe eines Skripts testen.

Jelly, 19 18 17 Bytes

H^Ḥ%®
2*©Ç‘СUµiḢ

Dieser Code berechnet die ersten 2 ⁿ Zustände, ist also nicht besonders schnell oder speichereffizient ...

Probieren Sie es online! oder überprüfen Sie die ersten 16 Testfälle .

Alternative Version, 13 Bytes (nicht konkurrierend)

Jelly-Versionen, die diese Herausforderung nachholen, verfügen über eine integrierte Schleifenerkennung, die eine kürzere und effizientere Lösung ermöglicht.

H^Ḥ%®
2*©ÇÐḶL

Dies erledigt den letzten Testfall mühelos. Probieren Sie es online!

Wie es funktioniert

2*©Ç‘СUµiḢ    Main link. Input: n (integer)

2*             Compute 2 ** n.
  ©            Store the result in the register.
     С        Do the following:
   Ç             Apply the helper link, which updates the state, ...
    ‘            2 ** n + 1 times.
               Collect all 2 ** n + 2 intermediate results in a list.
       U       Upend; reverse the list of results.

        µ      Begin a new, monadic chain. Argument: R (list of results)
          Ḣ    Yield and remove the first element of R (final state).
         i     Find its first index in the remainder or R.
               This is the length of the loop.

H^Ḥ%®        Helper link. Argument: s (state, integer)

H            Halve s. This yields a float, but ^ will cast to integer.
  Ḥ          Double s.
 ^           Compute (s ÷ 2) ^ (s × 2).
    ®        Retrieve the value stored in the register (2 ** n).
   %         Compute ((s ÷ 2) ^ (s × 2)) % (2 ** n).

Beachten Sie, dass die Hilfsverknüpfung in der ersten Iteration auf 2 ⁿ angewendet wird, wodurch kein gültiger Zustand codiert wird. Jedoch ((2 ⁿ ÷ 2) ^ (2 ⁿ × 2))% 2 ⁿ = (2 ^{n - 1} + 2 ^{n + 1} )% 2 ⁿ = 2 ^{n - 1} , die eine der möglichen Ausgangszustände ist.

Da wir 2 ⁿ + 1- mal eine Schleife durchführen , ist garantiert, dass wir zweimal auf einen Zustand stoßen, was die Schleifenerkennung erfolgreich macht.

CJam, 41 34 31 27 25 Bytes

Vielen Dank an Dennis für das Speichern von 3 Bytes. Das Ausleihen einer Idee aus seiner Gelee-Antwort ersparte weitere 4.

2ri#_){__4*^2/W$%}*]W%(#)

Teste es hier.

Erläuterung

Ich stelle den Draht einfach als Ganzzahl dar (deren Bits die Positionen der Elektronen angeben), anstatt eine tatsächliche Bitliste zu verwenden. Der Status wird über relativ einfache bitweise Berechnungen aktualisiert.

Um den Zeitraum zu ermitteln, für den wir alle Zwischenergebnisse auf dem Stapel gesammelt haben, führen Sie die Simulation für 2 ^n-1 + ^1- Schritte durch und bestimmen Sie dann den Zeitraum als Anzahl der Elemente seit dem letzten Auftreten des Endzustands (plus 1).

Hier ist eine Aufschlüsselung des Codes:

2ri#   e# Compute 2^n. This has a 1 in the n+1-th bit and zeroes below it. This is
       e# itself not a valid state but will be turned into 2^(n-1) by the first
       e# update.
_)     e# Duplicate and increment to get number of steps to simulate.
{      e# Repeat that many times...
  __   e#   Duplicate the last state twice.
  4*   e#   Multiply by 4, shifting all bits to the left by two positions.
  ^    e#   XOR - we only keep keep those cells where we have exactly one 1-bit
       e#   between both copies, i.e. those that neighboured a single electron
       e#   but shifted up by one position. We don't need handle the survival rule
       e#   explicitly, since electrons can never be adjacent in the first place.
  2/   e#   Divide by 2 shifting all bits back to the right again.
  W$   e#   Copy the initial number 2^n.
  %    e#   Modulo - this simply sets the first bit to 0.
}*
]      e# Wrap all states in an array.
W%     e# Reverse it.
(      e# Pull off the latest state.
#      e# Find its position in the remainder of the array.
)      e# Increment.

JavaScript (ES6) 99 104

n=>eval("a=[...Array(n)];k={};for(a[0]=i=1;!k[a=a.map((v,i)=>v?0:a[i-1]^a[i+1])];k[a]=i++);i-k[a]")

Prüfung

f = n=>eval("a=[...Array(n)];k={};for(a[0]=i=1;!k[a=a.map((v,i)=>v?0:a[i-1]^a[i+1])];k[a]=i++);i-k[a]")

console.log = x => O.textContent += x + '\n';

;[...Array(45)].map((_, i) => console.log(++i + ' ' + f(i)))

<pre id=O></pre>

Haskell, 170 Bytes

x!pGibt das Element am Index p an, wenn es sich in Grenzen befindet. Andernfalls nberechnet 0 den nächsten Schritt. g igibt den ith Schritt. c xgibt die Periode an, wenn mit x. fWickelt alles zusammen.

n x|l<-length x-1=[mod(x!(p-1)+x!(p+1))2|p<-[0..l],let y!q|q<0=0|q>=l=0|1<2=y!!p]
c x=[i-j|i<-[1..],j<-[0..i-1],let g k=iterate n x!!k,g i==g j]!!0
f n=c$1:map(*0)[2..n]

(Hinweis: Gepostet von einem Telefon mit dem Umarmungsinterpreter, der nicht über alle Funktionen verfügt und möglicherweise Tippfehler enthält.)

MATL , 38 37 36 35 Bytes

1Oi(`t0Y)5BX+8L)1=vt6#Xut0)=fdt?w}A

Hierbei wird eine Schleife verwendet, die neue Zustände berechnet, bis der neue Zustand einem der vorhergehenden entspricht. Jeder Zustand ist ein Vektor aus Nullen und Einsen. Diese Vektoren werden als Zeilen eines wachsenden 2D-Arrays gespeichert.

Die Berechnung jedes neuen Zustands erfolgt, indem der aktuelle Zustand mit der Sequenz verknüpft [1,0,1]wird, nur der zentrale Teil beibehalten und auf 0einen anderen Eintrag gesetzt wird 1.

BEARBEITEN (13. Mai 2016) Der Code unter dem folgenden Link wurde in Übereinstimmung mit den Änderungen, die in der Sprache nach dem Verfassen dieser Antwort vorgenommen wurden, leicht geändert

Probieren Sie es online!

1Oi(            % create initial vector [1,0,0,...,0], with size equal to input
`               % do...while loop
  t0Y)          %   duplicate. Get last row of array: most recent vector
  5BX+8L)       %   compute new vector by convolving the most recent one
                %   with [1,0,1] and keeping only the central part
  1=            %   set ones to 1, rest to 0
  v             %   append to 2D array
  t6#Xu         %   compute vector of unique numeric labels, so that equal rows
  t0)=f         %   indices of entries whose value equals that of the last entry.
                %   This will contain the index of the last entry and possibly
                %   another index, in which case we've found a repetition
  d             %   this will either be empty (which is falsy) or contain the
                %   period, which is a nonzero number (and thus truthy)
  t?            %   duplicate. If non-empty (and nonzero)
    w           %     swap to put the 2D-array at the top of the stack. This is
                %     falsy, because it contains at least one zero, even in the
                %     n=1 case (the array is initiallized to 0 in that case)
                %     So the loop will terminate, with the period left on the stack
  }             %   else
    A           %     this transforms the empty array at the top of the stack
                %     into a true value, so that the loop will continue
                %   implicitly end if
                % implicitly end loop
                % implicitly display stack contents (period)

Perl 6, 81 Bytes

{my@h=my$w=2;@h.push($w=$w/2+^$w*2%2**$_)while 2>@h.grep($w);[R-] @h.grep($w,:k)}

Erweitert und etwas ungolfed

-> $n {
    my @history = my $wire = 2;
    while 2 > @history.grep($wire) {
        @history.push($wire = $wire/2 +^ $wire*2 % 2**$n)
    }
    [R-] @history.grep($wire,:k)
}

Ein bisschen Erklärung:

• [op]reduziert die Liste mit op. Zum Beispiel [+] @listwird summieren@list
• Rist eine Meta-Operation, die die Argumente einer Operation umkehrt. Zum Beispiel 1 R- 3ergibt 2.

C ++, 211 Bytes

Golf gespielt

#include <bitset>
#include <cstdio>
#define B std::bitset<1<<10>
B m,t(1),h(2);int main() {int p,l;for(scanf("%d",&p);p--;m.set(p));
for(p=l=1;t!=h;h=(h>>1^h<<1)&m,l++)p==l?t=h,p*=2,l=0:0;return !printf("%d",l);}

Mit zusätzlichen Leerzeichen für die Lesbarkeit

#include <bitset>
#include <cstdio>
#define B std::bitset<1<<10>
B m,t(1),h(2);
int main() {    
    int p,l;
    for(scanf("%d",&p);p--;m.set(p));
    for(p=l=1;t!=h;h=(h>>1^h<<1)&m,l++)p==l?t=h,p*=2,l=0:0;    
    return !printf("%d",l);
}

Gute Praxis für das Bitset von C ++; und eine großartige Aufklärung über den Zykluserkennungsalgorithmus von Brent (wie er von @orlp verwendet wird)

Pyth, 95 Bytes

J.[ZQ[1)K_1=bYW<K0=NY aN?hJZ?htJ1ZFTr1tlJ aN?@JTZ?x@JhT@JtT1Z) aN?eJZ?@J_2 1Z=JN=KxbJ abJ;-tlbK

Sie können es hier ausprobieren .

Pyth, 29 Bytes

J^2QL%x/b2*b2JK.uyN1;-lKxKyeK

• Probieren Sie es online!
• Testsuite

Verwendet den Algorithmus a(n+1) = ((a(n) << 1)^(a(n) >> 1)) % (2 ** N).

Ruby, 72 Bytes

Anonyme Funktion.

->n{s=[w=1];c=p
(j=s.index w=w*2%2**n^w/2
j ?c=s.size-j:s<<w)while !c
c}