# Verify a Tower of Hanoi solution

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

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.

• Is it also okay if the 2nd input can be represented using your method, but using numbers instead of letters (i.e. A=1, B=2, C=3, etc.)? Jul 27, 2016 at 20:28
• May I zero index the inputs? Jul 27, 2016 at 20:33
• Is it okay if an error is thrown when a disk is taken from an empty or nonexistent rod? Jul 27, 2016 at 20:44
• Can we assume that there won't be non-moves like A->A? Jul 28, 2016 at 9:32
• @Kobi you have to check for moving discs to nonexistant rods. so of course yes, it's a D Jul 29, 2016 at 7:00

## Retina, 167165157150 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. # 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!  • What does System.out.println(Arrays.toString(s)) do? Jul 27, 2016 at 23:05 • It will pretty print the stacks. Like so [[2,1,0],[][]] Jul 27, 2016 at 23:06 • Whoops @Frozn that was a debug feature removing now Jul 27, 2016 at 23:06 • I know, just wondering why it's there :) You can also replace && with &. Jul 27, 2016 at 23:08 • @Frozn I can not replace that sadly because I was relying on short circuit behavior to avoid trying to peek at an empty stack. Thanks for the 39 byte reduction Jul 27, 2016 at 23:14 # Python 2, 186167158135127115110 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! • The check that each pile is sorted seems too complicated. Can't you just check that the moved disk is larger than the top disk of the pile it's moved onto? – xnor Jul 28, 2016 at 18:42 • @xnor Thanks, that should work. Adding it now. Jul 28, 2016 at 18:54 # 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). • Wow, thats impressive Aug 21, 2016 at 15:59 # Python 2.7, 173158138130127 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. • two things: variable Y is never defined in your code (I think that should be J) and U[J]+=[Y,[U[K].pop()]][U[J]<[1]or U[K]<U[J]] is shorter by 3 characters that the stmt1 if cond else stmt2 Jul 28, 2016 at 13:25 • @jermenkoo Well, I use that Y variable like that is to raise the NameError whenever the 2nd condition is not met. If I were to change Y to J, then the NameError would not be raised. For this reason, I also cannot do U[J]+=[Y,[U[K].pop()]][U[J]<[1]or U[K]<U[J]] because this would raise a NameError all the time, not just when the 2nd condition is not met. Jul 28, 2016 at 18:02 • alright, thanks for your explanation! Jul 29, 2016 at 16:30 # VBA, 234217213 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  # 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.

# 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>`