CJam, 33 32 20 19 17 bytes
Revised version, with massive support from @Sp3000 and @MartinBüttner:
qN/_z]{:e`z,3<}/|
Try it online
Contributions
- @Sp3000 suggested a critical simplification to my original algorithm.
- @MartinBüttner applied his mad golfing skills to the revised approach, which almost certainly resulted in shorter code than I would have come up with even after considering the simplification.
Algorithm and Proof
The following explains the criteria for the puzzle sliding apart horizontally. The vertical case can be determined by looking at columns instead of rows, or transposing the character matrix and looking at the rows again.
I'll use the term "stretch" for a maximum sequence of the same letters. For example, the following rows have 1, 2, and 3 stretches respectively:
AAAAAAAA
BBBAAAAA
AABBBAAA
I'll also use the term "interlocked" for a row/puzzle that cannot slide apart.
The key observation is that the puzzle can slide apart if and only if all rows have at most 2 stretches. Or reversed, it is interlocked if and only if there is any row with more than 2 stretches.
The following might not qualify as a strict mathematical proof, but I believe that it makes for a convincing explanation why this has to be the case.
It is easy to see that the puzzle is interlocked if it has rows of more than 2 stretches. Looking at a row with 3 stretches:
BBBAAB
it is clear that it prevents the puzzle from sliding apart because the A stretch is locked between the B stretches. This means that the row is interlocked, which in turn makes the whole puzzle interlocked.
The opposite direction of the proof is not quite as obvious. We need to show that there are no interlocked puzzles where all rows have only 1 or 2 stretches. Starting with a couple of observations:
- Rows with only 1 stretch do not contribute to a puzzle being interlocked, since they can slide in either direction without any collisions.
- If all rows with 2 stretches have the same order of
A and B, the puzzle is clearly not interlocked. In this case, all A cells are left of all B cells, or vice versa, and there are no collisions when sliding the two pieces apart.
The only tricky case would be puzzles where we have rows with 2 stretches of different order. I'm going to show that such puzzles do not exist under the given specifications. To show this, let's look at a partial puzzle that does have this configuration, where . are wildcards:
.......
AAABBBB
.......
BBAAAAA
.......
Now, the specification says that both the A and B cells are simply connected in all valid puzzles. To make the A cells connected in the partial puzzle above, we have two options:
We loop around one of the stretches of B, for example:
..AAAAAA
AAABBBBA
.......A
BBAAAAAA
........
To do this, we unavoidably extend one of the rows to have 3 stretches, so this will never give us a valid puzzle where all rows have at most 2 stretches.
We connect them on a direct path:
.......
AAABBBB
..A....
BBAAAAA
.......
The A cells are now simply connected, and there are still no rows with more than 2 stretches. However, the B cells also need to be simply connected. The direct path is now blocked by the connected A cells, and the only way to connect the B cells is to loop around one of the stretches of A cells. This leads back to case 1, where we can't do that without creating rows of 3 stretches.
To count the stretches, the implementation uses the CJam RLE operator.
Explanation of Code
qN/ Get input and split at newlines.
_z Make a transposed copy.
] Wrap the original and transposed puzzle in an array so that we can
loop over the two.
{ Start of loop over original and transposed puzzle.
:e` Apply RLE to all rows.
z, Transpose the matrix with the RLE rows, and take the element count of the
result. Or in other words, take the column count. This will be the length
of the longest row after RLE.
3< Check the length for less than 3.
}/ End of loop over original and transposed puzzle.
| Or the results of the two.
