Zamek rowerowy kombinowany

46

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. Zamek rowerowy kombinowany

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.

Lui
źródło
18
Witamy w PPCG; bardzo miłe pierwsze wyzwanie!
Klamka
4
To wygląda dla mnie solidnie! Witamy w PPCG!
Mego
1
Niezłe wyzwanie. Czy mogę zapytać, jaka powinna być wydajność dla spraw: 7478 i 3737?
noisyass2
1
@ noisyass2 Thanks; Odpowiedź flawr daje następujące brzmienie: 7478 8588 9698 0708 0808 0908 0008 0009 0000 i 3737 2627 1517 0407 0307 0207 0107 0007 0008 0009 0000 Patrząc tylko na 3737, ma to sens: patrząc tylko na pierwsze 3 cyfry: jeśli przesunę wszystkie pierwsze trzy jednocześnie wymagają 3 ruchów dla cyfr 1 i 3, a następnie kolejnych 4 ruchów dla cyfry 2, czyli w sumie siedem. Podczas gdy poruszam się indywidualnie, każdy wykonuje 3 ruchy, a więc 9 ruchów.
Lui,
1
Zastanawiam się, czy tytuł „Blokada kombinacji” (lub „Blokada roweru”) może przyciągnąć więcej widzów.
DavidC

Odpowiedzi:

10

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,''])
wada
źródło
Miły! Będąc głównie użytkownikiem Matlaba, zastanawiałem się, jak dobrze sobie z tym poradzi.
Lui,
1
Do 6444wpisania kod podaje 6444 7554 8664 9774 0884 0994 0004 0003 0002 0001 0000, podczas gdy uważam, że odpowiedź brzmi 6444 6333 6222 6111 6000 7000 8000 9000 0000. Moja odpowiedź to 8 kroków, twój to 10. Nie widzę problem i wydaje się, że występuje zarówno w wersji golfowej, jak i nie golfowej. Zostało to naprawione w twojej ostatniej edycji.
Lui
1
Właśnie poprawiłem mały błąd w kodzie. W sostatnim rzędzie powinno być [0,1,1,1]. Następnie otrzymujesz 8-krokowe rozwiązanie! Przepraszam za niedogodności =)
błąd
1
@Lui Istnieje czat matlab / oktawę , między innymi jest to rodzaj bazy dla języka golfowego MATL pochodzącego z Matlab.
flawr
1
dla 4826 znalazłem rozwiązanie 11 ruchów: 4826 3716 2606 1506 0406 0306 0206 0106 0007 0008 0009 0000
noisyass2
4

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.

hałasować
źródło
Nie przyjrzałem się twojej odpowiedzi dogłębnie, ale staram się podążać za twoją logiką z pierwszego akapitu. Który przykład konkretnie masz na myśli? A twoim przykładem przejścia od 1234do nie0224 jest jeden ruch. Chodzi o to, że używając tylko dwóch palców, mogę uchwycić do trzech kolejnych pierścieni jednym uchwytem.
Lui,
Chodzi mi o to, że jeśli możesz przesunąć 3 kolejne pierścienie, rozsądnie jest pomyśleć, że możesz także przesunąć pierwszy i trzeci, unikając drugiego. Czy powinienem zmienić kod?
noize
Twoje założenie jest błędne; powinieneś zmienić swój kod. Czy widzisz logikę wyjaśnioną w powyższym komentarzu?
Lui
Naprawiono kod. Sprawdziłem kilka różnych rodzajów kombinacji i wydaje mi się, że zawsze idzie to krócej.
noize
Wydaje się, że liczy się to tylko w dół, więc zajmuje więcej czasu niż jest to konieczne w przypadku kombinacji z dużymi liczbami (np. 18 ruchów dla 9999)
faubi 13.01.2016
2

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.

faubi
źródło
Wydaje się, że jest to solidna podstawa dla twojego podejścia. Nie mam doświadczenia z Haskellem ani (o których wiem) żadnych środków jego kompilacji / uruchamiania. Szybkie google nie daje mi nigdzie możliwości wypróbowania. Czy możesz podać link, który pozwala mi spróbować? Dzięki.
Lui
@Lui Można go skompilować za pomocą kompilatora Glasgow Haskell , ale poza pobraniem i używaniem nie wiem, jak go uruchomić.
faubi