Arbitrary-Length Ternary Squarefree Words

Question

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.

Answer 1

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 ''.

Answer 2

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

Answer 3

Python, 129 125 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]

Answer 4

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 (13ⁿ) characters long

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

Answer 5

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