Kata-Kata Ternary Squarefree Tanpa Batas Sewenang-wenang

9

String bebas persegi jika tidak mengandung substring dua kali berturut-turut.

Dimungkinkan untuk memiliki kata bebas persegi panjang sembarang menggunakan alfabet 3 huruf.

Tulis sebuah program yang menerima bilangan bulat positif n dari stdin dan mencetak kata panjang bebas persegi n, menggunakan karakter A, Bdan C.

Kode terpendek menang.

code-golf string kotak kardus
sumber

Jawaban:

4

GolfScript ( 40 27 karakter)

~1,{.{!}%+}2$*1,/<{,65+}%n+

Pendekatan ini merupakan varian sepele pada salah satu yang dijelaskan dalam Wikipedia: run-lengths 1s dalam urutan Thue-Morse.

Jika ekstra baris baru tidak dapat diterima dapat dihapus pada biaya satu karakter dengan mengganti ndengan ''.

Peter Taylor
sumber
6

Python, 94

n=input()
x=[0]
exec"x+=[1-y for y in x];"*n
print''.join('ABC'[x[i+1]-x[i]]for i in range(n))

Ia menggunakan metode urutan Thue-Morse dari wikipedia.

Versi efisien (100 karakter):

n=input()
x=[0]
while x==x[:n]:x+=[1-y for y in x]
print''.join('ABC'[x[i+1]-x[i]]for i in range(n))
grc
sumber
1
exec"x+=[1-y for y in x];"*nmenghemat 6 karakter dengan mengorbankan efisiensi - tapi hei ini golf!
gnibbler
4

Python, 129 125 119

Menggunakan metode John Leech seperti yang dijelaskan pada halaman wiki yang tertaut.

s='A'
n=input()
while len(s)<=n:s=''.join('ABCBCACABBCAABCCABBCACABABCBCACABBCAABC'[ord(t)%5::3]for t in s)
print s[:n]
kotak kardus
sumber
1
Anda dapat menyimpan beberapa karakter dengan:'ABCBCACABBCAABCCABBCACABABCBCACABBCAABC'[ord(t)%5::3]
grc
while s[:n]==s:hemat 1 lagi
gnibbler
3

Python2 - 112 karakter

Ini sangat tidak efisien. Ini menghasilkan string yang jauh lebih lama dari yang dibutuhkan dan kemudian memotongnya. Misalnya perantara suntuk n=762748517 (13 n ) karakter

s='A'
n=input()
exec"s=''.join('ABCBCACABBCAABCCABBCACABABCBCACABBCAABC'[ord(t)%5::3]for t in s);"*n
print s[:n]
gnibbler
sumber
2

Mathematica 159 140 134

Sunting : Menulis ulang lengkap, menggunakan rekursi ( NestWhile). Jauh lebih cepat dan tidak ada usaha yang sia-sia.

Kode

g@n_:=StringTake[NestWhile[#~StringReplace~{"A"-> "ABCBACBCABCBA","B"-> "BCACBACABCACB",
     "C"->"CABACBABCABAC"}&,"ABC",StringLength[#]<n&],n]

Pemakaian

Dibutuhkan sekitar 1/40 detik untuk menghasilkan kata bebas terner persegi dengan satu juta karakter.

g[10]
g[53]
g[506]
AbsoluteTiming[g[10^6];]

hasil

Memverifikasi

f akan menguji apakah sebuah string bebas persegi.

f[s_]:=StringFreeQ[s, x__~~x__]

Memeriksa output di atas dan satu case di mana string "CC" muncul.

f@Out[336]
f@Out[337]
f@Out[338]
f["ABCBACBCABCBABCACBACCABCACBCABACBABCABACBCACBACABCACBA"]

Benar
Benar
Benar
Salah

DavidC
sumber