Le scénario

Après une longue journée de travail au bureau et à parcourir le site stackexchange.com , j’ai finalement franchi la porte à 16h58, déjà fatiguée par la journée. Comme je ne suis encore qu’un stagiaire, mon moyen de transport actuel est le vélo. Je me dirige vers mon fidèle Peugeot Reynolds 501 , mais avant de pouvoir naviguer au-dessus, je dois le déverrouiller. La serrure est une serrure à combinaison à quatre chiffres standard (0-9) traversant le cadre et la roue avant. Alors que j'essaie de rester éveillé, je lève la main pour entrer dans la combinaison.

Le défi

Parce que mes doigts sont si fatigués, je veux que la serrure soit correctement assortie du moins possible de mouvements. Un mouvement est défini comme une rotation d'une position (36 degrés). Par exemple, il y a un mouvement de 5737à 5738. Cependant, je suis capable de saisir jusqu'à trois sonneries consécutives à la fois et de les faire tourner comme un seul , ce qui ne compte que pour un seul mouvement. Par exemple , il y a aussi un seul mouvement de 5737la 6837ou 5626. Aller de 5737à 6838n'est pas un mouvement, car les chiffres 1, 2 et 4 ont évolué dans le même sens, mais indépendamment du chiffre 3.

Par conséquent, pour une combinaison donnée, je peux voir sur le cadenas du vélo (tout nombre entier à 4 chiffres), quel est le plus petit nombre de mouvements que je peux faire pour le déverrouiller, et oui, je peux effectuer une rotation dans n'importe quelle direction à tout moment. J'entends par là que je peux tourner certains chiffres dans une direction et d'autres chiffres dans l'autre direction: tous mes mouvements ne seront pas dans le sens contraire des aiguilles d'une montre ou dans le sens des aiguilles d'une montre pour chaque déverrouillage.

Parce que je suis paresseux, mon code de déverrouillage est 0000.

C’est du code golf, je ne me dérange pas pour écrire beaucoup de code, donc le programme le plus court en nombre d’octets gagne.

L'entrée est à partir de stdin, et votre code doit générer les combinaisons que je peux voir à chaque étape après chaque mouvement, y compris le 0000 à la fin. Chaque sortie des combinaisons doit être séparée par un espace / nouvelle ligne / virgule / période / esperluette.

Exemples

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

J'ai essayé de poster ceci sur http://bicycles.stackexchange.com , mais ils ne l'ont pas aimé ...

Clause de non-responsabilité: Premier golf, donc tout ce qui est brisé / toute information manquante faites le moi savoir! De plus, j'ai fait tous les exemples à la main, il peut donc y avoir des solutions qui impliquent moins de mouvements!

EDIT: Pour les réponses qui ont plusieurs chemins de solution avec un nombre égal de mouvements (pratiquement tous), il n'y a pas de solution préférée.

Matlab, 412 327 octets

Golfé (Merci à @AndrasDeak pour le 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)

Ces codes utilisent une programmation dynamique pour trouver le "chemin" le plus court du nombre donné et 0000utiliser uniquement les étapes possibles. Le défi est fondamentalement un prioblème de chemin le plus court (vous pouvez également envisager les étapes en tant que groupe commutatif), mais la difficulté consistait à trouver une mise en œuvre efficace . Les structures de base sont deux tableaux de 10000 éléments, l’un pour stocker le nombre d’étapes permettant d’atteindre cet index, l’autre pour stocker un pointeur sur le «nœud» précédent de notre graphique. Il calcule simultanément les "chemins" vers tous les autres nombres possibles.

Exemples:

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    

Code complet (avec quelques commentaires):

%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,''])

Lot - 288 octets

Même si vous avez dit qu'ils doivent être consécutifs (les anneaux), je suppose par logique (en suivant l'exemple) que je peux ignorer celui du milieu, de 1234à 0224.

set / px =
définir a =% x: ~ 0,1% et définir b =% x: ~ 1,1% et définir c =% x: ~ 2,1% et définir d =% x: ~ 3,1%
: l
@echo% x% & if% a% == 0 (si% d% NEQ 0 set / ad = d-1) sinon set / aa = a-1
@if% b% NEQ 0 set / ab = b-1
@if% c% NEQ 0 set / ac = c-1
@if% x% NEQ 0000 défini x =% a %% b %% c %% d% & goto l

Ceci est ma solution de lot: 236 octets.

Edit: solution corrigée

set / px =
définir a =% x: ~ 0,1% et définir b =% x: ~ 1,1% et définir c =% x: ~ 2,1% et définir d =% x: ~ 3,1%
: l
@echo% x% & set k = 1 & si% a% == 0 (si% d% NEQ 0 set / ad = d-1 & set k = 0) sinon set / aa = a-1 & set k = 1
@if% b% NEQ 0 si% k% == 1 ensemble / ab = b-1 & ensemble k = 0
@if% c% NEQ 0 si% k% == 0 ensemble / ac = c-1
@if% x% NEQ 0000 défini x =% a %% b %% c %% d% & goto l

La nouvelle solution (corrigée en fonction des commentaires sous-jacents) est lourde de 288 octets.

Haskell - 310 octets

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]]#[]

Cela fonctionne en construisant de manière répétée une nouvelle liste de combinaisons en appliquant chaque tour possible à chaque combinaison déjà atteinte jusqu'à ce que l'une d'entre elles soit la bonne combinaison. Les doublons sont supprimés de la liste à chaque itération pour éviter que l'utilisation de la mémoire ne croisse de façon exponentielle.

En tant que solution de force brute, ceci est très inefficace et peut prendre plusieurs minutes à s'exécuter.

Je n'ai pas beaucoup d'expérience avec Haskell, donc quelque chose pourrait probablement être amélioré.