El escenario
Después de un largo día de trabajo en la oficina y hojeando stackexchange.com , finalmente salgo por la puerta a las 16:58, ya cansado con el día. Debido a que todavía soy solo un interno, mi medio de transporte actual es en bicicleta. Me dirijo a mi confiable Peugeot Reynolds 501 , pero antes de que pueda navegar, necesito desbloquearlo. El bloqueo es un bloqueo de combinación estándar de cuatro dígitos (0-9), a través del cuadro y la rueda delantera. Mientras trato de permanecer despierto, levanto mi mano para entrar en la combinación.
El reto
Debido a que mis dedos están tan cansados, quiero girar la cerradura a la combinación correcta con la menor cantidad de movimientos. Un movimiento se define como una rotación de una posición (36 grados), por ejemplo, hay un movimiento de 5737
a 5738
. Sin embargo, puedo agarrar hasta tres anillos consecutivos al mismo tiempo y rotarlos como uno , lo que solo cuenta como un solo movimiento. Por ejemplo, también hay un solo movimiento desde 5737
hacia 6837
o hacia 5626
. Moverse de 5737
a 6838
no es un movimiento, ya que los dígitos número 1,2 y 4 se han movido en la misma dirección, pero independientemente del número número 3.
Por lo tanto, para una combinación dada, puedo ver en el candado de la bicicleta (cualquier número entero de 4 dígitos), cuál es el número más bajo de movimientos que puedo hacer para desbloquearlo, y sí, puedo rotar en cualquier dirección en cualquier momento. Con esto quiero decir que puedo girar algunos dígitos en una dirección y otros dígitos en la otra dirección: no todos mis movimientos serán en sentido horario o horario para cada desbloqueo.
Como soy vago, mi código de desbloqueo es 0000.
Este es el código de golf. No puedo molestarme en escribir mucho código, por lo que gana el programa más corto en número de bytes.
La entrada es de stdin, y su código debe generar las combinaciones que puedo ver en cada paso después de cada movimiento, incluido el 0000 al final. Cada una de las combinaciones de salida debe estar separada por un espacio / nueva línea / coma / punto / ampersand.
Ejemplos
Input: 1210
0100
0000
Input: 9871
9870
0980
0090
0000
Input: 5555
4445&3335&2225&1115&0005&0006&0007&0008&0009&0000
Input: 1234
0124 0013 0002 0001 0000
Intenté publicar esto en http://bicycles.stackexchange.com , pero no les gustó ...
Descargo de responsabilidad: Primero golf, así que cualquier cosa que esté rota / cualquier información faltante ¡hágamelo saber! También hice todos los ejemplos a mano, por lo que puede haber soluciones que implican menos movimientos.
EDITAR: Para las respuestas que tienen múltiples rutas de solución con el mismo número de movimientos (prácticamente todas), no hay una solución preferida.
Respuestas:
Matlab,
412327 bytesGolfed (¡Gracias a @AndrasDeak por jugar al golf
s
!):Este código usa alguna programación dinámica para encontrar la 'ruta' más corta desde el número dado para
0000
usar solo los pasos posibles. El desafío es básicamente un problema de la ruta más corta (alternativamente, tal vez podría considerar los pasos como un grupo de conmutación), pero la dificultad fue encontrar una implementación eficiente . Las estructuras básicas son dos matrices de 10000 elementos, una para almacenar el número de pasos para llegar a ese índice, la otra para almacenar un puntero al 'nodo' anterior en nuestro gráfico. Simultáneamente calcula las 'rutas' a todos los demás números posibles.Ejemplos:
Código completo (incluidos algunos comentarios):
fuente
6444
su código, da 6444 7554 8664 9774 0884 0994 0004 0003 0002 0001 0000, mientras que encuentro que la respuesta es 6444 6333 6222 6111 6000 7000 8000 9000 0000. Mi respuesta es 8 pasos, el suyo es 10. No puedo ver el problema, y parece estar allí tanto en la versión golfizada como no golfista. Esto se soluciona en su última edición.s
la última fila debería estar[0,1,1,1]
. ¡Entonces también obtienes una solución de 8 pasos! Disculpe las molestias =)Lote - 288 bytes
Incluso si dijiste que tienen que ser consecutivos (los anillos), asumo por lógica (siguiendo el ejemplo) que puedo omitir el del medio, de1234
a0224
.Esta es mi solución Batch: 236 bytes.Editar: solución corregida
La nueva solución (arreglada de acuerdo con los comentarios subyacentes) tiene 288 bytes.
fuente
1234
a no0224
es un solo movimiento. La idea es que con el uso de solo dos dedos puedo agarrar hasta tres anillos consecutivos con un solo agarre.Haskell - 310 bytes
Esto funciona al construir repetidamente una nueva lista de combinaciones aplicando cada turno posible a cada combinación ya alcanzada hasta que una de ellas sea la combinación correcta. Los duplicados se eliminan de la lista en cada iteración para evitar que el uso de memoria crezca exponencialmente.
Como solución de fuerza bruta, esto es muy ineficiente y puede tardar varios minutos en ejecutarse.
No tengo mucha experiencia con Haskell, por lo que probablemente se podría hacer algo mejor.
fuente