La idea aquí es producir un patrón casi repetitivo. Es decir, la secuencia que se está construyendo cambia en el último momento para evitar la repetición de alguna subsecuencia. Se deben evitar las subsecuencias del tipo AA y ABA (donde B no es más largo que A).

Ejemplos:

Seguiré adelante y comenzaré enumerando todos los pequeños ejemplos para aclarar mi descripción. Comencemos con 0.

Válido: 0

Inválido: 00 (patrón AA)
Válido: 01

Inválido: 010 (patrón ABA)
Inválido: 011 (patrón AA)
Válido: 012

Válido: 0120
Inválido: 0121 (patrón ABA)
Inválido: 0122 (patrón AA)

Inválido: 01200 (patrón AA)
Inválido: 01201 (patrón ABA; 01-2-01)
Inválido: 01202 (patrón ABA)
Válido: 01203

Ahora, creo firmemente que 4nunca se necesita a, aunque no tengo una prueba, porque he encontrado fácilmente secuencias de cientos de caracteres que solo se usan 0123. (Probablemente esté estrechamente relacionado con la forma en que solo se necesitan tres caracteres para tener cadenas infinitas que no tengan ningún patrón AA. Hay una página de Wikipedia sobre esto).

De entrada y salida

La entrada es un número entero positivo, distinto de cero n. Puedes suponer eso n <= 1000.

La salida es una nsecuencia de caracteres sin subsecuencias que coincidan con patrones prohibidos (AA o ABA).

Muestra de entradas y salidas

>>> 1
0 0

>>> 2
01

>>> 3
012

>>> 4
0120

>>> 5
01203

>>> 50
01203102130123103201302103120132102301203102132012

Reglas

• Solo 0123se permiten los personajes .
• B ya no es de A. Esto es para evitar la situación en la que 012345tiene que ser seguido por 6porque 0123451tiene esta: 1-2345-1. En otras palabras, la secuencia sería trivial y poco interesante.
• nse puede ingresar a través de cualquier método deseado, excepto la codificación fija.
• La salida puede ser una lista o una cadena, según cuál sea más fácil.
• Sin fuerza bruta ; el tiempo de ejecución debe ser del orden de minutos, como máximo una hora en una máquina realmente lenta, por n=1000. (Esto tiene la intención de descalificar soluciones que simplemente recorren todas las npermutaciones de todas las longitudes de {0,1,2,3}, para que no se permitan trucos y trucos similares).
• Las lagunas estándar no están permitidas, como de costumbre.
• La puntuación está en bytes. Este es el código de golf , por lo que gana la entrada más corta (probablemente, vea el bono).
• Bonificación: elija el dígito más bajo permitido en cada paso. Si 1y 3son posibles opciones para el siguiente dígito en la secuencia, seleccione 1. Resta 5 bytes de tu puntaje. Sin embargo, tome nota de la nota a continuación.

¡Nota!

Los callejones sin salida son posibles. Su programa o función debe evitarlos. Aquí hay un ejemplo:

Tocón: 01203102130123103201302103120132102301203102132012302103120130231032012302132031023012032102312013021031230132031021301203210230132031230220310320123102112032031023013203203103302201310320210230220310213201230210312013023103201230213203102301203210231201302103123013203102130120321023013203123022032031023013203202
Stump: 0120310213012310320130210312013210230120310213201230210312013023103201230213203102301203210231201302103123013203102130120321023013203123021032012310213012031023013203123021320123102130123
Tocón: 01203102130123103201302103120132102301203102132012302103120130231032012302132031023012032102312013021031230132031021301203210230132031230210320123102130120310230132032031023013203203102301320320310230132032031023013202
Stump: 012031021301231032013021031201321023012031021320123021031201302310320123021320310230120321023120130210312301320310213012032102301320312302103201231021301203102301320312302132012310321301203102130

Cada una de estas secuencias no puede extenderse más (sin usar a 4). Pero también tenga en cuenta que hay una diferencia crucial entre los dos primeros y los segundos dos. Reemplazaré la subsecuencia inicial compartida con una Xpara aclarar esto.

Tocón: X2130120
Tocón: X2130123
Tocón: X320
Tocón: X321301203102130

Los dos últimos dígitos de Xson 10, por lo que las únicas opciones posibles para el siguiente dígito son 2y 3. Elegir 2conduce a una situación en la que la secuencia debe terminar. El codicioso algoritmo no funcionará aquí. (No sin retroceder, de todos modos).

Retina , 86 bytes - 5 = 81

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

Donde <empty>representa una línea final vacía. Puede ejecutar el código anterior desde un solo archivo con la -sbandera.

La entrada debe darse en unario , por ejemplo 111111. Todavía no lo he probado para la producción en el orden de miles, dos de las expresiones regulares pueden volverse un poco lentas después de un tiempo, pero puede manejar fácilmente un par de cientos en unos segundos.

Explicación

Esta es una solución simple de retroceso.

1. Anexar a 0.
2. Si bien la secuencia actual no es válida, elimine todos los 3 finales e incremente los últimos no 3.
3. Repita hasta que tengamos una secuencia válida de la longitud deseada.

Este retroceso se implementa mediante un bucle de sustituciones de expresiones regulares que aborta una vez que la cadena permanece sin cambios a través de una iteración.

$
_

Esto agrega un _a la entrada, que se utiliza para separar la entrada unaria de la secuencia que estamos construyendo.

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

Esta es la primera sustitución en el bucle (indicado por el líder (). La expresión regular coincide si a) hay un carácter de palabra (es decir, un dígito) al final de la cadena (lo que significa que la cadena es válida; veremos a continuación que las secuencias no válidas están marcadas con un final #) yb) hay al menos tantos caracteres en la secuencia como en la entrada (esto se verifica usando grupos de equilibrio ). Si ese es el caso, eliminamos la entrada y agregamos a !. Esto !sirve para hacer que todas las expresiones regulares en el bucle fallen, de modo que finalice.

\b$
0

Si hay un carácter de palabra al final (es decir, la secuencia es válida y el ciclo no finalizó en el paso anterior), agregue a 0.

3#
#

Si (en cambio) la secuencia se marcó como inválida y terminó en 3, la eliminamos 3(pero dejamos la secuencia como inválida, porque no hay continuación posible para el prefijo actual ... por lo que el siguiente carácter también debe retroceder).

0#
1
1#
2
2#
3

Si la secuencia está marcada como no válida y cualquier dígito que no 3sea ​​al final, incrementaremos el dígito y eliminaremos el marcador.

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

La última sustitución en el bucle (como lo indica el )). Comprueba si la cadena termina en ABA(donde Bno es más larga Apero está potencialmente vacía). Las longitudes relativas de Ay Bse verifican nuevamente utilizando grupos de equilibrio, y la repetición de Ase verifica con una simple referencia inversa.

Si esta expresión regular coincide, marcamos la secuencia como inválida agregando #.

!
<empty>

Una vez que el ciclo termina, todo lo que tenemos que hacer es eliminar el !y luego quedar con la salida deseada.

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 es el algoritmo codicioso con retroceso. Desearía que fuera más corto. Espero que sea correcto (ver más abajo).

Construye la cadena un dígito a la vez. Dada una cadena de ddígitos que ya ha encontrado, intenta agregar a 0como el (d+1)dígito st. Si eso no funciona, entonces intenta a 1, luego a 2, luego a 3. Si ninguno de estos funciona, vuelve al ddígito th y lo incrementa (si es menor que 3) o lo elimina (si es igual a 3, en cuyo caso incrementa el anterior, etc.).

La verificación de validez es la línea que .findcontiene. En caso de que alguien decida leer mi código, debo decir que este programa en realidad está almacenando la cadena hacia atrás, lo que significa que está agregando dígitos al frente . Por lo tanto, la verificación implica buscar lugares donde los primeros c dígitos aparecen nuevamente más adelante en la cadena (en cualquier lugar después de los primeros cdígitos), y si hay tales lugares, si la longitud intermedia es como máximo c.

(Por supuesto, invierte la cadena antes de imprimir).

También podría ser fácilmente más rápido; Originalmente tuve que salir de varios bucles temprano por eficiencia, pero eso costó bytes preciosos. Sin embargo, todavía funciona bien en el rango de n=1000.

De todos modos, el programa parece exhibir una preferencia por los dígitos más pequeños, pero no es una preferencia muy fuerte. Por ejemplo, ejecutarlo n=2000me dio una cadena con 523ceros, 502unos, 497dos y 478tres, terminando en 30210312013021. Entonces, si alguien más está trabajando en un algoritmo codicioso, tal vez puedan confirmar este resultado. O con n=1000lo conseguido [263, 251, 248, 238]por los conteos por dígitos.

Finalmente, mencionaría que estos recuentos sugieren una especie de simetría, casi (aunque no exactamente) como si hubiéramos comenzado con una distribución uniforme y luego hubiéramos convertido algunas de las 3's en 0' sy algunas de las 2's en 1' s. Pero obviamente eso podría ser una coincidencia. ¡No tengo idea!

Haskell, 115 (120 bytes - 5 bonus)

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.([]?)

Corre en línea en Ideone

Ejemplo de ejecución:

*Main> f 40
"0120310213012310320130210312013210230120"