Verify a Tower of Hanoi solution
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.
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!
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!