Произвольная длина троичных слов без квадратов

9

Строка не содержит квадратов, если она не содержит подстроки дважды подряд.

Можно использовать произвольно длинное слово без квадратов, используя трехбуквенный алфавит.

Напишите программу, которая принимает положительное целое число n из стандартного ввода и печатает любое слово без квадратов длины n, используя символы A, Bи C.

Самый короткий код выигрывает.

code-golf string картонная коробка
источник

Ответы:

4

GolfScript ( 40 27 символов)

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

Подход представляет собой тривиальный вариант одного из описанных в Википедии: длины серий 1 с в последовательности Туэ-Морса.

Если дополнительный завершающий символ новой строки недопустим, его можно удалить за счет одного символа, заменив nна ''.

Питер Тейлор
источник
6

Питон, 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))

Он использует метод последовательности Туэ – Морса из Википедии.

Эффективная версия (100 символов):

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
источник
1
exec"x+=[1-y for y in x];"*nэкономит 6 символов за счет эффективности - но эй, это гольф!
Гнибблер
4

Питон, 129 125 119

Использование метода Джона Лича, как описано на связанной странице вики.

s='A'
n=input()
while len(s)<=n:s=''.join('ABCBCACABBCAABCCABBCACABABCBCACABBCAABC'[ord(t)%5::3]for t in s)
print s[:n]
картонная коробка
источник
1
Вы можете сохранить некоторые символы с помощью:'ABCBCACABBCAABCCABBCACABABCBCACABBCAABC'[ord(t)%5::3]
grc
while s[:n]==s:сохраняет еще 1
gnibbler
3

Python2 - 112 символов

Это довольно неэффективно. Он генерирует намного более длинную строку, чем требуется, а затем усекает ее. Например, промежуточное значение sдля n=7длиной 62748517 (13 n ) символов

s='A'
n=input()
exec"s=''.join('ABCBCACABBCAABCCABBCACABABCBCACABBCAABC'[ord(t)%5::3]for t in s);"*n
print s[:n]
gnibbler
источник
2

Mathematica 159 140 134

Редактировать : полное переписывание с использованием рекурсии ( NestWhile). Намного быстрее и без усилий.

Код

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

Применение

Требуется приблизительно 1/40 секунды, чтобы сгенерировать слово без троичного квадрата с одним миллионом символов.

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

Результаты

Проверка

f проверит, является ли строка свободной от квадратов.

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

Проверка вышеприведенных выходных данных и один случай, в котором появляется строка «CC».

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

Истинно
верно
верно
ложно

DavidC
источник