Mots ternaires sans carré de longueur arbitraire

9

Une chaîne est sans carré si elle ne contient pas de sous-chaîne deux fois de suite.

Il est possible d'avoir un mot sans carré arbitrairement long en utilisant un alphabet à 3 lettres.

Ecrire un programme qui accepte un entier positif n de stdin et imprime un mot de longueur n quadratfrei, en utilisant des caractères A, Bet C.

Le code le plus court gagne.

code-golf string boîte en carton
la source

Réponses:

4

GolfScript ( 40 27 caractères)

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

L'approche est une variante triviale de l'une de celles décrites dans Wikipédia: les longueurs d'exécution de 1 dans la séquence Thue-Morse.

Si la nouvelle ligne supplémentaire n'est pas acceptable, elle peut être supprimée au prix d'un caractère en la remplaçant npar ''.

Peter Taylor
la source
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))

Il utilise la méthode de séquence Thue – Morse de wikipedia.

Version efficace (100 caractères):

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
la source
1
exec"x+=[1-y for y in x];"*nenregistre 6 caractères au détriment de l'efficacité - mais bon, c'est du golf!
gnibbler
4

Python, 129 125 119

En utilisant la méthode de John Leech comme décrit sur la page wiki liée.

s='A'
n=input()
while len(s)<=n:s=''.join('ABCBCACABBCAABCCABBCACABABCBCACABBCAABC'[ord(t)%5::3]for t in s)
print s[:n]
boîte en carton
la source
1
Vous pouvez enregistrer certains personnages avec:'ABCBCACABBCAABCCABBCACABABCBCACABBCAABC'[ord(t)%5::3]
grc
while s[:n]==s:sauve 1 de plus
gnibbler
3

Python2 - 112 caractères

C'est assez inefficace. Il génère une chaîne beaucoup plus longue que nécessaire, puis la tronque. Par exemple, l'intermédiaire spour n=762748517 (13 n ) caractères

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

Mathematica 159 140 134

Edit : Une réécriture complète, en utilisant récursion ( NestWhile). Beaucoup plus rapide et sans effort inutile.

Code

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

Usage

Il faut environ 1/40 sec pour générer un mot libre carré ternaire avec un million de caractères.

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

résultats

Vérification

f testera si une chaîne est sans carré.

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

Vérification des sorties ci-dessus et d'un cas dans lequel la chaîne "CC" apparaît.

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

Vrai
Vrai
Vrai
Faux

DavidC
la source