A idéia aqui é produzir um padrão quase repetitivo. Ou seja, a sequência que está sendo construída muda no último momento para evitar uma repetição de alguma subsequência. As subseqüências do tipo AA e ABA devem ser evitadas (onde B não é maior que A).

Exemplos:

Vou seguir em frente e começar listando todos os pequenos exemplos para tornar minha descrição mais clara. Vamos começar com 0.

Válido: 0

Inválido: 00 (padrão AA)
Válido: 01

Inválido: 010 (padrão ABA)
Inválido: 011 (padrão AA)
Válido: 012

Válido: 0120
Inválido: 0121 (padrão ABA)
Inválido: 0122 (padrão AA)

Inválido: 01200 (padrão AA)
Inválido: 01201 (padrão ABA; 01-2-01)
Inválido: 01202 (padrão ABA)
Válido: 01203

Agora, acredito firmemente que a 4nunca é necessária, embora eu não tenha uma prova, porque encontrei facilmente sequências de centenas de caracteres que apenas usam 0123. (Provavelmente, está intimamente relacionado à forma como são necessários apenas três caracteres para ter seqüências infinitas que não possuem nenhum padrão AA. Há uma página da Wikipedia sobre isso.)

Entrada / Saída

A entrada é um número inteiro único, positivo e diferente de zero n. Você pode assumir isso n <= 1000.

Saída é uma nsequência de caracteres sem subseqüências que correspondem ao padrão proibido (AA ou ABA).

Amostras de entradas e saídas

>>> 1
0 0

>>> 2
01

>>> 3
012

>>> 4
0120

>>> 5
01203

>>> 50
01203102130123103201302103120132102301203102132012

Regras

• Somente os caracteres 0123são permitidos.
• B não é mais do que A. Isto é para evitar a situação em que 012345tem de ser seguido por 6porque 0123451tem este: 1-2345-1. Em outras palavras, a sequência seria trivial e desinteressante.
• npode ser introduzido através de qualquer método desejado, exceto codificação.
• A saída pode ser uma lista ou uma string, dependendo do que for mais fácil.
• Sem força bruta ; o tempo de execução deve ser da ordem de minutos, no máximo uma hora em uma máquina muito lenta, por n=1000. (Pretende-se desqualificar soluções que apenas circulam através de npermutações de todo o comprimento {0,1,2,3}, para que truques e truques semelhantes sejam proibidos.)
• As brechas padrão não são permitidas, como de costume.
• A pontuação está em bytes. Isso é código-golfe , então a entrada mais curta vence (provavelmente - veja o bônus).
• Bônus: escolha o dígito mais baixo permitido em cada etapa. Se 1e 3são possíveis opções para o próximo dígito na sequência, escolha 1. Subtraia 5 bytes da sua pontuação. No entanto, tome nota da nota abaixo.

Nota!

Os becos sem saída são possíveis. Seu programa ou função deve evitá-los. Aqui está um exemplo:

Stump: 01203102130123103201302103120132102301203102132012302103120130231032012302132031023012032102312013021031230132031021301203210230132031021301203210230310320123102301320310330
Stump: 01203102130123103201302103120132102301203102132012302103120130231032012302132031023012032102312013021031230132031021301203210230132031021301203210230310320123102301320310330
Stump: 0120310213012310320130210312013210230120310213201230210312013023103201230213203102301203210231201302103123013203102130120321023013203102130120321023013203103303103103103102301320310330
Stump: 01203102130123103201302103120132102301203102132012302103120130231032012302132031023012032102312013021031230132031021301203210230132031021301203103103103102301320310330

Cada uma dessas seqüências não pode ser estendida mais (sem usar a 4). Mas observe também que há uma diferença crucial entre os dois primeiros e os dois segundos. Substituirei a subsequência inicial compartilhada por uma Xpara tornar isso mais claro.

Coto: X2130120
Coto: X2130123
Coto: X320
Coto: X321301203102130

Os últimos dois dígitos de Xsão 10, portanto, as únicas opções possíveis para o próximo dígito são 2e 3. A escolha 2leva a uma situação em que a sequência deve terminar. O algoritmo ganancioso não funcionará aqui. (Não sem retroceder, pelo menos.)

Retina , 86 bytes - 5 = 81

$
_
(r`^(?<-2>.)+_((.)+)\b$
$1!
\b$
0
3#
#
0#
1
1#
2
2#
3
)r`\1(?<-2>.)*((.)+)$
$0#
!
<empty>

Onde <empty>representa uma linha de fuga vazia. Você pode executar o código acima a partir de um único arquivo com o -ssinalizador

A entrada deve ser dada em unário , por exemplo 111111. Ainda não testei a saída na ordem de milhares - duas das expressões regulares podem ficar um pouco lentas depois de um tempo - mas ela pode lidar facilmente com algumas centenas em poucos segundos.

Explicação

Esta é uma solução simples de retorno.

1. Anexar a 0.
2. Enquanto a sequência atual for inválida, remova todos os 3s finais e aumente o último não 3.
3. Repita até que tenhamos uma sequência válida do comprimento desejado.

Esse retorno é implementado por um loop de substituições de regex que é interrompido quando a sequência permanece inalterada por uma iteração.

$
_

Isso anexa _a à entrada, que é usada para separar a entrada unária da sequência que estamos construindo.

(r`^(?<-2>.)+_((.)+)\b$
$1!

Esta é a primeira substituição no loop (indicada pelo líder (). O regex corresponde se a) houver um caractere de palavra (ou seja, um dígito) no final da string (o que significa que a string é válida - veremos abaixo que sequências inválidas são marcadas com um final #) eb) existem pelo menos tantos caracteres na sequência quanto na entrada (isso é verificado usando grupos de balanceamento ). Se for esse o caso, removemos a entrada e anexamos a !. Isso !serve para fazer com que todas as expressões regulares no loop falhem, de forma que elas terminem.

\b$
0

Se houver um caractere de palavra no final (por exemplo, a sequência é válida e o loop não foi encerrado pela etapa anterior), acrescente a 0.

3#
#

Se (em vez disso) a sequência tiver sido marcada como inválida e encerrada 3, nós a removeremos 3(mas deixaremos a sequência como inválida, porque não há continuação possível para o prefixo atual ... para que o próximo caractere precise ser retornado também).

0#
1
1#
2
2#
3

Se a sequência estiver marcada como inválida e qualquer dígito que não 3esteja no final, incrementamos o dígito e removemos o marcador.

)r`\1(?<-2>.)*((.)+)$
$0#

A última substituição no loop (como indicado pelo )). Ele verifica se a sequência termina ABA(onde Bnão é maior que, Amas potencialmente vazio). Os comprimentos relativos de Ae Bsão novamente verificados usando grupos de balanceamento, e a repetição de Aé verificada com uma referência simples.

Se esse regex corresponder, marcaremos a sequência inválida anexando #.

!
<empty>

Depois que o loop termina, tudo o que precisamos fazer é remover o !e, em seguida, ficar com a saída desejada.

Python 2, 175 - 5 = 170 bytes

n=input();s='';u=j=-1
while n>len(s):
 while u>2:u=int(s[0]);s=s[1:]
 u+=1;t=`u`+s;m=c=0
 while t[c:]*0**m:c+=1;i=t[c:].find(t[:c]);m=j<i<=c
 if c>=len(t):s=t;u=j
print s[::j]

Este é o algoritmo ganancioso com retorno. Eu gostaria que fosse mais curto. Espero que esteja correto (veja abaixo).

Constrói a string um dígito de cada vez. Dada uma sequência de ddígitos que já encontrou, ele tenta anexar a 0como o (d+1)dígito st. Se isso não funcionar, ele tenta a 1, então a 2, então a 3. Se nada disso funcionar, ele retornará ao ddécimo dígito e o incrementará (se for menor que 3) ou o removerá (se for igual a 3, caso em que incrementa o anterior, etc.).

A verificação de validade é a linha contida .findnela. Caso alguém decida ler meu código, devo dizer que este programa está realmente armazenando a string para trás, o que significa que está adicionando dígitos à frente . Portanto, a verificação envolve procurar lugares em que os primeiros c dígitos apareçam novamente mais tarde na string (em qualquer lugar após os primeiros cdígitos) e, se houver algum desses lugares, se o comprimento intermediário é no máximo c.

(É claro que ele reverte a sequência antes de imprimir.)

Também poderia ser facilmente mais rápido; Originalmente, tive que sair vários loops cedo para obter eficiência, mas isso custou bytes preciosos. Ele ainda funciona bem no intervalo de n=1000, no entanto.

De qualquer forma, o programa parece exibir uma preferência pelos dígitos menores, mas não é uma preferência muito forte. Por exemplo, executá-lo com n=2000me deu uma string com 523zeros, 502uns, 497dois e 478três, terminando em 30210312013021. Portanto, se alguém mais estiver trabalhando em um algoritmo ganancioso, talvez possa confirmar esse resultado. Ou com n=1000eu consegui [263, 251, 248, 238]as contagens por dígito.

Finalmente, eu mencionaria que essas contagens sugerem simetria, quase (embora não exatamente), como se tivéssemos começado com uma distribuição uniforme e depois convertido alguns dos 3's para 0' s e alguns dos 2's para 1' s. Mas, obviamente, isso poderia ser apenas coincidência. Eu não faço ideia!

Haskell, 115 (120 bytes - 5 bônus)

x?_|or[t x==t(drop i x)|i<-[1..length x],t<-[take$div(i+1)2]]=[]
x?0=[x]
x?n=(?(n-1)).(:x)=<<"0123"
f=reverse.head.([]?)

Corra online em Ideone

Exemplo de execução:

*Main> f 40
"0120310213012310320130210312013210230120"