# Arbitrary-Length Ternary Squarefree Words

A string is squarefree if it contains no substring twice in a row.

It is possible to have an arbitrarily long squarefree word using a 3-letter alphabet.

Write a program which accepts a positive integer n from stdin and prints any squarefree word of length n, using characters A, B and C.

Shortest code wins.

## 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))


It uses the Thue–Morse sequence method from wikipedia.

Efficient version (100 chars):

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))

• exec"x+=[1-y for y in x];"*n saves 6 chars at the expense of efficiency - but hey this is golf! Feb 1, 2013 at 6:28

## GolfScript (40 27 chars)

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


The approach is a trivial variant on one of those described in Wikipedia: the run-lengths of 1s in the Thue-Morse sequence.

If the extra trailing newline is unacceptable it can be removed at the cost of one character by replacing n with ''.

## Python, 129125 119

Using John Leech's method as described on the linked wiki page.

s='A'
n=input()
while len(s)<=n:s=''.join('ABCBCACABBCAABCCABBCACABABCBCACABBCAABC'[ord(t)%5::3]for t in s)
print s[:n]

• You could save some characters with: 'ABCBCACABBCAABCCABBCACABABCBCACABBCAABC'[ord(t)%5::3]
– grc
Jan 31, 2013 at 22:34
• while s[:n]==s: saves 1 more Feb 1, 2013 at 2:21

## Python2 - 112 chars

This is pretty inefficient. It generates a much much much longer string than required and then truncates it. For example the intermediate s for n=7 is 62748517 (13n) characters long

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


# Mathematica 159 140 134

Edit: A complete rewrite, using recursion (NestWhile). Much faster and no wasted effort.

Code

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


Usage

It takes approximately 1/40 sec to generate a ternary square free word with one million characters.

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


Verifying

f will test whether a string is square free.

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


Checking the above outputs and one case in which the string "CC" appears.

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


True
True
True
False