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.
Odpowiedzi:
~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ą ''.
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))
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]
'ABCBCACABBCAABCCABBCACABABCBCACABBCAABC'[ord(t)%5::3]
while s[:n]==s:oszczędza jeszcze 1
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]
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];]
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
exec"x+=[1-y for y in x];"*noszczędza 6 znaków kosztem wydajności - ale hej, to jest golf!