Can I Slide Apart The Puzzle? Write a program or function that takes in a rectangular grid of text where every cell is either an A or a B. All the A cells will form a simply-connected shape, i.e. they will all be orthogonally connected with no holes (diagonally neighboring letters do not count as connected). Likewise, all the B cells will form another simply-connected shape. The grid will always contain at least one A and at least one B.

Imagine the grid is actually two blocky-shaped pieces of thin plastic, represented by the A and B portions. If it were placed flat on a table, could the two pieces be slid apart while keeping both completely flat on the table?

Print or return a truthy value if the two A and B shapes could be separated like this by simply pulling them apart. If not, print or return a falsy value.

For example, the input

AAA
ABB
AAA


is truthy because the BB section can be slid to the right, separating it from the A's:

AAA
A    BB
AAA


However, the input

AAAA
ABBA
ABAA


is falsy because there's no way to slide the A and B portions apart without having them overlap.

The shortest code in bytes wins. If desired, you may use any two distict printable ASCII characters in place of A and B.

Truthy Examples (separated by empty lines)

BBB
BAA
BBB

BA

A
B

AB
AB

AAA
BBB

AAAAB
ABBBB

ABBA
ABBA
AAAA

AAAAAABBBBBBBBB
AABBBBBBBBBBBBB
AAAAAAAAAABBBBB
AABBBBBBBBBBBBB
AAAAAAAAAAAAAAB

AAAAAAAAAAAA
ABABABABABAB
BBBBBBBBBBBB

BAAAAABB
BBAAABBB
BBBABBBB
BBBABBBB
BBBABBBB
BBBBBBBB
BBBBBBBB

AAA
BAA
AAA


Falsy Examples

BBBB
BAAB
BABB

BBBB
BAAB
AABB

BBBBBBB
BBBBBAB
AAAAAAB
BBBBBBB

BAAA
BABA
BBBA
AABA
AAAA

AAAAAAA
ABBBBBA
AAAAABA
BBBBBBA

BAAAAABB
BBAAABBB
BBBABBBB
BBBABBBB
BBBAABBB
BBBBBBBB
BBBBBBBB

AAA
ABA
BBA
ABA
AAA
CJam, 33 32 20 19 17 bytes

Revised version, with massive support from @Sp3000 and @MartinBüttner:

qN/_z]{:e`z,3&lt;}/|


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&lt;      Check the length for less than 3.
}/      End of loop over original and transposed puzzle.
|       Or the results of the two.