Palabras arbitrarias ternarias cuadradas libres

9

Una cadena es cuadrada si no contiene ninguna subcadena dos veces seguidas.

Es posible tener una palabra arbitrariamente larga sin cuadrados utilizando un alfabeto de 3 letras.

Escriba un programa que acepte un entero positivo n de stdin e imprima cualquier palabra cuadrada de longitud n, usando caracteres A, By C.

El código más corto gana.

code-golf string caja de cartón
fuente

Respuestas:

4

GolfScript ( 40 27 caracteres)

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

El enfoque es una variante trivial de una de las descritas en Wikipedia: las longitudes de ejecución de 1s en la secuencia Thue-Morse.

Si el salto de línea final extra es inaceptable que se puede quitar a costa de un carácter mediante la sustitución ncon ''.

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

Utiliza el método de secuencia Thue – Morse de wikipedia.

Versión eficiente (100 caracteres):

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
fuente
1
exec"x+=[1-y for y in x];"*nahorra 6 caracteres a expensas de la eficiencia, pero bueno, ¡esto es golf!
gnibbler 01 de
4

Python, 129 125 119

Usando el método de John Leech como se describe en la página wiki vinculada.

s='A'
n=input()
while len(s)<=n:s=''.join('ABCBCACABBCAABCCABBCACABABCBCACABBCAABC'[ord(t)%5::3]for t in s)
print s[:n]
caja de cartón
fuente
1
Puede guardar algunos caracteres con:'ABCBCACABBCAABCCABBCACABABCBCACABBCAABC'[ord(t)%5::3]
grc
while s[:n]==s:ahorra 1 más
gnibbler 01 de
3

Python2 - 112 caracteres

Esto es bastante ineficiente. Genera una cadena mucho más larga que la requerida y luego la trunca. Por ejemplo, el intermedio spara n=7tiene 62748517 (13 n ) caracteres de longitud

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

Mathematica 159 140 134

Editar : una reescritura completa, utilizando recursión ( NestWhile). Mucho más rápido y sin esfuerzo desperdiciado.

Código

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

Uso

Se tarda aproximadamente 1/40 segundos en generar una palabra libre cuadrada ternaria con un millón de caracteres.

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

resultados

Verificando

f probará si una cadena está libre de cuadrados.

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

Verificando las salidas anteriores y un caso en el que aparece la cadena "CC".

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

Verdadero
Verdadero
Verdadero
Falso

DavidC
fuente