Wyobraź sobie „drut”, który ma nspacje. Wyobraź sobie dalej, że w tym przewodzie są „elektrony”. Te elektrony żyją tylko przez jedną jednostkę czasu. Wszelkie przestrzenie w przewodzie, które sąsiadują z dokładnie jednym elektronem, stają się elektronem. W terminologii Game of Life tak właśnie jest B1/S.

Na przykład jest to drut o długości 10, z okresem 62.

Zasady

• Dane wejściowe nto pojedyncza, dodatnia liczba całkowita.
• Wyjściem musi być pojedyncza liczba całkowita oznaczająca okres drutu o długości n.
• Stanem początkowym jest pojedynczy elektron na jednym końcu drutu.
• Okres niekoniecznie obejmuje stan początkowy. Niektóre długości nigdy nie wracają do stanu początkowego, ale wszystkie są okresowe.
• Drut statyczny (tj. Bez elektronów) ma okres 1.
• Warunki brzegowe nie są okresowe. Oznacza to, że drut nie jest w żaden sposób toroidalny.

Przypadki testowe

Specjalne podziękowania dla orlp za stworzenie tej listy. (Sprawdziłem to do n = 27).

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

Tutaj możesz zobaczyć przypadki testowe dla n = 2 do 21 w moim symulatorze Game-of-Life: Wariacje życia .

EDYCJA: sekwencja tutaj została opublikowana jako A268754 !

Python 2, 148 142 87 bajtów

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

Wykorzystuje algorytm wykrywania cyklu Brenta , a tym samym działa szybko.

Napisałem również animację w języku Python (zarówno prace 2, jak i 3). To musi pygletbiec. Możesz wyświetlić animację, uruchamiając:

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

(Nie krępuj się pobrać listy i sprawdzić kod przed uruchomieniem.) Możesz nacisnąć klawisze + i -, aby zwiększyć / zmniejszyć wyświetlaną n .

I na koniec, dla osób zainteresowanych dalszym badaniem tej sekwencji numerów, oto czytelna wersja (została użyta do wygenerowania powyższych przypadków testowych):

# 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 bajtów

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

Wyjaśnienie

Reguła 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

Przypadki testowe

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

Python 2, 68 bajtów

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

Wykrywanie cyklu może być lepsze, ale krok iteracyjny jest przyjemny.

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

Reprezentując tablicę jako liczbę binarną k, aktualizacji można dokonać, biorąc XOR kprzesuniętego jednego w lewo /2i jednego w prawo *2, a następnie skracając do nbajtów jako %2**n.

Python 3 2, 134 121 118 bajtów

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)

Zasadniczo to samo, co moja odpowiedź w języku Pyth , ale dostosowałem ją nieco z powodu braku niektórych wbudowanych funkcji w języku Python.

Wersja bez golfa:

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 bajtów

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

Używa funkcji „skumulowanego punktu stałego” do iteracji do momentu, gdy konfiguracja się powtórzy, i zwraca wszystkie konfiguracje pośrednie jako listę list. Działa to, ponieważ reguły są deterministyczne, a konfiguracja następnej generacji jest funkcją bieżącej konfiguracji. Oznacza to, że gdy ta sama konfiguracja pojawi się ponownie, automaty zakończą cykl.

Po osiągnięciu tego (ostatniej iteracji cyklu) wywołuje funkcję następnej generacji po raz ostatni na ostatnim elemencie listy „historii”, aby uzyskać następną konfigurację (czyli konfigurację początkową cyklu), i znajdź jego indeks w historii. Teraz okres jest po prostu długością (1 + wskaźnik końca cyklu) minus wskaźnik początku cyklu.

W pythonowym pseudokodzie:

                  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] ) ) )

Zestaw testowy zabiera zbyt dużo czasu, aby serwer go zabił, więc musisz użyć zwykłego programu i przetestować go jeden po drugim lub zainstalować Pyth (jeśli nie masz) i użyć skryptu, aby go przetestować.

Galaretka, 19 18 17 bajtów

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

Ten kod oblicza pierwsze 2 ⁿ stanów, więc nie jest szczególnie szybki ani nie zajmuje mało pamięci ...

Wypróbuj online! lub sprawdź pierwsze 16 przypadków testowych .

Wersja alternatywna, 13 bajtów (niekonkurująca)

Wersje Galaretki po tym wyzwaniu mają wbudowane wykrywanie pętli, dzięki czemu rozwiązanie jest zarówno krótsze, jak i bardziej wydajne.

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

To z łatwością obsługuje ostatni przypadek testowy. Wypróbuj online!

Jak to działa

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).

Zauważ, że łącze pomocnicze jest stosowane do 2 ⁿ w pierwszej iteracji, która nie koduje prawidłowego stanu. Jednak ((2 ⁿ ÷ 2) ^ (2 ⁿ × 2))% 2 ⁿ = (2 ^{n - 1} + 2 ^{n + 1} )% 2 ⁿ = 2 ^{n - 1} , co jest jednym z możliwych stanów początkowych.

Ponieważ zapętlamy 2 ⁿ + 1 razy, gwarantujemy, że napotkamy dwa razy stan, dzięki czemu wykrywanie pętli zakończy się powodzeniem.

CJam, 41 34 31 27 25 bajtów

Dzięki Dennis za oszczędność 3 bajtów. Pożyczenie pomysłu z jego odpowiedzi na żelki uratowało kolejne 4.

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

Sprawdź to tutaj.

Wyjaśnienie

Przedstawiam drut po prostu jako liczbę całkowitą (której bity wskazują pozycje elektronów) zamiast używania rzeczywistej listy bitów. Stan jest aktualizowany za pomocą dość prostych obliczeń bitowych.

Aby znaleźć okres, w którym zbieramy wszystkie wyniki pośrednie na stosie, uruchom symulację dla 2 kroków ^n-1 +1, a następnie określ okres jako liczbę elementów od ostatniego wystąpienia stanu końcowego (plus 1).

Oto podział kodu:

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]")

Test

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 bajtów

x!pdaje element o indeksie p, jeśli jest w granicach, w przeciwnym razie 0. noblicza następny krok. g idaje ith krok. c xpodaje okres, jeśli zaczyna się od x. fotacza to wszystko razem.

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]

(Uwaga: wysłane z telefonu, który ma interpretera uścisków, który nie jest w pełni funkcjonalny, więc mogą mieć literówki).

MATL , 38 37 36 35 bajtów

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

Korzysta z pętli, która oblicza nowe stany, dopóki nowy stan nie będzie równy jednemu z poprzednich. Każdy stan jest wektorem zer i jedynek. Wektory te są przechowywane jako rzędy rosnącej tablicy 2D.

Obliczanie każdego nowego stanu odbywa się przez zebranie bieżącego stanu z sekwencją [1,0,1], zachowanie tylko środkowej części i ustawienie dla 0dowolnego wpisu, który nie jest 1.

EDYCJA (13 maja 2016 r.) Kod w poniższym linku został nieco zmodyfikowany zgodnie ze zmianami wprowadzonymi w języku po napisaniu tej odpowiedzi

Wypróbuj 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 bajtów

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

Rozbudował się i trochę nie golfił

-> $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)
}

Trochę wyjaśnienia:

• [op]zmniejsza listę za pomocą op. Na przykład [+] @listsuma@list
• Rto meta-op, który odwraca argumenty podane dla op. Na przykład 1 R- 3spowoduje 2.

C ++, 211 bajtów

Grał w golfa

#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);}

Z dodatkową spacją dla czytelności

#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);
}

Dobra praktyka dla zestawu bitów C ++; oraz wspaniałą edukację zdobywającą wiedzę na temat algorytmu detekcji cyklu Brenta (używanego przez @orlp)

Pyth, 95 bajtów

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

Możesz to wypróbować tutaj .

Pyth, 29 bajtów

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

• Wypróbuj online!
• Zestaw testowy

Używa algorytmu a(n+1) = ((a(n) << 1)^(a(n) >> 1)) % (2 ** N).

Rubinowy, 72 bajty

Funkcja anonimowa.

->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}