9
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
6
\$\begingroup\$

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))
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ exec"x+=[1-y for y in x];"*n saves 6 chars at the expense of efficiency - but hey this is golf! \$\endgroup\$ – gnibbler Feb 1 '13 at 6:28
4
\$\begingroup\$

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]
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ You could save some characters with: 'ABCBCACABBCAABCCABBCACABABCBCACABBCAABC'[ord(t)%5::3] \$\endgroup\$ – grc Jan 31 '13 at 22:34
  • \$\begingroup\$ while s[:n]==s: saves 1 more \$\endgroup\$ – gnibbler Feb 1 '13 at 2:21
3
\$\begingroup\$

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]
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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];]

results

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

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.