Imagine un "cable" que tiene nespacios. Imagine además que hay "electrones" en ese cable. Estos electrones solo viven por una unidad de tiempo. Cualquier espacio en el cable adyacente a exactamente un electrón se convierte en un electrón. En la terminología de Game of Life, esto es B1/S.

Por ejemplo, este es un cable de longitud 10, con período 62.

Reglas

• La entrada, nes un entero positivo único.
• La salida debe ser un entero entero que denote el período de un cable de longitud n.
• El estado inicial es un solo electrón en un extremo del cable.
• El período no incluye necesariamente el estado inicial. Algunas longitudes nunca vuelven al estado inicial, pero todas son periódicas.
• Un cable estático (es decir, uno sin electrones) tiene período 1.
• Las condiciones de contorno no son periódicas. Es decir, el cable no es toroidal de ninguna manera.

Casos de prueba

Un agradecimiento especial a orlp por producir esta lista. (Lo he verificado hasta 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

Puede ver casos de prueba para n = 2 a 21 aquí con mi simulador de Game-of-Life-esque: Variations of Life .

EDITAR: ¡ la secuencia aquí ha sido publicada como A268754 !

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

Utiliza el algoritmo de detección de ciclo de Brent y, por lo tanto, en realidad funciona rápido.

También he escrito una animación en Python (ambos funcionan en 2 y 3). Necesita pygletcorrer. Puede ver la animación ejecutando:

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

(Siéntase libre de descargar la esencia e inspeccionar el código antes de ejecutarlo). Puede presionar las teclas + y - para aumentar / disminuir la n que se visualiza.

Y finalmente, para aquellos interesados ​​en explorar más esta secuencia numérica, aquí hay una versión legible (esto se usó para generar los casos de prueba anteriores):

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

Explicación

Regla 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

Casos de prueba

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)

La detección del ciclo podría ser mejor, pero el paso iterativo es bueno.

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

Al representar la matriz como un número binario k, la actualización se puede realizar tomando el XOR de kuno desplazado hacia la izquierda /2y otro hacia la derecha *2, y luego truncando a nbytes como %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)

Básicamente lo mismo que mi respuesta de Pyth , pero lo adapté un poco debido a la falta de ciertas funciones integradas en Python.

Versión sin golf:

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

Utiliza la función de "punto fijo acumulativo" para iterar hasta justo antes de que se repita una configuración, y devuelve todas las configuraciones intermedias como una lista de listas. Esto funciona porque las reglas son deterministas y la configuración de la próxima generación es una función de la configuración actual. Esto significa que una vez que la misma configuración aparece nuevamente, los autómatas han completado un ciclo.

Después de llegar a eso (la última iteración del ciclo), llama a la función next-gen por última vez en el último elemento de la lista "history", para obtener la siguiente configuración (que es la configuración inicial de un ciclo), y encuentra su índice en la historia. Ahora el período es simplemente la duración (1 + índice de finalización del ciclo) menos el índice de inicio del ciclo.

En pseudocódigo pitónico:

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

El conjunto de pruebas lleva demasiado tiempo para que el servidor lo elimine, por lo que deberá usar el programa normal y probarlo uno por uno, o instalar Pyth (si no lo ha hecho) y usar un script para probarlo.

Jalea, 19 18 17 bytes

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

Este código calcula los primeros 2 ⁿ estados, por lo que no es particularmente rápido ni eficiente en memoria ...

Pruébalo en línea! o verificar los primeros 16 casos de prueba .

Versión alternativa, 13 bytes (no competitiva)

Las versiones de Jelly posteriores a este desafío tienen detección de bucle incorporada, lo que permite una solución que es más corta y más eficiente.

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

Esto maneja el último caso de prueba con facilidad. Pruébalo en línea!

Cómo funciona

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

Tenga en cuenta que el enlace auxiliar se aplica a 2 ⁿ en la primera iteración, que no codifica un estado válido. Sin embargo, ((2 ⁿ ÷ 2) ^ (2 ⁿ × 2))% 2 ⁿ = (2 ^{n - 1} + 2 ^{n + 1} )% 2 ⁿ = 2 ^{n - 1} , que es uno de los posibles estados iniciales.

Como hacemos un bucle 2 ⁿ + 1 veces, tenemos la garantía de encontrar un estado dos veces, lo que hace que la detección del bucle sea exitosa.

CJam, 41 34 31 27 25 bytes

Gracias a Dennis por guardar 3 bytes. Tomar prestada una idea de su respuesta de Jelly salvó otras 4.

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

Pruébalo aquí.

Explicación

Estoy representando el cable simplemente como un número entero (cuyos bits indican las posiciones de los electrones) en lugar de usar una lista real de bits. El estado se actualiza mediante cálculos bit a bit bastante simples.

Para encontrar el período, recopilamos todos los resultados intermedios en la pila, ejecutamos la simulación para 2 ^n-1 +1 pasos, y luego determinamos el período como el número de elementos desde la última aparición del estado final (más 1).

Aquí hay un desglose del código:

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

Prueba

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!pda el elemento en el índice p si está dentro de los límites, de lo contrario, 0. ncalcula el siguiente paso. g ida el ipaso th. c xda el período, si comienza con x. flo envuelve todo junto.

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]

(Nota: publicado desde un teléfono que tiene el intérprete de abrazos, que no tiene todas las funciones, por lo que podría tener errores tipográficos).

MATL , 38 37 36 35 bytes

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

Esto usa un ciclo que sigue calculando nuevos estados hasta que el nuevo estado sea igual a cualquiera de los anteriores. Cada estado es un vector de ceros y unos. Estos vectores se almacenan como filas de una matriz 2D en crecimiento.

El cálculo de cada nuevo estado se realiza convolucionando el estado actual con la secuencia [1,0,1], manteniendo solo la parte central y configurando 0cualquier entrada que no lo sea 1.

EDITAR (13 de mayo de 2016) El código en el siguiente enlace se ha modificado ligeramente de acuerdo con los cambios introducidos en el idioma después de que se escribió esta respuesta

Pruébalo en línea!

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

Expandido y ungolfed un poco

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

Un poco de explicación:

• [op]reduce la lista usando op. Por ejemplo [+] @listsumará@list
• Res un meta-op que invierte los argumentos dados a un op. Por ejemplo 1 R- 3resultará en 2.

C ++, 211 bytes

Golfed

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

Con espacio en blanco agregado para facilitar la lectura

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

Buena práctica para el bitset de C ++; y una gran educación aprendiendo sobre el algoritmo de detección de ciclo de Brent (como lo utiliza @orlp)

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

Puedes probarlo aquí .

Pyth, 29 bytes

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

• Pruébalo en línea!
• Banco de pruebas

Utiliza el algoritmo a(n+1) = ((a(n) << 1)^(a(n) >> 1)) % (2 ** N).

Ruby, 72 bytes

Función anónima.

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