Cerradura de bicicleta combinada

46

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. Cerradura de bicicleta combinada

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 5737a 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 5737hacia 6837o hacia 5626. Moverse de 5737a 6838no 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.

Lui
fuente
18
Bienvenido a PPCG; muy bonito primer reto!
Pomo de la puerta
44
¡Esto me parece sólido! Bienvenido a PPCG!
Mego
1
Buen desafío ¿Puedo preguntar cuál debería ser la salida para los casos: 7478 y 3737?
noisyass2
1
@ noisyass2 Gracias; La respuesta de flawr da lo siguiente: 7478 8588 9698 0708 0808 0908 0008 0009 0000 y 3737 2627 1517 0407 0307 0207 0107 0007 0008 0009 0000 Solo mirando el 3737, esto tiene sentido: Mirando los primeros 3 dígitos solamente: Si me muevo todos los primeros tres al mismo tiempo, toma 3 movimientos para los dígitos 1 y 3, y luego otros 4 movimientos para el dígito 2, por lo tanto, un total de siete. Mientras que si muevo cada uno individualmente, cada uno toma 3 movimientos, por lo tanto 9 movimientos.
Lui
1
Me pregunto si el título "Bloqueo de combinación" (o "Bloqueo de bicicleta") podría atraer a más espectadores.
DavidC

Respuestas:

10

Matlab, 412 327 bytes

Golfed (¡Gracias a @AndrasDeak por jugar al golf s!):

s=dec2bin('iecbmgdoh'.'-97)-48;s=[s;-s];T=1e4;D=Inf(1,T);P=D;I=NaN(T,4);for i=1:T;I(i,:)=sprintf('%04d',i-1)-'0';end;G=input('');D(G+1)=0;for k=0:12;for n=find(D==k);for i=1:18;m=1+mod(I(n,:)+s(i,:),10)*10.^(3:-1:0)';if D(m)==Inf;D(m)=k+1;P(m)=n-1;end;end;end;end;n=0;X='0000';while n-G;n=P(n+1);X=[I(n+1,:)+48;X];end;disp(X)

Este código usa alguna programación dinámica para encontrar la 'ruta' más corta desde el número dado para 0000usar 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:

9871
0981
0091
0001
0000

1210
0100
0000

Examples by @noisyass:

7478
8578
9678
0788
0899
0900
0000

3737
2627
1517
0407
0307
0207
0107
0007
0008
0009
0000

Own Example (longest sequence, shared with 6284)

4826
3826
2826
1826
0826
0926
0026
0015
0004
0003
0002
0001
0000    

Código completo (incluidos algunos comentarios):

%steps
s=[eye(4);1,1,0,0;0,1,1,0;0,0,1,1;1,1,1,0;0,1,1,1];
s=[s;-s];


D=NaN(1,10000);%D(n+1) = number of steps to get to n
P=NaN(1,10000);%P(n+1) was last one before n

I=NaN(10000,4);%integer representation as array
for i=0:9999; 
    I(i+1,:)=sprintf('%04d',i)-'0';
end

G=9871; % define the current number (for the golfed version replaced with input('');
D(G+1)=0;
B=10.^(3:-1:0); %base for each digit

for k=0:100; %upper bound on number of steps;
    L=find(D==k)-1;
    for n=L; %iterate all new steps
        for i=1:18; %search all new steps
            m=sum(mod(I(n+1,:)+s(i,:),10) .* [1000,100,10,1]);
            if isnan(D(m+1))
                D(m+1) = k+1;
                P(m+1)=n;
            end
        end
    end
end
n=0;%we start here
X=[];
while n~=G
    X=[I(n+1,:)+'0';X];
    n=P(n+1);
end
disp([I(G+1,:)+'0';X,''])
falla
fuente
¡Agradable! Siendo un usuario mayormente de Matlab, me preguntaba qué tan bien le iría.
Lui
1
Para ingresar 6444su 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.
Lui
1
Acabo de corregir un pequeño error en el código. En sla última fila debería estar [0,1,1,1]. ¡Entonces también obtienes una solución de 8 pasos! Disculpe las molestias =)
error
1
@Lui Hay una sala de chat matlab / octava , entre otras cosas, es una especie de Base para el lenguaje de golf derivado de Matlab MATL.
falla
1
para 4826, encontré una solución de 11 movimientos: 4826 3716 2606 1506 0406 0306 0206 0106 0007 0008 0009 0000
noisyass2
4

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, de 1234a 0224.

set / px =
establecer a =% x: ~ 0,1% y establecer b =% x: ~ 1,1% y establecer c =% x: ~ 2,1% y establecer d =% x: ~ 3,1%
: l
@echo% x% & if% a% == 0 (if% d% NEQ 0 set / ad = d-1) else set / aa = a-1
@if% b% NEQ 0 set / ab = b-1
@if% c% NEQ 0 set / ac = c-1
@if% x% NEQ 0000 set x =% a %% b %% c %% d% & goto l

Esta es mi solución Batch: 236 bytes.


Editar: solución corregida

set / px =
establecer a =% x: ~ 0,1% y establecer b =% x: ~ 1,1% y establecer c =% x: ~ 2,1% y establecer d =% x: ~ 3,1%
: l
@echo% x% & set k = 1 & if% a% == 0 (if% d% NEQ 0 set / ad = d-1 & set k = 0) else set / aa = a-1 & set k = 1
@if% b% NEQ 0 si% k% == 1 set / ab = b-1 & set k = 0
@if% c% NEQ 0 si% k% == 0 set / ac = c-1
@if% x% NEQ 0000 set x =% a %% b %% c %% d% & goto l

La nueva solución (arreglada de acuerdo con los comentarios subyacentes) tiene 288 bytes.

hacer ruido
fuente
No he visto tu respuesta en gran profundidad, pero estoy luchando por seguir tu lógica en el primer párrafo. ¿A qué ejemplo te refieres específicamente? Y su ejemplo de ir de 1234a 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.
Lui
Quiero decir, si puedes mover 3 anillos consecutivos, es razonable pensar que también puedes mover el primero y el tercero, evitando el segundo. ¿O debería cambiar mi código?
Noize
Tu suposición es incorrecta; Deberías cambiar tu código. ¿Ves la lógica como se explica en el comentario anterior?
Lui
Código fijo Verifiqué con varios tipos diferentes de combinaciones y me parece que siempre toma el camino más corto.
Noize
Esto parece solo contar hacia abajo, por lo que lleva más tiempo del necesario para combinaciones con números altos (por ejemplo, 18 movimientos para 9999)
faubi
2

Haskell - 310 bytes

import Data.Char
import Data.List
r=replicate
h=head
a x=map(:x)[map(`mod`10)$zipWith(+)(h x)((r n 0)++(r(4-j)q)++(r(j-n)0))|j<-[1..3],n<-[0..j],q<-[1,-1]]
x!y=h x==h y
x#[]=(nubBy(!)$x>>=a)#(filter(![(r 4 0)])x)
x#y=unlines.tail.reverse.map(intToDigit<$>)$h y
main=do x<-getLine;putStrLn$[[digitToInt<$>x]]#[]

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.

faubi
fuente
Parece una base sólida para su enfoque. No tengo experiencia con Haskell, ni (que yo sepa) ningún medio para compilarlo / ejecutarlo. Un google rápido tampoco me da ningún lugar donde pueda probarlo. ¿Eres capaz de dar un enlace que me permite probarlo? Gracias.
Lui
@Lui Se puede compilar con el Glasgow Haskell Compiler , pero aparte de descargarlo y usarlo, no conozco ninguna forma de ejecutarlo.
faubi