Scenariusz

Po długim dniu pracy w biurze i przeglądaniu stackexchange.com , w końcu wychodzę za drzwi o 16:58, już zmęczony dniem. Ponieważ nadal jestem tylko stażystą, mój obecny środek transportu jest na rowerze. Podchodzę do mojego zaufanego Peugeota Reynoldsa 501 , ale zanim zdążę na niego odpłynąć, muszę go odblokować. Zamek jest standardowym czterocyfrowym zamkiem szyfrowym (0–9) przechodzącym przez ramę i przednie koło. Kiedy staram się nie zasnąć, podnoszę rękę, aby wejść do kombinacji.

Wyzwanie

Ponieważ moje palce są tak zmęczone, chcę przekręcić blokadę do właściwej kombinacji przy jak najmniejszej liczbie ruchów. Jeden ruch jest definiowany jako obrót o jedną pozycję (36 stopni), na przykład jeden ruch od 5737do 5738. Jestem jednak w stanie jednocześnie uchwycić dowolne trzy kolejne pierścienie i obrócić je jako jeden , co liczy się tylko jako jeden ruch. Na przykład istnieje również tylko jeden ruch od 5737do 6837lub 5626. Przejście od 5737do 6838nie jest jednym ruchem, ponieważ cyfry 1,2 i 4 przesunęły się w tym samym kierunku, ale niezależnie od cyfry 3.

Dlatego dla danej kombinacji widzę na blokadzie roweru (dowolna 4-cyfrowa liczba całkowita), jaka jest najmniejsza liczba ruchów, jaką mogę wykonać, aby ją odblokować, i tak, mogę obracać się w dowolnym kierunku w dowolnym momencie. Rozumiem przez to, że mogę obrócić niektóre cyfry w jednym kierunku, a inne cyfry w drugim kierunku: nie wszystkie moje ruchy będą wykonywane w kierunku przeciwnym do ruchu wskazówek zegara lub zgodnie z ruchem wskazówek zegara dla każdego odblokowania.

Ponieważ jestem leniwy, mój kod odblokowujący to 0000.

To jest golf golfowy Nie mogę się martwić pisaniem dużej ilości kodu, więc wygrywa najkrótszy program pod względem liczby bajtów.

Dane wejściowe pochodzą ze standardowego wejścia, a kod powinien wyświetlać kombinacje, które widzę na każdym kroku po każdym ruchu, w tym 0000 na końcu. Każde wyjście kombinacji powinno być oddzielone spacją / znakiem nowej linii / przecinkiem / kropką / znakiem ampersand.

Przykłady

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

Próbowałem zamieścić to na http://bicycles.stackexchange.com , ale nie podobało im się ...

Uwaga: Najpierw golf, więc wszystko, co jest zepsute / brakujące informacje, daj mi znać! Zrobiłem też wszystkie przykłady ręcznie, więc mogą istnieć rozwiązania wymagające mniej ruchów!

EDYCJA: Dla odpowiedzi, które mają wiele ścieżek rozwiązania z jednakową liczbą ruchów (praktycznie wszystkie z nich), nie ma preferowanego rozwiązania.

Matlab, 412 327 bajtów

Gra w golfa (dzięki @AndrasDeak za grę w golfa 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)

Kody te wykorzystują dynamiczne programowanie do znajdowania najkrótszej „ścieżki” od podanego numeru do 0000korzystania tylko z możliwych kroków. Wyzwanie to jest w zasadzie najkrótsza ścieżka (alternatywnie można by uznać kroki za grupę komutatywną). Trudność polegała jednak na skutecznym wdrożeniu. Podstawowymi strukturami są dwie tablice 10000 elementów, jedna do przechowywania liczby kroków, aby dostać się do tego indeksu, druga do przechowywania wskaźnika do poprzedniego „węzła” na naszym wykresie. Jednocześnie oblicza „ścieżki” do wszystkich innych możliwych liczb.

Przykłady:

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    

Pełny kod (w tym niektóre komentarze):

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

Partia - 288 bajtów

Nawet jeśli powiedziałeś, że muszą być następujące po sobie (pierścienie), zakładam logicznie (zgodnie z przykładem), że mogę pominąć środkowy, od 1234do 0224.

set / px =
ustaw a =% x: ~ 0,1% i ustaw b =% x: ~ 1,1% i ustaw c =% x: ~ 2,1% i ustaw d =% x: ~ 3,1%
: l
@echo% x% i jeśli% a% == 0 (jeśli% d% NEQ 0 zestaw / reklama = d-1) inaczej zestaw / aa = a-1
@ jeśli% b% NEQ 0 zestaw / ab = b-1
@ if% c% NEQ 0 set / ac = c-1
@ if% x% NEQ 0000 set x =% a %% b %% c %% d% & goto l

To jest moje rozwiązanie wsadowe: 236 bajtów.

Edycja: poprawione rozwiązanie

set / px =
ustaw a =% x: ~ 0,1% i ustaw b =% x: ~ 1,1% i ustaw c =% x: ~ 2,1% i ustaw d =% x: ~ 3,1%
: l
@echo% x% i zestaw k = 1 i jeśli% a% == 0 (jeśli% d% NEQ 0 zestaw / reklama = d-1 i zestaw k = 0) inaczej zestaw / aa = a-1 i zestaw k = 1
@ jeśli% b% NEQ 0, jeśli% k% == 1 zestaw / ab = b-1 i zestaw k = 0
@ jeśli% c% NEQ 0, jeśli% k% == 0 zestaw / ac = c-1
@ if% x% NEQ 0000 set x =% a %% b %% c %% d% & goto l

Nowe rozwiązanie (naprawione zgodnie z komentarzami) ma 288 bajtów.

Haskell - 310 bajtów

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

Działa to poprzez wielokrotne budowanie nowej listy kombinacji poprzez zastosowanie każdej możliwej tury do każdej już osiągniętej kombinacji, aż jedna z nich będzie odpowiednią kombinacją. Duplikaty są usuwane z listy przy każdej iteracji, aby zapobiec gwałtownemu wzrostowi zużycia pamięci.

Jako rozwiązanie brutalnej siły jest to bardzo nieefektywne i może potrwać kilka minut.

Nie mam dużego doświadczenia z Haskellem, więc pewnie coś można zrobić lepiej.