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:


In the end all n discs are on rod C(3).
For any given disc at any given state there is no smaller disc below it.
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:


The number of discs n (an integer)
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-&gt;C"

n=1, "A-&gt;B ; B-&gt;C"

n=2, "A-&gt;B ; A-&gt;C ; B-&gt;C"

n=2, "A-&gt;C ; C-&gt;B ; A-&gt;C ; B-&gt;C"

n=2, "A-&gt;C ; A-&gt;B ; C-&gt;B ; B-&gt;A ; B-&gt;C ; A-&gt;C"

n=3, "A-&gt;C ; A-&gt;B ; C-&gt;B ; A-&gt;C ; B-&gt;A ; B-&gt;C ; A-&gt;C"

n=4, "A-&gt;B ; A-&gt;C ; B-&gt;C ; A-&gt;B ; C-&gt;A ; C-&gt;B ; A-&gt;B ; A-&gt;C ; B-&gt;C ; B-&gt;A ; C-&gt;A ; B-&gt;C ; A-&gt;B ; A-&gt;C ; B-&gt;C"


False:

3rd one suggested by @MartinEnder, 7th by @Joffan

n=1, "A-&gt;B"

n=1, "C-&gt;A"

n=2, "A-&gt;C ; A-&gt;B ; C-&gt;B ; A-&gt;C ; B-&gt;A ; B-&gt;C ; A-&gt;C"

n=2, "A-&gt;B ; A-&gt;C ; C-&gt;B"

n=2, "A-&gt;C ; A-&gt;B ; C-&gt;B ; B-&gt;A"

n=2, "A-&gt;C ; A-&gt;C"

n=3, "A-&gt;B ; A-&gt;D; A-&gt;C ; D-&gt;C ; A-&gt;C"

n=3, "A-&gt;C ; A-&gt;C ; A-&gt;B ; C-&gt;B ; A-&gt;C ; B-&gt;A ; B-&gt;C ; A-&gt;C"

n=3, "A-&gt;C ; A-&gt;B ; C-&gt;B ; A-&gt;B ; B-&gt;C ; B-&gt;A ; B-&gt;C ; A-&gt;C"

n=3, "A-&gt;C ; A-&gt;B ; C-&gt;B ; A-&gt;C ; B-&gt;A ; B-&gt;C ; C-&gt;B"

n=4, "A-&gt;B ; A-&gt;C ; B-&gt;C ; A-&gt;B ; C-&gt;A ; C-&gt;B ; A-&gt;B ; A-&gt;C ; B-&gt;C ; B-&gt;A ; C-&gt;A ; B-&gt;C ; A-&gt;B ; A-&gt;C"

n=4, "A-&gt;B ; A-&gt;B ; A-&gt;B ; A-&gt;C ; B-&gt;C ; B-&gt;C ; B-&gt;C"


This is code-golf, shortest solution wins. Standard rules and loopholes apply. No batteries included.
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*((?=(?&lt;3&gt;1+))1)+)((?=A(?&lt;1-3&gt;.+)|B(?&lt;1-4&gt;.+)|C(?&lt;1-5&gt;.+)).(?=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*((?=(?&lt;3&gt;1+))1)+)((?=A(?&lt;1-3&gt;.+)|B(?&lt;1-4&gt;.+)|C(?&lt;1-5&gt;.+)).(?=A.*(?!\3)(\1)|B.*(?!\4)(\1)|C.*(?!\5)(\1)).)+(?&lt;-5&gt;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 (?&lt;A-B&gt;...) 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 (?&lt;A&gt;a).(?&lt;B-A&gt;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 (?&lt;A&gt;...) and (?&lt;B-A&gt;...) 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...
    (?=(?&lt;3&gt;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(?&lt;1-3&gt;.+)
|
  B(?&lt;1-4&gt;.+)
|
  C(?&lt;1-5&gt;.+)
)


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 (?&lt;1-N&gt;.+) 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 (?&lt;A-B&gt;...) 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.