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 5737
do 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 5737
do 6837
lub 5626
. Przejście od 5737
do 6838
nie 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.
Odpowiedzi:
Matlab,
412327 bajtówGra w golfa (dzięki @AndrasDeak za grę w golfa
s
!):Kody te wykorzystują dynamiczne programowanie do znajdowania najkrótszej „ścieżki” od podanego numeru do
0000
korzystania 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:
Pełny kod (w tym niektóre komentarze):
źródło
6444
wpisania 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.s
ostatnim rzędzie powinno być[0,1,1,1]
. Następnie otrzymujesz 8-krokowe rozwiązanie! Przepraszam za niedogodności =)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, od1234
do0224
.To jest moje rozwiązanie wsadowe: 236 bajtów.Edycja: poprawione rozwiązanie
Nowe rozwiązanie (naprawione zgodnie z komentarzami) ma 288 bajtów.
źródło
1234
do 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.Haskell - 310 bajtów
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.
źródło