Bayangkan sebuah "kawat" yang memiliki nspasi. Bayangkan lebih lanjut bahwa ada "elektron" di kawat itu. Elektron ini hanya hidup untuk satu unit waktu. Setiap ruang dalam kawat yang berdekatan dengan tepat satu elektron menjadi elektron. Dalam terminologi Game of Life, ini B1/S.

Misalnya, ini adalah kawat dengan panjang 10, dengan periode 62.

Aturan

• Input,, nadalah bilangan bulat tunggal, positif.
• Output harus berupa bilangan bulat tunggal yang menunjukkan periode panjang kawat n.
• Keadaan awal adalah elektron tunggal di salah satu ujung kawat.
• Periode tidak harus termasuk kondisi awal. Beberapa panjang tidak pernah kembali ke keadaan awal, tetapi semuanya bersifat periodik.
• Kawat statis (yaitu, satu tanpa elektron) memiliki periode 1.
• Kondisi batas tidak periodik. Artinya, kawat tidak toroidal dengan cara apa pun.

Uji kasus

Terima kasih khusus kepada orlp untuk membuat daftar ini. (Saya telah memverifikasi hingga 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

Anda dapat melihat kasus uji untuk n = 2 hingga 21 di sini dengan simulator Game-of-Life-esque saya: Variasi Kehidupan .

EDIT: urutan di sini telah diterbitkan sebagai A268754 !

Python 2, 148 142 87 byte

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

Menggunakan algoritme deteksi siklus Brent , dan karenanya benar-benar berjalan cepat.

Saya juga menulis animasi dalam Python (keduanya 2 & 3 bekerja). Perlu pygletdijalankan. Anda dapat melihat animasi dengan menjalankan:

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

(Jangan ragu untuk mengunduh inti dan memeriksa kodenya sebelum menjalankan.) Anda dapat menekan tombol + dan - untuk menambah / mengurangi n yang sedang divisualisasikan.

Dan akhirnya, bagi mereka yang tertarik untuk mengeksplorasi urutan nomor ini lebih lanjut, ini adalah versi yang dapat dibaca (ini digunakan untuk menghasilkan kasus uji di atas):

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

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

Penjelasan

Aturan 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

Uji kasus

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

Python 2, 68 byte

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

Deteksi siklus bisa lebih baik, tetapi langkah berulang bagus.

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

Dengan merepresentasikan array sebagai angka biner k, pembaruan dapat dilakukan dengan mengambil XOR yang kbergeser satu kiri dengan /2dan yang kanan *2, kemudian memotong menjadi nbyte sebagai %2**n.

Python 3 2, 134 121 118 byte

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)

Pada dasarnya sama dengan jawaban Pyth saya , tetapi mengadaptasinya agak karena kurangnya fungsi built-in tertentu di Python.

Versi tidak disatukan:

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 byte

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

Menggunakan fungsi "titik tetap kumulatif" untuk beralih hingga sesaat sebelum konfigurasi berulang, dan mengembalikan semua konfigurasi menengah sebagai daftar daftar. Ini berfungsi karena aturan bersifat deterministik dan konfigurasi generasi berikutnya adalah fungsi dari konfigurasi saat ini. Ini berarti bahwa sekali konfigurasi yang sama muncul lagi automata telah menyelesaikan satu siklus.

Setelah mencapai itu (iterasi terakhir dari siklus), ia memanggil fungsi next-gen untuk terakhir kalinya pada elemen terakhir dari daftar "history", untuk mendapatkan konfigurasi berikutnya (yang merupakan konfigurasi awal dari sebuah siklus), dan temukan indeksnya dalam sejarah. Sekarang periode hanyalah panjang (1 + indeks akhir siklus) dikurangi indeks dimulainya siklus.

Dalam pseudocode pythonic:

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

Test suite membutuhkan terlalu banyak waktu sehingga server akan membunuhnya, jadi Anda harus menggunakan program reguler dan mengujinya satu per satu, atau menginstal Pyth (jika belum) dan menggunakan skrip untuk mengujinya.

Jelly, 19 18 17 byte

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

Kode ini menghitung 2 ⁿ status pertama, jadi tidak terlalu cepat atau memori efisien ...

Cobalah online! atau verifikasi 16 kasus uji pertama .

Versi alternatif, 13 byte (tidak bersaing)

Versi Jelly yang mengunggah tantangan ini memiliki deteksi loop bawaan, memungkinkan solusi yang lebih pendek dan lebih efisien.

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

Ini menangani test case terakhir dengan mudah. Cobalah online!

Bagaimana itu bekerja

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

Perhatikan bahwa tautan helper diterapkan pada 2 ⁿ pada iterasi pertama, yang tidak menyandikan status yang valid. Namun, ((2 ⁿ ÷ 2) ^ (2 ⁿ × 2))% 2 ⁿ = (2 ^{n - 1} + 2 ^{n + 1} )% 2 ⁿ = 2 ^{n - 1} , yang merupakan salah satu kondisi awal yang mungkin.

Karena kita mengulangi 2 ⁿ + 1 kali, kita dijamin akan menghadapi keadaan dua kali, membuat deteksi putaran berhasil.

CJam, 41 34 31 27 25 byte

Terima kasih kepada Dennis karena telah menghemat 3 byte. Meminjam ide dari jawaban Jeli menyimpan 4 lainnya.

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

Uji di sini.

Penjelasan

Saya mewakili kawat hanya sebagai bilangan bulat (yang bit menunjukkan posisi elektron) daripada menggunakan daftar bit yang sebenarnya. Status adalah pembaruan melalui perhitungan bitwise yang cukup sederhana.

Untuk menemukan periode, kami mengumpulkan semua hasil antara di tumpukan, menjalankan simulasi untuk langkah 2 ^n-1 +1, dan kemudian menentukan periode sebagai jumlah elemen sejak kemunculan terakhir dari keadaan akhir (ditambah 1).

Berikut ini rincian kode:

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

Uji

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 byte

x!pmemberikan elemen pada indeks p jika dalam batas, jika 0. nmenghitung langkah selanjutnya. g iberikan ilangkah th. c xmemberi titik, jika dimulai dengan x. fmembungkus semuanya.

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]

(Catatan: diposting dari ponsel yang memiliki penerjemah pelukan, yang tidak berfitur lengkap, jadi mungkin ada kesalahan ketik.)

MATL , 38 37 36 35 byte

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

Ini menggunakan loop yang terus menghitung status baru sampai status baru sama dengan yang sebelumnya. Setiap negara adalah vektor nol dan satu. Vektor ini disimpan sebagai baris array 2D yang berkembang.

Perhitungan masing-masing negara baru dilakukan dengan menggabungkan keadaan saat ini dengan urutan [1,0,1], hanya menjaga bagian tengah, dan pengaturan untuk 0setiap entri yang tidak 1.

EDIT (13 Mei 2016) Kode di tautan berikut telah sedikit dimodifikasi sesuai dengan perubahan yang diperkenalkan dalam bahasa setelah jawaban ini ditulis

Cobalah 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 byte

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

Mengembang dan sedikit berubah bentuk

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

Sedikit penjelasan:

• [op]mengurangi daftar menggunakan op. Misalnya [+] @listakan dijumlahkan@list
• Radalah meta-op yang membalik argumen yang diberikan pada op. Misalnya 1 R- 3akan menghasilkan 2.

C ++, 211 byte

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

Dengan spasi tambahan untuk keterbacaan

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

Praktik yang baik untuk bitet C ++; dan pembelajaran yang bagus tentang algoritma deteksi siklus Brent (seperti yang digunakan oleh @orlp)

Pyth, 95 byte

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

Anda dapat mencobanya di sini .

Pyth, 29 byte

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

• Cobalah online!
• Suite uji

Menggunakan algoritma a(n+1) = ((a(n) << 1)^(a(n) >> 1)) % (2 ** N).

Ruby, 72 byte

Fungsi anonim.

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