Jeśli nie wiesz, czym jest Wieża Hanoi , wyjaśnię to krótko: Istnieją trzy pręty i niektóre dyski, z których każda ma inny rozmiar. Na początku wszystkie dyski znajdują się w pierwszej wieży w uporządkowanej kolejności: największa jest na dole, a najmniejsza na górze. Celem jest przeniesienie wszystkich dysków na trzeci pręt. Brzmi łatwo? Oto haczyk: Nie można umieścić płyty na płycie, która jest mniejsza niż druga płyta; możesz jednocześnie trzymać tylko jeden dysk w dłoni, aby przenieść go na inny pręt i możesz umieścić dysk tylko na prętach, a nie na stole, podstępny draniu.
przykładowe rozwiązanie ascii:
A B C
| | |
_|_ | |
__|__ | |
A B C
| | |
| | |
__|__ _|_ |
A B C
| | |
| | |
| _|_ __|__
A B C
| | |
| | _|_
| | __|__
Wyzwanie
Istnieją trzy pręty zwane A, B i C. (Można to również nazywać odpowiednio 1,2 i 3, jeśli to pomaga) Na początku wszystkie n tarcz są na pręcie A (1).
Twoim wyzwaniem jest zweryfikowanie rozwiązania dla wieży hanoi. Musisz upewnić się, że:
- Na koniec wszystkie n tarcz znajduje się na pręcie C (3).
- Dla dowolnego dysku w dowolnym stanie nie ma pod nim mniejszego dysku.
- Żadnych oczywistych błędów, takich jak próba przeniesienia dysków z pustego pręta lub przesunięcia dysków do nieistniejących prętów.
(rozwiązanie nie musi być optymalne).
Wkład
Twój program otrzyma dwa dane wejściowe:
- Liczba dysków n (liczba całkowita)
Wykonane ruchy, które będą składały się z zestawu krotek: (wieża, z której zabiera się obecnie najwyższy dysk), (wieża, aby zabrać ten dysk), gdzie każda krotka odnosi się do ruchu. Możesz wybrać sposób ich reprezentacji. Na przykład coś takiego jak następujące sposoby przedstawienia rozwiązania dla n = 2, które narysowałem powyżej w ascii. (Wykorzystam pierwszy z przypadków testowych, ponieważ jest łatwy dla oczu):
„A-> B; A-> C; B-> C”
[(„A”, „B”), („A”, „C”), („B”, „C”)]
[(1,2), (1,3), (2,3)]
„ABACBC”
[1,2,1,3,2,3]
Wydajność
Prawda, jeśli spełnione są warunki, które można znaleźć w „wyzwaniu”.
Falsy, jeśli nie.
Przypadki testowe:
Prawdziwe:
n=1, "A->C"
n=1, "A->B ; B->C"
n=2, "A->B ; A->C ; B->C"
n=2, "A->C ; C->B ; A->C ; B->C"
n=2, "A->C ; A->B ; C->B ; B->A ; B->C ; A->C"
n=3, "A->C ; A->B ; C->B ; A->C ; B->A ; B->C ; A->C"
n=4, "A->B ; A->C ; B->C ; A->B ; C->A ; C->B ; A->B ; A->C ; B->C ; B->A ; C->A ; B->C ; A->B ; A->C ; B->C"
Fałszywe:
Trzeci sugerowany przez @MartinEnder, 7-ty @Joffan
n=1, "A->B"
n=1, "C->A"
n=2, "A->C ; A->B ; C->B ; A->C ; B->A ; B->C ; A->C"
n=2, "A->B ; A->C ; C->B"
n=2, "A->C ; A->B ; C->B ; B->A"
n=2, "A->C ; A->C"
n=3, "A->B ; A->D; A->C ; D->C ; A->C"
n=3, "A->C ; A->C ; A->B ; C->B ; A->C ; B->A ; B->C ; A->C"
n=3, "A->C ; A->B ; C->B ; A->B ; B->C ; B->A ; B->C ; A->C"
n=3, "A->C ; A->B ; C->B ; A->C ; B->A ; B->C ; C->B"
n=4, "A->B ; A->C ; B->C ; A->B ; C->A ; C->B ; A->B ; A->C ; B->C ; B->A ; C->A ; B->C ; A->B ; A->C"
n=4, "A->B ; A->B ; A->B ; A->C ; B->C ; B->C ; B->C"
To jest golf golfowy , wygrywa najkrótsze rozwiązanie. Obowiązują standardowe zasady i luki. Brak baterii w zestawie.
A=1
,B=2
,C=3
, itd.)?A->A
?moving discs to nonexistant rods.
więc oczywiście tak, toD
Odpowiedzi:
Retina ,
8480 bajtów-5 bajtów dzięki Martinowi Enderowi
Wypróbuj online! (plus 5 bajtów dla testów linia po linii)
Kod symuluje pełną grę.
ACABCBACBABCAC~~~
.~~~
oznacza trzy dyski.ACABCBACBABCAC ~~~ ~~ ~ABC
.Na początku pręt A ma wszystkie 3 dyski, a pręty B i C są puste.
Na zewnątrz przykład, po pierwszym etapie, tekst będzie wyglądać następująco:
~CABCBACBABCAC ~~~ ~~ABC
.ABCBACBABCAC ~~~ ~~AB ~C
.źródło
Siatkówka ,
167165157150123 bajtówTo całkowicie wygląda na wyzwanie, które powinno zostać rozwiązane za pomocą jednego wyrażenia regularnego ... (pomimo nagłówka z napisem „Retina”, jest to po prostu waniliowy regex .NET, pasujący do poprawnych danych wejściowych).
Format wejściowy to lista instrukcji w formularzu
AB
, po których następujen
unary przy użyciu cyfry1
. Nie ma separatorów. Dane wyjściowe są1
ważne i0
nieprawidłowe.Wypróbuj online! (Pierwsze dwa znaki włączają pakiet testowy oddzielony od linii).
Alternatywne rozwiązanie, ta sama liczba bajtów:
To może być ewentualnie skrócić za pomocą
1
,11
i111
zamiastA
,B
aC
jednak będę musiał patrzeć na później. Podzielenie programu na kilka etapów może być również krótsze, ale w czym to wyzwanie? ;)Wyjaśnienie
To rozwiązanie intensywnie wykorzystuje grupy równoważące .NET. Aby uzyskać pełne wyjaśnienie, zobacz mój post na temat przepełnienia stosu , ale sedno polega na tym, że przechwytywanie grup w .NET to stosy, w których każde nowe przechwytywanie przesuwa kolejne podciągi i gdzie można również wyskoczyć z takiego stosu. Pozwala to zliczać różne ilości w ciągu. W tym przypadku pozwala nam to wdrożyć trzy pręty bezpośrednio jako trzy różne grupy przechwytywania, w których każdy dysk jest reprezentowany przez przechwytywanie.
Aby przenosić dyski między prętami, używamy dziwnego dziwactwa
(?<A-B>...)
składni. ZwykleB
powoduje to wyskakiwanie przechwytywania ze stosu i wypycha na stosA
ciąg między tym przechwyconym przechwyceniem a początkiem tej grupy. Tak(?<A>a).(?<B-A>c)
dobrane przeciwabc
pozostawiłybyA
puste iB
zb
(w przeciwieństwie doc
). Jednak ze względu na zmienną długość spojrzenia .NET możliwe jest przechwytywanie(?<A>...)
i(?<B-A>...)
nakładanie się. Z jakiegokolwiek powodu, jeśli tak jest, przecinają się dwie grupyB
. Szczegółowo opisałem to zachowanie w „sekcji zaawansowanej” na temat równoważenia grup w tej odpowiedzi .Przejdź do wyrażenia regularnego. Pręty
A
,B
iC
odpowiadają grupom3
,4
oraz5
w regex. Zacznijmy od inicjalizacji prętaA
:Na przykład, jeśli wejście kończy się na
111
, grupa 3 / prętA
będzie teraz przechowywał listę przechwyceń[111, 11, 1]
(górna część znajduje się po prawej stronie).Następny bit kodu ma następującą strukturę:
Każda iteracja tej pętli przetwarza jedną instrukcję. Pierwsza przemiana wyciąga dysk z danego pręta (na grupę tymczasową), druga przemiana umieszcza ten dysk na drugim pręcie. Za chwilę zobaczymy, jak to działa i jak upewnimy się, że ruch jest prawidłowy.
Najpierw zdejmij dysk z pręta źródłowego:
Wykorzystuje to dziwne zachowanie grupowe, które opisałem powyżej. Należy pamiętać, że grupy
3
,4
i5
zawsze będzie trzymać podciągi z1
S na końcu łańcucha, którego długość odpowiada wielkości płyty. Teraz używamy(?<1-N>.+)
do usuwania górnej płyty ze stosuN
i wciskania przecięcia tego podciągu z zapałką.+
na stos1
. Ponieważ.+
zawsze koniecznie obejmuje całe zdejmowane przechwytywanieN
, wiemy, że to po prostu przenosi przechwytywanie.Następnie kładziemy ten dysk ze stosu
1
na stos odpowiadający drugiemu prętowi:Pamiętaj, że nie musimy czyścić stosu
1
, możemy po prostu zostawić tam dysk, ponieważ przed ponownym użyciem stosu umieścimy nowy na wierzchu. Oznacza to, że możemy uniknąć(?<A-B>...)
składni i po prostu skopiować ciąg znaków(\1)
. Aby upewnić się, że ruch jest prawidłowy, używamy negatywnego spojrzenia w przyszłość(?!\N)
. Zapewnia to, że z miejsca, w którym chcemy dopasować bieżącą płytę, niemożliwe jest dopasowanie płyty znajdującej się już na stosieN
. Może się to zdarzyć tylko wtedy, gdy albo a)\N
nigdy nie będzie pasować, ponieważ stos jest całkowicie pusty lub b)the disc on top of stack
Nis larger than the one we're trying to match with
\ 1`.Na koniec pozostaje tylko upewnienie się, że a) dopasowaliśmy wszystkie instrukcje ib) pręty
A
iB
są puste, aby wszystkie dyski zostały przeniesioneC
.My po prostu sprawdzić, ani
\3
też nie\4
może się równać (który jest tylko w przypadku, gdy oba są puste, ponieważ każdy rzeczywisty dysk będzie dopasowywać) i że możemy następnie dopasowywania1
tak, że nie pominięto żadnych instrukcji.źródło
Java „tylko”
311 272 263 261 260 259256 bajtówZaoszczędzono
39niezliczonych bajtów, ponieważ @Frozn zauważył starszą funkcję debugowania, a także kilka sprytnych sztuczek golfowych.Wersja golfowa
bez wytłumaczenia i ładnymi drukowanymi stosami na każdym kroku
Wersja bez golfa ma funkcję, w której będzie drukować, jak wyglądają stosy na każdym kroku, tak ...
źródło
System.out.println(Arrays.toString(s))
zrobić?&&
z&
.Python 2,
186167158135127115110102 bajtówPobiera dane wejściowe STDIN w następującym formacie:
Oznacza to krotkę Pythona z liczbą dysków i listę krotek Pythona z
(from_rod,to_rod)
. Podobnie jak w Pythonie, otaczające nawiasy są opcjonalne. Pręty są zerowane.Na przykład ten przypadek testowy:
byłby podany jako:
Jeśli rozwiązanie jest poprawne, nic nie wyprowadza i wychodzi z kodem wyjścia 0. Jeśli jest nieważne, zgłasza wyjątek i wychodzi z kodem wyjścia 1. Wyrzuca i
IndexError
przenosi się do nieistniejącego pręta lub próbuje zdjąć dysk z pręt, który nie ma na nim tarcz, aZeroDivisionError
jeśli tarcza jest umieszczona na mniejszej tarczy, lubNameError
jeśli na końcu znajdują się dyski na pierwszym lub drugim pręcie.Zaoszczędź 13 bajtów dzięki @KarlKastor!
Zaoszczędź 8 bajtów dzięki @xnor!
źródło
Pyton 2,7,
173158138130127123 bajtów:Pobiera dane wejściowe przez standardowe wejście w formacie, w
(<Number of Discs>,<Moves>)
którym<Moves>
jest podane jako tablica zawierająca krotki odpowiadające każdemu ruchowi, z których każdy zawiera parę liczb całkowitych oddzielonych przecinkami. Na przykład przypadek testowy:podany w poście będzie podany jako:
do mojego programu. Wyprowadza,
IndexError
jeśli trzeci warunek nie jest spełniony, aNameError
jeśli drugi warunek nie jest spełniony, aFalse
jeśli pierwszy warunek nie jest spełniony. W przeciwnym razie wyjściaTrue
.źródło
Y
nigdy nie jest zdefiniowana w twoim kodzie (myślę, że powinna to być J) iU[J]+=[Y,[U[K].pop()]][U[J]<[1]or U[K]<U[J]]
jest krótsza o 3 znaki niżstmt1 if cond else stmt2
Y
zmiennej, aby podnosić zaNameError
każdym razem, gdy drugi warunek nie jest spełniony. Gdybym miał się zmienićY
naJ
, wtedyNameError
nie zostałbym podniesiony. Z tego powodu również nie mogę tego zrobić,U[J]+=[Y,[U[K].pop()]][U[J]<[1]or U[K]<U[J]]
ponieważ spowoduje to wzrostNameError
cały czas , nie tylko wtedy, gdy drugi warunek nie jest spełniony.VBA,
234217213196 bajtówFormat wejściowy dla ruchów jest ciągiem o parzystej liczbie cyfr (012). Wywołanie jest w arkuszu kalkulacyjnym, = H ([liczba dysków], [przenieś ciąg])
Układ A utrzymuje pozycję pręta różnych tarcz. Ruch polega po prostu na aktualizacji pierwszego wystąpienia numeru pręta „Od” na numer pręta „Do”. Jeśli najpierw napotkasz tarczę pręta „Do” lub nie masz tarczy pręta „Z”, jest to nieprawidłowy ruch. Całkowita „wartość pręta” A jest utrzymywana w L, która musi kończyć się na 2N. Błędy są kumulowane jako liczba ujemna w E.
Podobnie jak w przypadku innych rozwiązań, „przenoszenie” dysku z wieży do tej samej wieży nie jest zabronione. Mógłbym zabronić tego na kolejne 6 bajtów.
Wyniki
Wynik funkcji w pierwszej kolumnie (ostatni przypadek n = 3 to mój dodatek za pomocą dodatkowego pręta).
źródło
php, 141 bajtów
Skrypt wiersza poleceń pobiera dane wejściowe jako wysokość, a następnie szereg indeksów tablic (indeksowanych 0), np. 1 0 2 lub 2 0 1 0 2 1 2 dla najkrótszych przypadków testowych o wysokości 1 lub 2.
Echa 1 na prawdziwych przypadkach i nic na fałszywych.
Daje 2 powiadomienia i 1 ostrzeżenie, dlatego należy je uruchomić w środowisku, które je ucisza.
źródło
JavaScript (ES6), 108
Format wejściowy: funkcja z 2 argumentami
Wyjście: zwraca 1, jeśli jest w porządku, 0, jeśli jest nieprawidłowe, wyjątek, jeśli nieistniejący pręt
Mniej golfa i wyjaśnienia
Uwaga dotycząca testu : pierwszy wiersz funkcji Test jest potrzebny do przekonwertowania formatu wejściowego podanego w pytaniu na dane wejściowe oczekiwane przez moją funkcję
źródło