Cadenas à vélo

46

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. Cadenas à vélo

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.

Lui
la source
18
Bienvenue chez PPCG; très beau premier challenge!
Poignée de porte
4
Cela me semble solide! Bienvenue chez PPCG!
Mego
1
Beau défi. Puis-je demander quelle devrait être la sortie pour les cas: 7478 et 3737?
noisyass2
1
@ noisyass2 Merci; La réponse de flawr donne ceci: 7478 8588 9698 0708 0808 0908 0008 0009 0000 et 3737 2627 1517 0407 0307 0207 0107 0007 0008 0009 0000 Rien qu'en regardant le 3737, cela n'a de sens: En regardant que les 3 premiers chiffres: Si je bouge tous les trois premiers en même temps, il faut 3 mouvements pour les chiffres 1 et 3, puis 4 autres mouvements pour le chiffre 2, soit un total de sept. Alors que si je bouge chacun individuellement, chacun prend 3 coups, soit 9 mouvements.
Lui
1
Je me demande si le titre "Combination Lock" (ou "Bike Lock") pourrait attirer davantage de téléspectateurs.
DavidC

Réponses:

10

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,''])
flawr
la source
Agréable! Étant moi-même principalement utilisateur de Matlab, je me demandais si tout se passerait bien.
Lui
1
Pour entrer 6444votre code, donne 6444 7554 8664 9774 0884 0994 0004 0003 0002 0001 0000, alors que je trouve que la réponse est 6444 6333 6222 6111 6000 7000 8000 9000 0000. Ma réponse est 8 étapes, la vôtre est 10. Je ne peux pas voir le question, et il semble être là à la fois dans la version golfée et non-golfée. Ceci est corrigé dans votre dernière édition.
Lui
1
Je viens de corriger une petite erreur dans le code. Dans sla dernière rangée devrait être [0,1,1,1]. Ensuite, vous obtenez également une solution en 8 étapes! Je suis désolé pour le désagrément =)
mardi
1
@Lui Il y a un chat matlab / octave , entre autres c'est une sorte de base pour la langue de golf MATLab dérivée de Matlab.
mardi
1
pour 4826, j'ai trouvé une solution en 11 coups: 4826 3716 2606 1506 0406 0306 0206 0106 0007 0008 0009 0000
noisyass2
4

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.

noize
la source
Je n'ai pas examiné votre réponse de manière approfondie, mais j'ai du mal à suivre votre logique dans le premier paragraphe. De quel exemple parlez-vous précisément? Et votre exemple d'aller de 1234à 0224n'est pas un mouvement. L'idée est que, avec seulement deux doigts, je peux saisir jusqu'à trois bagues consécutives avec une seule poignée.
Lui
Je voulais dire, si vous pouvez déplacer 3 anneaux consécutifs, il est raisonnable de penser que vous pouvez également déplacer les premier et troisième, en évitant le second. Ou devrais-je changer mon code?
Noize
Votre hypothèse est fausse; vous devriez changer votre code. Voyez-vous la logique telle qu'expliquée dans le commentaire ci-dessus?
Lui
Code corrigé. J'ai vérifié avec plusieurs types de combinaisons et il me semble que cela prend toujours le chemin le plus court.
Noize
Cela semble ne compter que vers le bas, il faut donc plus de temps que nécessaire pour les combinaisons avec des nombres élevés (par exemple, 18 coups pour 9999)
faubi
2

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é.

faubi
la source
Cela semble être une base solide pour votre approche. Je n'ai pas d'expérience avec Haskell, ni (à ma connaissance, aucun moyen de le compiler ou de le lancer). Un rapide Google ne me donne nulle part où je peux l'essayer non plus. Pouvez-vous donner un lien qui me permet de l'essayer? Merci.
Lui
@Lui Il peut être compilé avec le compilateur Glasgow Haskell , mais mis à part le téléchargement et l'utilisation, je ne connais aucun moyen de le lancer.
Faubi