Imaginez un "fil" qui a des nespaces. Imaginez de plus qu'il y a des "électrons" dans ce fil. Ces électrons ne vivent que pour une unité de temps. Tous les espaces dans le fil qui sont adjacents à exactement un électron deviennent un électron. Dans la terminologie de Game of Life, c'est B1/S.

Par exemple, il s’agit d’un fil de longueur 10, de période 62.

Règles

• L'entrée, nest un seul entier positif.
• La sortie doit être un entier indiquant la période d’un fil de longueur n.
• L'état de départ est un seul électron à une extrémité du fil.
• La période n'inclut pas nécessairement l'état de départ. Certaines longueurs ne reviennent jamais à l'état de départ, mais elles sont toutes périodiques.
• Un fil statique (c'est-à-dire sans électrons) a la période 1.
• Les conditions aux limites ne sont pas périodiques. C'est-à-dire que le fil n'est en aucun cas toroïdal.

Cas de test

Un merci spécial à Orlp pour la production de cette liste. (Je l'ai vérifié jusqu'à 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

Vous pouvez voir des scénarios de test pour n = 2 à 21 ici avec mon simulateur Game-of-Life-esque: Variations of Life .

EDIT: la séquence ici a été publiée sous le numéro A268754 !

Python 2, 148 142 87 octets

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

Utilise l'algorithme de détection de cycle de Brent et fonctionne donc rapidement.

J'ai également écrit une animation en Python (travaux 2 et 3). Il faut pygletcourir. Vous pouvez voir l'animation en lançant:

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

(N'hésitez pas à télécharger le résumé et à inspecter le code avant d'exécuter.) Vous pouvez appuyer sur les touches + et - pour augmenter / diminuer le n en cours de visualisation.

Et enfin, pour ceux intéressés à explorer davantage cette séquence de numéros, voici une version lisible (utilisée pour générer les cas de test ci-dessus):

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

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

Explication

Règle 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

Cas de test

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

Python 2, 68 octets

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 détection de cycle pourrait être meilleure, mais l'étape itérative est agréable.

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

En représentant le tableau sous forme de nombre binaire k, la mise à jour peut être effectuée en prenant le XOR de kdécalage avec un gauche /2et un droit avec *2, puis en tronquant noctets comme %2**n.

Python 3 2, 134 121 118 octets

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)

Fondamentalement identique à ma réponse Pyth , mais quelque peu adapté en raison du manque de certaines fonctions intégrées dans Python.

Version non-golfée:

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 octets

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

Utilise la fonction "cumulative fixed-point" pour effectuer une itération jusque juste avant qu'une configuration ne se reproduise, et renvoie toutes les configurations intermédiaires sous forme de liste de listes. Cela fonctionne parce que les règles sont déterministes et que la configuration de la génération suivante est fonction de la configuration actuelle. Cela signifie qu'une fois la même configuration réapparue, les automates ont terminé un cycle.

Après avoir atteint cela (la dernière itération du cycle), il appelle la fonction next-gen une dernière fois sur le dernier élément de la liste "historique" pour obtenir la configuration suivante (qui est la configuration de départ d'un cycle), et trouve son index dans l'historique. Maintenant, la période est simplement la longueur (1 + indice de fin de cycle) moins l'indice de début de cycle.

En pseudocode pythonique:

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

La suite de tests prend trop de temps à tuer par le serveur. Vous devez donc utiliser le programme standard et le tester un par un, ou installer Pyth (si ce n’est pas déjà le cas) et utiliser un script pour le tester.

Jelly, 19 18 17 octets

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

Ce code calcule les premiers 2 ⁿ états, il est donc pas particulièrement rapide ou efficace de la mémoire ...

Essayez-le en ligne! ou vérifiez les 16 premiers cas de test .

Version alternative, 13 octets (non concurrente)

Les versions de Jelly postérieures à ce défi comportent une détection de boucle intégrée, ce qui permet une solution à la fois plus courte et plus efficace.

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

Cela gère facilement le dernier cas de test. Essayez-le en ligne!

Comment ça fonctionne

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

Notez que le lien d'assistance est appliqué à 2 ⁿ lors de la première itération, ce qui ne code pas un état valide. Cependant, ((2 ⁿ ÷ 2) ^ (2 ⁿ × 2))% 2 ⁿ = (2 ^{n - 1} + 2 ^{n + 1} )% 2 ⁿ = 2 ^{n - 1} , qui est l'un des états de départ possibles.

Puisque nous bouclons 2 ⁿ + 1 fois, nous sommes assurés de rencontrer un état deux fois, ce qui rend la détection de boucle réussie.

CJam, 41 34 31 27 25 octets

Merci à Dennis d'avoir économisé 3 octets. Emprunter une idée de sa réponse sur Jelly en a sauvé 4 autres.

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

Testez-le ici.

Explication

Je représente le fil simplement comme un entier (dont les bits indiquent les positions des électrons) au lieu d'utiliser une liste de bits. L'état est mis à jour via des calculs au niveau des bits assez simples.

Pour trouver la période, nous collectons tous les résultats intermédiaires sur la pile, exécutons la simulation pour 2 ^n-1 +1 étapes, puis déterminons la période comme le nombre d'éléments depuis la dernière occurrence de l'état final (plus 1).

Voici une ventilation du code:

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

Tester

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 octets

x!pdonne l’élément à l’indice p si dans les bornes, sinon 0. ncalcule l’étape suivante. g idonne le ith pas. c xdonne la période, si on commence par x. fenveloppe tout ensemble.

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]

(Remarque: posté à partir du téléphone qui a l'interprète câlins, qui n'est pas complet, peut avoir des fautes de frappe.)

MATL , 38 37 36 35 octets

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

Cela utilise une boucle qui continue à calculer les nouveaux états jusqu'à ce que le nouvel état soit égal à l'un des précédents. Chaque état est un vecteur de zéros et de uns. Ces vecteurs sont stockés sous forme de lignes d'un tableau 2D en croissance.

Le calcul de chaque nouvel état est effectué en convertissant l'état actuel en convolution avec la séquence [1,0,1], en ne conservant que la partie centrale et en définissant 0toute entrée qui ne l'est pas 1.

EDIT (13 mai 2016) Le code dans le lien suivant a été légèrement modifié conformément aux modifications introduites dans la langue après la rédaction de cette réponse

Essayez-le en ligne!

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 octets

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

Élargi et ungolfé un peu

-> $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 peu d'explication:

• [op]réduit la liste en utilisant op. Par exemple [+] @list, la somme@list
• Rest une méta-opération qui inverse les arguments donnés à un op. Par exemple, vous 1 R- 3obtiendrez 2.

C ++, 211 octets

Golfé

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

Avec des espaces ajoutés pour la lisibilité

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

Bonne pratique pour les bitset C ++; et une excellente éducation sur l'algorithme de détection de cycle de Brent (utilisé par @orlp)

Pyth, 95 octets

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

Vous pouvez l'essayer ici .

Pyth, 29 octets

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

• Essayez-le en ligne!
• Suite de tests

Utilise l'algorithme a(n+1) = ((a(n) << 1)^(a(n) >> 1)) % (2 ** N).

Ruby, 72 octets

Fonction anonyme.

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