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:

1. Na koniec wszystkie n tarcz znajduje się na pręcie C (3).
2. Dla dowolnego dysku w dowolnym stanie nie ma pod nim mniejszego dysku.
3. Ż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:

1. Liczba dysków n (liczba całkowita)

2. 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.

Retina , 84 80 bajtów

^{-5 bajtów dzięki Martinowi Enderowi}

~
 ~$'
$
ABC
{`^(.)(.*)( ~+)\1
$3$2$1
}`^(\W+)(\w)(.*)(?<=\1~+|\w)\2
$3$1$2
^AB 

Wypróbuj online! (plus 5 bajtów dla testów linia po linii)

Kod symuluje pełną grę.

• Dane wejściowe są podane jako ACABCBACBABCAC~~~.
  ~~~oznacza trzy dyski.
• Pierwsze cztery linie konwertować dane wejściowe do formatu gra: ACABCBACBABCAC ~~~ ~~ ~ABC.
  Na początku pręt A ma wszystkie 3 dyski, a pręty B i C są puste.
• Następnie mamy pętlę dwóch kroków:
  • Weź pierwszą literę w linii, która wskazuje następną źródłową wędkę. Znajdź ten pręt i weź ostatnią płytę. Wyjmij literę i przenieś płytę na surowy (podnieś).
    Na zewnątrz przykład, po pierwszym etapie, tekst będzie wyglądać następująco: ~CABCBACBABCAC ~~~ ~~ABC.
  • W drugim etapie znajdujemy docelowy pręt i tam przesuwamy dysk. Możemy potwierdzić pręt jest pusta lub ma większy dysk na górze: ABCBACBABCAC ~~~ ~~AB ~C.
• Na koniec potwierdzamy, że pręty A i B są puste - oznacza to, że wszystkie dyski są w C (w ostatnim wierszu jest dodatkowe miejsce).

Siatkówka , 167 165 157 150 123 bajtów

To 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).

^(?=\D*((?=(?<3>1+))1)+)((?=A(?<1-3>.+)|B(?<1-4>.+)|C(?<1-5>.+)).(?=A.*(?!\3)(\1)|B.*(?!\4)(\1)|C.*(?!\5)(\1)).)+(?!\3|\4)1

Format wejściowy to lista instrukcji w formularzu AB, po których następuje nunary przy użyciu cyfry 1. Nie ma separatorów. Dane wyjściowe są 1ważne i 0nieprawidłowe.

Wypróbuj online! (Pierwsze dwa znaki włączają pakiet testowy oddzielony od linii).

Alternatywne rozwiązanie, ta sama liczba bajtów:

^(?=\D*((?=(?<3>1+))1)+)((?=A(?<1-3>.+)|B(?<1-4>.+)|C(?<1-5>.+)).(?=A.*(?!\3)(\1)|B.*(?!\4)(\1)|C.*(?!\5)(\1)).)+(?<-5>1)+$

To może być ewentualnie skrócić za pomocą 1, 11i 111zamiast A, Ba Cjednak 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. Zwykle Bpowoduje to wyskakiwanie przechwytywania ze stosu i wypycha na stos Aciąg między tym przechwyconym przechwyceniem a początkiem tej grupy. Tak (?<A>a).(?<B-A>c)dobrane przeciw abcpozostawiłyby Apuste i Bz b(w przeciwieństwie do c). 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 grupy B. 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, Bi Codpowiadają grupom 3, 4oraz 5w regex. Zacznijmy od inicjalizacji pręta A:

^                 # Ensure that we start at the beginning of the input.
(?=               # Lookahead so that we don't actually move the cursor.
  \D*             # Skip all the instructions by matching non-digit characters.
  (               # For each 1 at the end of the input...
    (?=(?<3>1+))  # ...push the remainder of the string (including that 1)
                  # onto stack 3.
  1)+
)

Na przykład, jeśli wejście kończy się na 111, grupa 3 / pręt Abę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ę:

(
  (?=A...|B...|C...).
  (?=A...|B...|C...).
)+

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:

(?=
  A(?<1-3>.+)
|
  B(?<1-4>.+)
|
  C(?<1-5>.+)
)

Wykorzystuje to dziwne zachowanie grupowe, które opisałem powyżej. Należy pamiętać, że grupy 3, 4i 5zawsze będzie trzymać podciągi z 1S 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 stosu Ni wciskania przecięcia tego podciągu z zapałką .+na stos 1. Ponieważ .+zawsze koniecznie obejmuje całe zdejmowane przechwytywanie N, wiemy, że to po prostu przenosi przechwytywanie.

Następnie kładziemy ten dysk ze stosu 1na stos odpowiadający drugiemu prętowi:

(?=
  A.*(?!\3)(\1)
|
  B.*(?!\4)(\1)
|
  C.*(?!\5)(\1)
)

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 stosie N. Może się to zdarzyć tylko wtedy, gdy albo a) \Nnigdy nie będzie pasować, ponieważ stos jest całkowicie pusty lub b) the disc on top of stackN is 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 Ai Bsą puste, aby wszystkie dyski zostały przeniesione C.

(?!\3|\4)1

My po prostu sprawdzić, ani \3też nie \4moż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 dopasowywania 1tak, że nie pominięto żadnych instrukcji.

Java „tylko” 311 272 263 261 260 259 256 bajtów

Zaoszczędzono 39 niezliczonych bajtów, ponieważ @Frozn zauważył starszą funkcję debugowania, a także kilka sprytnych sztuczek golfowych.

Wersja golfowa

int i(int n,int[]m){int j=0,k=0,i=n;Stack<Integer>t,s[]=new Stack[3];for(;j<3;)s[j++]=new Stack();for(;i-->0;)s[0].push(i);for(;k<m.length;k+=2)if((t=s[m[k+1]]).size()>0&&s[m[k]].peek()>t.peek())return 0;else t.push(s[m[k]].pop());return s[2].size()<n?0:1;}

bez wytłumaczenia i ładnymi drukowanymi stosami na każdym kroku

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package codegolf;

/**
 *
 * @author rohan
 */
import java.util.Arrays;
import java.util.Stack;
public class CodeGolf {
    //golfed version
    int i(int n,int[]m){int j=0,k=0,i=n;Stack<Integer>[] s=new Stack[3];for(;j<3;j++)s[j]=new Stack();for(;i-->0;)s[0].push(i);for(;k<m.length;System.out.println(Arrays.toString(s)),k+=2)if(!s[m[k+1]].isEmpty()&&s[m[k]].peek()>s[m[k+1]].peek())return 0;else s[m[k+1]].push(s[m[k]].pop());return s[2].size()==n?1:0;}
    /** Ungolfed
        * 0 as falsy 1 as truthy
        * @param n the number of disks
        * @param m represents the zero indexed stacks in the form of [from,to,from,to]
        * @return 0 or 1 if the puzzle got solved, bad moves result in an exception
        */
    int h(int n, int[] m) {
        //declarations
        int j = 0, k = 0, i = n;
        //create the poles
        Stack<Integer>[] s = new Stack[3];
        for (; j < 3; j++) {
            s[j] = new Stack();
        }
        //set up the first tower using the "downto operator
        for (; i-- > 0;) {
            s[0].push(i);
        }
    //go through and perform all the moves
        for (; k < m.length; System.out.println(Arrays.toString(s)), k += 2) {
            if (!s[m[k + 1]].isEmpty() && s[m[k]].peek() > s[m[k + 1]].peek()) {
                return 0;//bad move
            } else {
                s[m[k + 1]].push(s[m[k]].pop());
            }
        }
        return s[2].size() == n ? 1 : 0;// check if all the disks are done
    }
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
    //test case
        System.out.println( new CodeGolf().h(3,new int[]{0,2,0,1,2,1,0,2,1,0,1,2,0,2})==1?"Good!":"Bad!");
    }

}

Wersja bez golfa ma funkcję, w której będzie drukować, jak wyglądają stosy na każdym kroku, tak ...

[[2, 1], [], [0]]
[[2], [1], [0]]
[[2], [1, 0], []]
[[], [1, 0], [2]]
[[0], [1], [2]]
[[0], [], [2, 1]]
[[], [], [2, 1, 0]]
Good!

Python 2, 186 167 158 135 127 115 110 102 bajtów

n,m=input()
x=[range(n),[],[]]
for a,b in m:p=x[a].pop();e=x[b];e and 1/(p>e[-1]);e+=p,
if x[0]+x[1]:_

Pobiera dane wejściowe STDIN w następującym formacie:

(1,[(0,1),(1,2)])

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:

n=2; "A->B ; A->C ; B->C"

byłby podany jako:

(2,[(0,1),(0,2),(1,2)])

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 IndexErrorprzenosi się do nieistniejącego pręta lub próbuje zdjąć dysk z pręt, który nie ma na nim tarcz, a ZeroDivisionErrorjeśli tarcza jest umieszczona na mniejszej tarczy, lub NameErrorjeś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!

Pyton 2,7, 173 158 138 130 127 123 bajtów:

r=range;a,b=input();U=[r(a,0,-1),[],[]]
for K,J in b:U[J]+=[U[K].pop()]if U[J]<[1]or U[K]<U[J]else Y
print U[-1]==r(a,0,-1)

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:

n=3, "A->C ; A->B ; C->B ; A->C ; B->A ; B->C ; A->C" 

podany w poście będzie podany jako:

(3,[(0,2),(0,1),(2,1),(0,2),(1,0),(1,2),(0,2)]) 

do mojego programu. Wyprowadza, IndexErrorjeśli trzeci warunek nie jest spełniony, a NameErrorjeśli drugi warunek nie jest spełniony, a Falsejeśli pierwszy warunek nie jest spełniony. W przeciwnym razie wyjścia True.

VBA, 234 217 213 196 bajtów

Function H(N,S)
ReDim A(N)
While P<Len(S)
P=P+2:F=1*Mid(S,P-1,1):T=1*Mid(S,P,1)
E=E+(T>2):L=L+T-F
For i=1 To N
If A(i)=F Then A(i)=T:Exit For
E=E+(A(i)=T)+(i=N)
Next
Wend
H=L+9*E=2*N
End Function

Format 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).

TRUE    1   02
TRUE    1   0112
TRUE    2   010212
TRUE    2   02210212
TRUE    2   020121101202
TRUE    3   02012102101202
TRUE    4   010212012021010212102012010212

FALSE   1   01
FALSE   1   20
FALSE   2   02012102101202
FALSE   2   010221
FALSE   2   02012110
FALSE   2   0202
FALSE   3   0202012102101202
FALSE   3   0201210112101202
FALSE   3   02012102101221
FALSE   3   0103023212
FALSE   4   0102120120210102121020120102
FALSE   4   01010102121212

php, 141 bajtów

<?php $a=$argv;for($t=[$f=range($a[++$i],1),[],[]];($r=array_pop($t[$a[++$i]]))&&$r<(end($t[$a[++$i]])?:$r+1);)$t[$a[$i]][]=$r;echo$t[2]==$f;

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.

JavaScript (ES6), 108

n=>s=>!s.some(([x,y])=>s[y][s[y].push(v=s[x].pop())-2]<v|!v,s=[[...Array(s=n)].map(_=>s--),[],[]])&s[2][n-1]

Format wejściowy: funkcja z 2 argumentami

• arg 1, numeryczny, liczba pierścieni
• arg 2, tablica ciągów, każdy ciąg 2 znaki „0”, „1”, „2”

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

n=>a=>(
  // rods status, rod 0 full with an array n..1, rod 1 & 2 empty arrays
  s = [ [...Array(t=n)].map(_=>t--), [], [] ],
  // for each step in solution, evaluate function and stop if returns true
  err = a.some( ([x,y]) => {
    v = s[x].pop(); // pull disc from source rod
    // exception is s[x] is not defined
    if (!v) return 1; // error source rod is empty
    l = s[y].push(v); // push disc on dest rod, get number of discs in l
    // exception is s[y] is not defined
    if(s[y][l-2] < v) return 1; // error if undelying disc is smaller
  }),
  err ? 0 // return 0 if invalid move
  : s[2][n-1]; // il all moves valid, ok if the rod 2 has all the discs
)

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ę

F=
n=>s=>!s.some(([x,y])=>s[y][s[y].push(v=s[x].pop())-2]<v|!v,s=[[...Array(s=n)].map(_=>s--),[],[]])&s[2][n-1]

Out=x=>O.textContent+=x+'\n'

Test=s=>s.split`\n`.map(r=>[+(r=r.match(/\d+|.->./g)).shift(),r.map(x=>(parseInt(x[0],36)-10)+''+(parseInt(x[3],36)-10))])
.forEach(([n,s],i)=>{
  var r
  try {
    r = F(+n)(s);
  } 
  catch (e) {
    r = 'Error invalid rod';
  }
  Out(++i+' n:'+n+' '+s+' -> '+r)
})

Out('OK')
Test(`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"`)

Out('\nFail')
Test( `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"`)

<pre id=O></pre>