Trójskładnikowe słowa trójskładnikowe bez słów

9

Ciąg nie zawiera kwadratów, jeśli nie zawiera podłańcuchów dwa razy z rzędu.

Możliwe jest dowolne długie słowo bez kwadratów za pomocą 3-literowego alfabetu.

Napisz program, który akceptuje dodatnią liczbę całkowitą n ze standardowego wejścia i drukuje każdą kwadratem długości słowa n, przy użyciu znaków A, Bi C.

Najkrótszy kod wygrywa.

code-golf string pudełko kartonowe
źródło

Odpowiedzi:

4

GolfScript ( 40 27 znaków)

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

Podejście to jest trywialnym wariantem jednego z tych opisanych w Wikipedii: długości 1s w sekwencji Thue-Morse.

Jeśli dodatkowy znak nowej linii jest niedopuszczalny, można go usunąć kosztem jednej postaci, zastępując nją ''.

Peter Taylor
źródło
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))

Wykorzystuje metodę sekwencji Thue – Morse z wikipedii.

Wydajna wersja (100 znaków):

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
źródło
1
exec"x+=[1-y for y in x];"*noszczędza 6 znaków kosztem wydajności - ale hej, to jest golf!
gnibbler
4

Python, 129 125 119

Przy użyciu metody Johna Leecha opisanej na połączonej stronie wiki.

s='A'
n=input()
while len(s)<=n:s=''.join('ABCBCACABBCAABCCABBCACABABCBCACABBCAABC'[ord(t)%5::3]for t in s)
print s[:n]
pudełko kartonowe
źródło
1
Możesz uratować niektóre postacie za pomocą:'ABCBCACABBCAABCCABBCACABABCBCACABBCAABC'[ord(t)%5::3]
grc 31.01.13
while s[:n]==s:oszczędza jeszcze 1
gnibbler
3

Python2 - 112 znaków

To jest dość nieefektywne. Generuje o wiele znacznie dłuższy ciąg znaków niż jest to wymagane, a następnie go obcina. Na przykład wartość pośrednia sdla n=7wynosi 62748517 (13 n ) znaków

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

Mathematica 159 140 134

Edycja : Całkowite przepisanie przy użyciu rekurencji ( NestWhile). Znacznie szybciej i bez marnowania wysiłku.

Kod

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

Stosowanie

Wygenerowanie trójskładnikowego wolnego słowa z milionem znaków zajmuje około 1/40 sekundy.

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

wyniki

Weryfikacja

f sprawdzi, czy łańcuch nie zawiera kwadratów.

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

Sprawdzanie powyższych wyników i jednego przypadku, w którym pojawia się ciąg „CC”.

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

Prawda
Prawda
Prawda
Fałsz

DavidC
źródło