Ternário de comprimento arbitrário Palavras sem quadratura

9

Uma cadeia de caracteres é quadrada se não contiver substring duas vezes seguidas.

É possível ter uma palavra arbitrariamente longa e sem quadrados usando um alfabeto de três letras.

Escreva um programa que aceite um número inteiro positivo n de stdin e imprima qualquer palavra livre de comprimento n, usando caracteres A, Be C.

O menor código vence.

code-golf string caixa de papelão
fonte

Respostas:

4

GolfScript ( 40 27 caracteres)

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

A abordagem é uma variante trivial de uma das descritas na Wikipedia: as durações de 1s na sequência Thue-Morse.

Se a nova linha extra à direita for inaceitável, ela poderá ser removida ao custo de um caractere, substituindo npor ''.

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

Ele usa o método de sequência Thue – Morse da wikipedia.

Versão 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
fonte
11
exec"x+=[1-y for y in x];"*neconomiza 6 caracteres em detrimento da eficiência - mas ei, isso é golfe!
Gnibbler
4

Python, 129 125 119

Usando o método de John Leech, conforme descrito na 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]
caixa de papelão
fonte
11
Você pode salvar alguns caracteres com:'ABCBCACABBCAABCCABBCACABABCBCACABBCAABC'[ord(t)%5::3]
grc 31/01
while s[:n]==s:salva mais 1
gnibbler
3

Python2 - 112 caracteres

Isso é bastante ineficiente. Ele gera uma string muito muito muito mais longa do que o necessário e a trunca. Por exemplo, o intermediário spara n=7tem 62748517 (13 n ) caracteres

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

Mathematica 159 140 134

Editar : Uma reescrita completa, usando recursão ( NestWhile). Muito mais rápido e sem esforço desperdiçado.

Código

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

Uso

Demora aproximadamente 1/40 s para gerar uma palavra livre quadrada ternária com um milhão de caracteres.

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

resultados

Verificando

f testará se uma string é quadrada livre.

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

Verificando as saídas acima e um caso em que a string "CC" aparece.

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

Verdadeiro
Verdadeiro
Verdadeiro
Falso

DavidC
fonte