Zahlenschloss

46

Das Szenario

Nach einem langen Arbeitstag im Büro und dem Durchstöbern von stackexchange.com gehe ich endlich um 16:58 Uhr aus der Tür, schon müde vom Tag. Da ich noch Praktikant bin, bin ich momentan mit dem Fahrrad unterwegs. Ich gehe zu meinem vertrauenswürdigen Peugeot Reynolds 501 , aber bevor ich davonsegeln kann, muss ich ihn entsperren. Das Schloss ist ein vierstelliges Standardkombinationsschloss (0-9) über den Rahmen und das Vorderrad. Während ich versuche, wach zu bleiben, ziehe ich meine Hand nach oben, um in die Kombination einzutreten. Zahlenschloss

Die Herausforderung

Weil meine Finger so müde sind, möchte ich das Schloss mit den wenigsten Bewegungen auf die richtige Kombination drehen. Eine Bewegung ist definiert als eine Drehung um eine Position (36 Grad), zum Beispiel gibt es eine Bewegung von 5737bis 5738. Ich bin jedoch in der Lage, bis zu drei aufeinanderfolgende Ringe gleichzeitig zu erfassen und sie als einen zu drehen , was nur als eine einzige Bewegung zählt. Zum Beispiel gibt es auch nur eine Bewegung von 5737nach 6837oder nach 5626. Das Bewegen von 5737nach 6838ist nicht eine Bewegung, da sich die Ziffern 1, 2 und 4 in die gleiche Richtung bewegt haben, sondern unabhängig von Ziffer 3.

Daher kann ich für eine bestimmte Kombination auf dem Fahrradschloss (eine beliebige 4-stellige Ganzzahl) sehen, wie viele Bewegungen ich am wenigsten ausführen kann, um es zu entsperren, und ja, ich kann mich jederzeit in beide Richtungen drehen. Damit meine ich, dass ich einige Ziffern in die eine und andere Ziffern in die andere Richtung drehen kann: Nicht alle meine Bewegungen werden bei jedem Entsperren im oder gegen den Uhrzeigersinn ausgeführt.

Da ich faul bin, ist mein Freischaltcode 0000.

Dies ist Codegolf Ich kann nicht viel Code schreiben, so dass das kürzeste Programm in Anzahl von Bytes gewinnt.

Die Eingabe erfolgt von stdin, und Ihr Code sollte die Kombinationen ausgeben, die ich bei jedem Schritt nach jeder Bewegung sehen kann, einschließlich der 0000 am Ende. Jede der ausgegebenen Kombinationen sollte durch ein Leerzeichen / Zeilenumbruch / Komma / Punkt / Et-Zeichen getrennt werden.

Beispiele

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

Ich habe versucht, dies auf http://bicycles.stackexchange.com zu posten , aber es hat ihnen nicht gefallen ...

Haftungsausschluss: Erstes Golfen, also alles was kaputt ist / fehlende Informationen lass es mich wissen! Außerdem habe ich alle Beispiele von Hand gemacht, sodass es Lösungen geben kann, die weniger Bewegungen erfordern!

BEARBEITEN: Für Antworten mit mehreren Lösungspfaden und gleicher Anzahl von Bewegungen (praktisch alle) gibt es keine bevorzugte Lösung.

Lui
quelle
18
Willkommen bei PPCG; sehr schöne erste herausforderung!
Türklinke
4
Das sieht für mich solide aus! Willkommen bei PPCG!
Mego
1
Schöne Herausforderung. Kann ich fragen, was die Ausgabe für Fälle sein soll: 7478 und 3737?
noisyass2
1
@ noisyass2 Danke; Die Antwort von flawr lautet wie folgt: 7478 8588 9698 0708 0808 0908 0008 0009 0000 und 3737 2627 1517 0407 0307 0207 0107 0007 0008 0009 0000 Nur die 3737 zu betrachten, macht Sinn: Nur die ersten drei Ziffern zu betrachten: Wenn ich alle bewege die ersten drei gleichzeitig, es dauert 3 Bewegungen für die Ziffern 1 und 3, und dann weitere 4 Bewegungen für die Ziffer 2, also insgesamt sieben. Wenn ich dagegen jeden einzeln bewege, dauert jeder 3 Züge, also 9 Bewegungen.
Lui
1
Ich frage mich, ob der Titel "Combination Lock" (oder "Bike Lock") mehr Zuschauer anziehen könnte.
DavidC

Antworten:

10

Matlab, 412 327 Bytes

Golfen (Danke an @AndrasDeak fürs Golfen 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)

Dieser Code verwendet eine dynamische Programmierung, um den kürzesten "Pfad" von der angegebenen Nummer zu finden 0000und nur die möglichen Schritte zu verwenden. Die Herausforderung ist im Grunde genommen ein Problem mit dem kürzesten Weg (alternativ könnten Sie die Schritte vielleicht als eine kommutative Gruppe betrachten.), Aber die Schwierigkeit bestand darin, eine effiziente Implementierung zu finden. Die Grundstruktur besteht aus zwei 10000-Elemente-Arrays, eines zum Speichern der Anzahl der Schritte, um zu diesem Index zu gelangen, das andere zum Speichern eines Zeigers auf den vorherigen 'Knoten' in unserem Diagramm. Es berechnet gleichzeitig die 'Pfade' zu allen anderen möglichen Zahlen.

Beispiele:

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    

Vollständiger Code (einschließlich einiger Kommentare):

%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,''])
fehlerhaft
quelle
Nett! Da ich selbst größtenteils Matlab-Benutzer bin, habe ich mich gefragt, wie gut es mir gehen würde.
Lui
1
Für die Eingabe 6444gibt Ihr Code 6444 7554 8664 9774 0884 0994 0004 0003 0002 0001 0000, während ich die Antwort als 6444 6333 6222 6111 6000 7000 8000 9000 0000 finde. Meine Antwort ist 8 Schritte, Ihre ist 10. Ich kann die nicht sehen Ausgabe, und es scheint, dort in der Golf- und in der ungolfed Version zu sein. Dies ist in Ihrer letzten Bearbeitung behoben.
Lui
1
Ich habe gerade einen kleinen Fehler im Code behoben. In sder letzten Reihe sollte sein [0,1,1,1]. Dann erhalten Sie auch eine 8-Stufen-Lösung! Es tut mir leid für die Unannehmlichkeiten =)
Fehler
1
@Lui Es gibt einen Matlab / Octave- Chatroom, der unter anderem eine Art Basis für die Matlab-abgeleitete Golfsprache MATL ist.
Fehler
1
für 4826 fand ich eine 11-Zug-Lösung: 4826 3716 2606 1506 0406 0306 0206 0106 0007 0008 0009 0000
noisyass2
4

Batch - 288 Bytes

Selbst wenn Sie sagten, dass sie aufeinanderfolgend sein müssen (die Ringe), gehe ich logischerweise (gemäß dem Beispiel) davon aus, dass ich die mittlere von 1234bis überspringen kann 0224.

setze / px =
setze a =% x: ~ 0,1% & setze b =% x: ~ 1,1% & setze c =% x: ~ 2,1% & setze d =% x: ~ 3,1%
: l
@echo% x% & if% a% == 0 (if% d% NEQ 0 set / ad = d-1) else set / aa = a-1
@wenn% b% NEQ 0 gesetzt / ab = b-1
@wenn% c% NEQ 0 gesetzt ist / ac = c-1
@if% x% NEQ 0000 setze x =% a %% b %% c %% d% & gehe zu l

Dies ist meine Batch-Lösung: 236 Bytes.


Edit: korrigierte Lösung

setze / px =
setze a =% x: ~ 0,1% & setze b =% x: ~ 1,1% & setze c =% x: ~ 2,1% & setze d =% x: ~ 3,1%
: l
@echo% x% & setze k = 1 & falls% a% == 0 (falls% d% NEQ 0 gesetzt / ad = d-1 & setze k = 0) sonst setze / aa = a-1 & setze k = 1
@wenn% b% NEQ 0 ist, wenn% k% == 1 gesetzt / ab = b-1 und k = 0 gesetzt ist
@wenn% c% NEQ 0, wenn% k% == 0 gesetzt ist / ac = c-1
@if% x% NEQ 0000 setze x =% a %% b %% c %% d% & gehe zu l

Die neue Lösung (gemäß den zugrunde liegenden Kommentaren behoben) ist 288 Byte schwer.

Lärm
quelle
Ich habe Ihre Antwort nicht eingehend geprüft, aber ich bemühe mich, Ihrer Logik im ersten Absatz zu folgen. Auf welches Beispiel beziehen Sie sich konkret? Und Ihr Beispiel, von zu gehen 1234, 0224ist keine einzige Bewegung. Die Idee ist, dass ich mit nur zwei Fingern bis zu drei aufeinanderfolgende Ringe mit einem Griff greifen kann.
Lui
Ich meinte, wenn Sie 3 aufeinanderfolgende Ringe bewegen können, ist es vernünftig zu denken, dass Sie auch den ersten und den dritten verschieben können, wobei der zweite vermieden wird. Oder soll ich meinen Code ändern?
noize
Ihre Annahme ist falsch; Sie sollten Ihren Code ändern. Sehen Sie die Logik wie im obigen Kommentar erklärt?
Lui
Code behoben. Ich habe verschiedene Arten von Kombinationen geprüft und es sieht für mich so aus, als würde der Weg immer kürzer sein.
noize
Dies scheint nur abwärts zu zählen, daher dauert es länger als nötig für Kombinationen mit hohen Zahlen (z. B. 18 Züge für 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]]#[]

Dies funktioniert, indem wiederholt eine neue Liste von Kombinationen erstellt wird, indem jede mögliche Runde auf jede bereits erreichte Kombination angewendet wird, bis eine von ihnen die richtige Kombination ist. Duplikate werden bei jeder Iteration aus der Liste entfernt, damit die Speichernutzung nicht exponentiell zunimmt.

Als Brute-Force-Lösung ist dies sehr ineffizient und kann mehrere Minuten dauern.

Ich habe nicht viel Erfahrung mit Haskell, also könnte man wahrscheinlich etwas besser machen.

faubi
quelle
Scheint eine solide Basis für Ihre Herangehensweise zu sein. Ich habe weder Erfahrung mit Haskell noch (das weiß ich) irgendwelche Mittel, um es zu kompilieren / auszuführen. Ein schnelles googeln gibt mir auch nirgendwo, wo ich es ausprobieren kann. Können Sie einen Link angeben, mit dem ich es versuchen kann? Vielen Dank.
Lui
@Lui Es kann mit dem Glasgow Haskell Compiler kompiliert werden , aber abgesehen vom Herunterladen und Verwenden kenne ich keine Möglichkeit, es auszuführen.
Faubi