Imagine un camino formado por <y >y que termine en a @, por ej.
><>@
Un caminante comienza en la celda más a la izquierda. Atravesará el camino de la siguiente manera:
- Si el caminante está en una
@celda, ha alcanzado la meta y ya está. - Si el andador está en una
>celda, todo el camino se desplaza un paso hacia la derecha, cíclicamente, llevándose al andador . - Si el caminante está en una
<celda, todo el camino se desplaza un paso hacia la izquierda, cíclicamente, llevándose al caminante . - Luego, el caminante da un solo paso. Si está en cualquier extremo del camino, se aleja del final. De lo contrario, sigue moviéndose en la dirección en que se movió en el último paso (ignorando la rotación), caminando hacia la derecha inicialmente.
Analicemos el ejemplo anterior. La posición del caminante está marcada con ^:
><>@ --rotate--> @><>
^ ^
step right (first step):
@><> --rotate--> ><>@
^ ^
step right:
><>@ --rotate--> @><>
^ ^
step left (dead end):
@><> --rotate--> ><>@
^ ^
step left:
><>@ --rotate--> @><>
^ ^
step left:
@><> Goal reached!
^
El caminante visitó 6 celdas en el proceso (incluidas la celda inicial y la celda @y contando cada celda con la frecuencia que se visita).
Aquí hay un pequeño ejemplo, donde el andador se transporta a través de los bordes mediante una rotación:
>>@ --rotate--> @>>
^ ^
step right (first step):
@>> --rotate--> >@>
^ ^
step right (dead end):
>@> Goal reached!
^
Esta vez el caminante visitó 3 celdas.
Podemos convertir esto fácilmente en una secuencia entera:
- Te dan un entero positivo N , por ejemplo
9. - Calcula la representación binaria de este entero, por ejemplo
1001. - Luego convertir
1en>y0en<y agregar un@:><<>@. - Nos asociamos con N el número de células visitadas por el caminante en el número construido de esta manera.
Los primeros elementos de la secuencia resultante son:
2, 3, 3, 4, 6, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6,
6, 10, 6, 10, 8, 8, 6, 10, 8, 8, 6, 6, 6, 6, 7, 7
Esto puede parecer bastante arbitrario, pero la secuencia resultante en realidad resulta tener mucha estructura:
Como referencia, puede encontrar los primeros 2048 números de la secuencia en este pastebin .
El reto
Lo has adivinado: debes calcular la secuencia anterior. Puedes hacerlo de tres maneras:
- Puede producir una secuencia infinita (mientras la memoria lo permita), ya sea emitiendo continuamente (separados por caracteres no numéricos) valores o utilizando alguna forma de generador infinito en los idiomas que los admiten. Si imprime una secuencia infinita en STDOUT, no tiene que imprimir los números uno por uno, pero asegúrese de que cada número se imprima después de un período de tiempo finito (y en orden). Si usa esta opción, no debe tomar ninguna entrada.
- Puede tomar un entero N como entrada y producir el N º término de la secuencia.
- Puede tomar un entero N como entrada y producir todo hasta el N º término de la sucesión, ya sea como una lista o una cadena utilizando un separador de ambigüedades.
Como no quiero penalizar los idiomas que no pueden convertir fácilmente entre bases, en lugar del entero N , puede tomar la representación binaria de N , usando 0sy1 s como de costumbre (como una lista o cadena), con la mayoría -Pequeño bit primero.
Puede escribir un programa o función, tomando la entrada a través de STDIN (o la alternativa más cercana), argumento de línea de comando o argumento de función y generando el resultado a través de STDOUT (o la alternativa más cercana), el valor de retorno de la función o el parámetro de función (out).
Estándar Aplican reglas código de golf .
Antecedentes
Esto realmente calcula el número de "ticks" que un intérprete directo de mi lenguaje de programación esotérico Labyrinth necesitaría para interpretar la "ruta" como código fuente. En ese caso, el "caminante" es simplemente el puntero de instrucción (que tiene una posición y una dirección), el @comando termina el programa <y >son comandos de modificación del código fuente.
Respuestas:
Jalea , 10 bytes
Esta función acepta un solo entero en forma de la lista de sus dígitos binarios como entrada.
El algoritmo es equivalente al de la respuesta de @ Agawa001 .
Pruébalo en línea! o generar los primeros 2048 números .
Antecedentes
Enumere las posiciones debajo de la ruta de 0 a L , dando un total de L + 1 posiciones. L coincide con el número de dígitos binarios del número N que codifica la ruta. Con esta notación, el caminante comienza en la posición 0 , el gol en la posición L .
Con cada paso que da el caminante, se acerca un paso más a la meta (en la dirección en la que camina actualmente). Además, con cada paso de cambio, dependiendo de si camina con o en contra de la dirección de cambio, aumenta o disminuye su posición en 2 módulos L + 1 , o permanece en la posición actual.
Para cambiar de dirección, tiene que aterrizar en la posición L - 1 (mirando hacia L ) o en la posición 1 (mirando hacia 0 ), y luego desplazarse en su dirección. El siguiente paso que tome lo llevará de regreso a su posición anterior, mirando hacia la dirección opuesta.
Si L es par, L - 1 es impar, por lo que no puede avanzar desde su posición inicial a L - 1 directamente. La única forma de alcanzarlo es pasar por L , ser llevado a 0 y dar el siguiente paso para aterrizar en 1 , luego avanzar hacia la derecha. Esto requiere avanzar en posiciones de 2L , lo que se puede hacer en no menos de L pasos.
Sin embargo, después de dar pasos L sin cambiar de dirección, habrá alcanzado la meta. Al agregar uno para la celda inicial, obtenemos un total de celdas visitadas L + 1 en este caso.
Si L es impar, L - 1 es par, por lo que puede alcanzar esa posición desplazándose (L - 1) / 2 veces hacia la derecha. Si la posición L - 1 está debajo de un 1 en ese momento, será desplazado a la posición L , se dará la vuelta y pisará la posición L - 1 (mirando hacia la izquierda).
Esto puede o no suceder antes de que alcance su objetivo, por lo que hay dos casos para analizar:
Si hay menos de (L + 1) / 2 ocurrencias de 1 en la expansión binaria de N , dar pasos L no será suficiente para girar la dirección. Dado que estos pasos L llevan al caminante a su objetivo, agregando uno para la celda inicial, obtenemos un total de celdas visitadas L + 1 en este caso.
Si hay al menos (L + 1) / 2 ocurrencias de 1 en la expansión binaria de N , avanzando a la ((L + 1) / 2) º ocurrencia requerirá I pasos, donde I es la posición inicial de que la aparición de 1 .
Por lo tanto, después de tomar pasos I , el andador está en la posición L - 1 , mirando hacia la izquierda. Para cambiar de dirección nuevamente, tendría que caminar hacia la izquierda hacia la posición 1 . Sin embargo, como en el caso par, dado que (L - 1) - 1 es impar, esto requerirá pasar por 0 y tomar no menos de L pasos.
Dado que la distancia inicial a la meta en la dirección izquierda es 1 , después de dar los pasos I , el caminante se encuentra a una distancia de I + 1 de la meta después de cambiar de dirección. Como I <L , tenemos que I + 1 ≤ L , por lo que los próximos pasos de I + 1 lo llevarán a la meta.
Esto da un total de I + I + 1 = 2I + 1 pasos dados. Agregando uno para la celda inicial, obtenemos un total de 2I + 1 + 1 = 2 (I + 1) celdas visitadas en este caso.
Cómo funciona
fuente
Matlab (puntaje = 230, n = inf)
infsi desea mantener el infinito).h=1000000000000000000000000000000000000000000000000000;w(h,h+1)para asegurarse.El algoritmo sigue un enfoque matemático que explicaré más adelante, y confirma la lista referenciada de Martin, basándose en este programa:
Dado que el algoritmo verifica 2048 primeros casos de prueba, asumiré ciegamente que lo haría para cualquier caso de prueba, por lo que mi algoritmo funciona con respecto a algunas propiedades que descubrí en este proceso sin el dolor de cambiar y mover el puntero:
1- si el doble del número de 1 en la traducción binaria no excede la longitud de la secuencia,
Lentonces la salida esL+12- si la longitud de la secuencia es par y la condición anterior no está establecida, por lo que la salida es la misma
L+13- de lo contrario, la salida es dos veces el
L/2índice th de 1.fuente
a=dec2bin(input(''));c=find(a=='1');g=nnz(a)+1;if nnz(c)<g/2|mod(g,2);g,else,2*c(g/2),end, lo que solo da un elemento único de la secuencia.Python,
122119113110108107103 bytesToma la entrada como una lista de dígitos binarios. Función auxiliar para probar:
Crédito a Lynn por guardar 7 bytes.
fuente
p-d-1in[-2,w]guarda un byte.d*=2*(1!=d-p>~w)-1ahorra cuatro más! ° v °Python 2, 99 bytes
Puerto de Python de la brillante respuesta de Agawa001.
Versión legible:
fuente
MATL,
31, 25 bytesEsta es solo una versión MATL del algoritmo de Agawa001, excepto que toma una entrada entera N y devuelve el término N-ésimo en la secuencia. ¡Fue difícil mantenerse al día con todos los elementos en la pila! Tuve que recurrir al uso de un portapapeles para evitar volverme loco. ¡Puedes probarlo en línea!
Se puede convertir en un bucle imprimiendo los primeros N términos agregando
:"@antes del código, y]Ddespués.¡Gracias a Luis Mendo por guardar 6 bytes completos!
fuente
Julia 0.4, 4̷4̷ 42 bytes
Esta función acepta un solo entero en forma de la lista de sus dígitos binarios como entrada.
El algoritmo es equivalente al de la respuesta de @ Agawa001 y mi respuesta Jelly .
Pruébalo en línea!
Cómo funciona
find(x)devuelve los índices basados en 1 de todos los elementos distintos de cero de x . Intentamos acceder a la matriz resultante en el índice k / 2 y, si tiene éxito, sobrescribimos k con el doble del índice seleccionado.Esto fallará si y solo si uno de los siguientes es verdadero:
k / 2 es un flotante no integral, por lo que se genera InexactError .
La matriz de índice tiene menos de k / 2 elementos, por lo que se genera un BoundsError .
En cualquier caso, sobrescribir k fallará, por lo que se devolverá su valor original.
fuente
JavaScript (ES6), 65 bytes
Acepta una cadena binaria. Utiliza el cheque de rebote de las otras respuestas.
fuente
Python 2, 74 bytes
Esta función acepta un solo entero en forma de la lista de sus dígitos binarios como entrada.
El algoritmo es equivalente al de la respuesta de @ Agawa001 y mi respuesta Jelly .
Pruébalo en Ideone .
Cómo funciona
nextintenta encontrar el primer número entero 2i para el cualk==2*sum(x[:i])devuelve verdadero. Comox[:i]contiene elementos i , esto da el índice basado en 1 de (k / 2) th 1 .nextfallará si k / 2 no es integral o si x contiene menos de k / 2 unidades. En este caso, se devuelve el valor predeterminado k .fuente
> <> , 63 bytes
Desde el momento en que vi el patrón de ejemplo en este desafío, supe qué idioma usar :)
Usando N para obtener el N º plazo.
Se supone que la entrada está en binario en la pila. En lugar de mover el andador, esta solución se basa principalmente en mover la cinta debajo del andador.
Pruébalo en línea!
fuente