Ternäre quadratische Wörter beliebiger Länge

9

Eine Zeichenfolge ist quadratfrei, wenn sie zweimal hintereinander keine Teilzeichenfolge enthält.

Es ist möglich, ein beliebig langes quadratfreies Wort mit einem 3-Buchstaben-Alphabet zu haben.

Ein Programm schreiben , das eine positive ganze Zahl n von stdin nimmt und druckt jedes quadrat Wort der Länge n, unter Verwendung von Zeichen A, Bund C.

Der kürzeste Code gewinnt.

code-golf string Pappschachtel
quelle

Antworten:

4

GolfScript ( 40 27 Zeichen)

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

Der Ansatz ist eine triviale Variante einer der in Wikipedia beschriebenen: die Lauflängen von 1s in der Thue-Morse-Sequenz.

Wenn die zusätzliche nachfolgende Newline nicht akzeptabel ist, kann sie auf Kosten eines Zeichens durch Ersetzen ndurch entfernt werden ''.

Peter Taylor
quelle
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))

Es verwendet die Thue-Morse-Sequenzmethode aus Wikipedia.

Effiziente Version (100 Zeichen):

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
quelle
1
exec"x+=[1-y for y in x];"*nspart 6 Zeichen auf Kosten der Effizienz - aber hey, das ist Golf!
Gnibbler
4

Python, 129 125 119

Verwenden Sie die Methode von John Leech, wie auf der verlinkten Wiki-Seite beschrieben.

s='A'
n=input()
while len(s)<=n:s=''.join('ABCBCACABBCAABCCABBCACABABCBCACABBCAABC'[ord(t)%5::3]for t in s)
print s[:n]
Pappschachtel
quelle
1
Sie könnten einige Zeichen speichern mit:'ABCBCACABBCAABCCABBCACABABCBCACABBCAABC'[ord(t)%5::3]
grc
while s[:n]==s:spart 1 mehr
Gnibbler
3

Python2 - 112 Zeichen

Das ist ziemlich ineffizient. Es generiert eine viel, viel längere Zeichenfolge als erforderlich und schneidet sie dann ab. Das Zwischenprodukt sfür n=7ist beispielsweise 62748517 (13 n ) Zeichen lang

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

Mathematica 159 140 134

Bearbeiten : Ein vollständiges Umschreiben mit Rekursion ( NestWhile). Viel schneller und ohne unnötigen Aufwand.

Code

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

Verwendungszweck

Es dauert ungefähr 1/40 Sek., Um ein ternäres quadratfreies Wort mit einer Million Zeichen zu erzeugen.

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

Ergebnisse

Überprüfen

f testet, ob eine Zeichenfolge quadratfrei ist.

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

Überprüfen Sie die obigen Ausgänge und einen Fall, in dem die Zeichenfolge "CC" angezeigt wird.

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

Richtig
Richtig
Richtig
Falsch

DavidC
quelle