Verify a Tower of Hanoi solution

Question

If you don't know what the Tower of Hanoi is, I'll explain it briefly: There are three rods and some discs each of which has a different size. In the beginning all discs are on the first tower, in sorted order: The biggest one is at the bottom, the smallest at the top. The goal is to bring all the discs over to the third rod. Sounds easy? Here's the catch: You can't place a disc on top of a disc that is smaller than the other disc; you can only hold one disc in your hand at a time to move them to another rod and you can only place the disc on rods, not on the table, you sneaky bastard.

ascii example solution:

  A      B      C
  |      |      |      
 _|_     |      |      
__|__    |      |


  A      B      C
  |      |      |      
  |      |      |      
__|__   _|_     |


  A      B      C
  |      |      |      
  |      |      |      
  |     _|_   __|__


  A      B      C
  |      |      |      
  |      |     _|_     
  |      |    __|__      

Challenge

There are three rods called A,B and C. (You can also call them 1,2 and 3 respectivly if that helps) In the beginning all n discs are on rod A(1).

Your challenge is to verify a solution for the tower of hanoi. You'll need to make sure that:

1. In the end all n discs are on rod C(3).
2. For any given disc at any given state there is no smaller disc below it.
3. No obvious errors like trying to take discs from an empty rod or moving discs to nonexistant rods.

(the solution does not have to be optimal.)

Input

Your program will receive two inputs:

1. The number of discs n (an integer)

2. The moves which are taken, which will consist of a set of tuples of: (tower to take the currently uppermost disc from),(tower to take this disc to) where each tuple refers to a move. You can choose how they are represented. For example something like the following ways of representing the solution for n=2 which I've drawn in ascii above. (I'll use the first one in the test cases, because it's easy on the eyes):

   "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]

Output

• Truthy, if the conditions that can be found under "challenge" hold.

• Falsy, if they don't.

Test cases:

True:

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"

False:

3rd one suggested by @MartinEnder, 7th by @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"

This is code-golf, shortest solution wins. Standard rules and loopholes apply. No batteries included.

Answer 1

Retina, 167 165 157 150 123 bytes

This totally looks like a challenge that should be solved with a single regex... (despite the header saying "Retina", this is just a vanilla .NET regex, matching valid inputs).

^(?=\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

Input format is the list of instructions of the form AB, followed by n in unary using the digit 1. There are no separators. Output is 1 for valid and 0 for invalid.

Try it online! (The first two characters enable a linefeed-separated test suite.)

Alternative solution, same byte count:

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

This can possibly be shortened by using 1, 11 and 111 instead of A, B and C but I'll have to look into that later. It might also be shorter to split the program into several stages, but where's the challenge in that? ;)

Explanation

This solution makes heavy use of .NET's balancing groups. For a full explanation see my post on Stack Overflow, but the gist is that capturing groups in .NET are stacks, where each new capture pushes another substring and where it's also possible to pop from such a stack again. This lets you count various quantities in a string. In this case it lets us implement the three rods directly as three different capturing groups where each disc is represented by a capture.

To move discs around between rods we make use of a weird quirk of the (?<A-B>...) syntax. Normally, this pops a capture from stack B and pushes onto stack A the string between that popped capture and the beginning of this group. So (?<A>a).(?<B-A>c) matched against abc would leave A empty and B with b (as opposed to c). However, due to .NET variable-length lookbehinds it's possible for the captures of (?<A>...) and (?<B-A>...) to overlap. For whatever reason, if that's the case, the intersection of the two groups is pushed onto B. I've detailed this behaviour in the "advanced section" on balancing groups in this answer.

On to the regex. Rods A, B and C correspond to groups 3, 4 and 5 in the regex. Let's start by initialising rod 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)+
)

So e.g. if the input ends with 111, then group 3/rod A will now hold the list of captures [111, 11, 1] (the top being on the right).

The next bit of the code has the following structure:

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

Each iteration of this loop processes one instruction. The first alternation pulls a disc from the given rod (onto a temporary group), the second alternation puts that that disc onto the other given rod. We'll see in a moment how this works and how we ensure that the move is valid.

First, taking a disc off the source rod:

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

This uses the weird group-intersection behaviour I've described above. Note that group 3, 4 and 5 will always hold substrings of 1s at the end of the string whose length corresponds to the disc's size. We now use (?<1-N>.+) to pop the top disc off stack N and push the intersection of this substring with the match .+ onto stack 1. Since .+ always necessarily covers the entire capture popped off N, we know that this simply moves the capture.

Next, we put this disc from stack 1 onto the stack corresponding to the second rod:

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

Note that we don't have to clean up stack 1, we can just leave the disc there, since we'll put a new one on top before using the stack again. That means we can avoid the (?<A-B>...) syntax and simply copy the string over with (\1). To ensure that the move is valid we use the negative lookahead (?!\N). This ensures that, from the position where we want to match the current disc, it's impossible to match the disc already on stack N. This can only happen if either a) \N will never match because the stack is completely empty or b)the disc on top of stackNis larger than the one we're trying to match with\1`.

Finally, all that's left is ensuring that a) we've matched all instructions and b) rods A and B are empty, so that all discs have been moved onto C.

(?!\3|\4)1

We simply check that neither \3 nor \4 can match (which is only the case if both are empty, because any actual disc would match) and that we can then match a 1 so that we haven't omitted any instructions.

Answer 2

Java "only" 311 272 263 261 260 259 256 bytes

Saved 39 countless bytes due to @Frozn noticing an older debug feature as well as some clever golfing tricks.

Golfed version

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;}

ungolfed with explanation and pretty printed stacks at each step

/*
 * 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!");
    }

}

The ungolfed version has a feature where it will print out what the stacks look like at each step like so...

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

Answer 3

Python 2, 186 167 158 135 127 115 110 102 bytes

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]:_

Takes input on STDIN in the following format:

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

That is, a Python tuple of the number of discs and a Python list of tuples of (from_rod,to_rod). As in Python, the surrounding parentheses are optional. Rods are zero-indexed.

For example, this test case:

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

would be given as:

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

If the solution is valid, outputs nothing and exits with an exit code of 0. If it is invalid, throws an exception and exits with an exit code of 1. Throws an IndexError if moving to a nonexistant rod or trying to take a disc off a rod that has no discs on it, a ZeroDivisionError if a disc is placed on top of a smaller disc, or a NameError if there are discs left on the first or second rods at the end.

Saved 13 bytes thanks to @KarlKastor!

Saved 8 bytes thanks to @xnor!

Answer 4

Retina, 84 80 Bytes

^{-5 bytes thanks to Martin Ender}

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

Try it online! (plus 5 bytes for line-by-line tests)

The code simulates a full game.

• Input is given as ACABCBACBABCAC~~~.
  ~~~ means three discs.
• First four lines convert the input to the game format: ACABCBACBABCAC ~~~ ~~ ~ABC.
  In the beginning the A rod has all 3 discs, and B and C rods are empty.
• Next we have a loop of two steps:
  • Take the first letter in the line, which indicates the next source rod. Find this rod, and take the last disc on in. Remove the letter and move the disc to the stark (pick it up).
    In out example, after the first step, the text will look like: ~CABCBACBABCAC ~~~ ~~ABC.
  • In the second stage we find the target rod, and move the disc there. We validate the rod is empty, or has a bigger disc at the top: ABCBACBABCAC ~~~ ~~AB ~C.
• Finally we confirm the A and B rods are empty - this means all discs are in C (there's an extra space at the last line).

Answer 5

Python 2.7, 173 158 138 130 127 123 bytes:

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)

Takes input through the stdin in the format (<Number of Discs>,<Moves>) where <Moves> is given as an array containing tuples corresponding to each move, which each contain a pair of comma separated integers. For instance, the test case:

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

given in the post would be given as:

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

to my program. Outputs an IndexError if the 3rd condition isn't met, a NameError if the 2nd condition isn't met, and False if the 1st condition isn't met. Otherwise outputs True.

Answer 6

VBA, 234 217 213 196 bytes

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

Input format for moves is a string with an even number of digits (012). Invocation is in spreadsheet, =H([number of discs], [move string])

The array A holds the rod position of the various discs. A move is simply updating the first occurrence of the "From" rod number into the "To" rod number. If you encounter a "To" rod disc first, or no "From" rod disc, it's an invalid move. The total "rod value" of A is held in L, which needs to end at 2N. Errors are accumulated as a negative count in E.

In common with other solutions, "moving" a disc from a tower to the same tower is not forbidden. I could forbid it for another 6 bytes.

Results

Function result in first column (the last n=3 case is my addition using an extra rod).

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

Answer 7

php, 141 bytes

<?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;

Command line script, takes input as the height then a series of array indexes (0 indexed) e.g. 1 0 2 or 2 0 1 0 2 1 2 for the 1 or 2 height shortest test cases.
Echos 1 on true cases and nothing on false ones.
Gives 2 notices and 1 warning so needs to be run in an environment that silences those.

Answer 8

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]

Input format: function with 2 arguments

• arg 1, numeric, number of rings
• arg 2, array of strings, each string 2 characters '0','1','2'

Output: return 1 if ok, 0 if invalid, exception if nonexisting rod

Less golfed and explained

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
)

Test Note: the first row of the Test function is needed to convert the input format given in the question to the input expected by my function

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>