Can I Slide Apart The Puzzle?

Question

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

Answer 1

Snails, 14

o(t\B+~)+!(t\B

If the puzzle can be slid apart, it prints the area of the input. Otherwise, it prints 0.

It's a bit slow for the larger examples, as it takes time factorial in the area of the grid.

         ,, the program will print the number of starting cells matching this pattern
o        ,, pick a cardinal direction
(
    t    ,, teleport to any cell on the grid
    \B+  ,, match "B" 1 or more times, moving in the direction set by 'o'.
         ,, when a cell is matched, it gets slimed and can't be matched again.
    ~    ,, match an out-of-bounds cell
)+       ,, do parenthesized instructions 1 or more times
!(       ,, the following must not match:
    t\B  ,, teleport to some cell and match 'B'

Answer 2

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:

1. 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.

2. 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.

Answer 3

JavaScript (ES6), 108 107 98 91 82 bytes

a=>!(T=[],R=/AB+A|BA+B/).test([...a].map((c,i)=>T[i%-~a.search`
`]+=c))|!R.test(a)

Live demo. Tested in Firefox. Takes input as a newline-delimited string.

Edits:

• Saved 1 byte by changing \n to a literal newline.
• Saved 9 bytes by doing the RegExp test directly on the multi-line string instead of converting to an array.
• Eliminated another 9 bytes by using array comprehensions to split string, moving ! into g function and calling RegExp directly on array instead of using find.
• Continued the arthmetic sequence by saving another 9 bytes. Did a modulus on the index instead of splitting the array by newlines before taking the transpose.

How it works

Previous version:

a=>(T=[],a.split`
`.map(s=>s.split``.map((c,i)=>T[i]+=c)),!T.find(g=s=>/AB+A|BA+B/.test(s)))|!g(a)

1. Take the input a and split it by newlines into an array of strings.
2. Transpose a and store it in T. Use map to iterate over each element of a, split the string into a character array, and use map again to append the ith character in the line to the ith line of T. Since each element of T is uninitialized, it will end up looking something like "undefinedAAABBA", but this won't matter.
3. Create a RegExp based testing function g that matches the pattern /AB+A|BA+B/. If it matches, the pieces are locked in the given direction because then there are a set of Bs sandwiched between two or more As or vice-versa.
4. Use the testing function g to test all elements of the block a and its transpose T for a match using find. If both match, then the pieces are locked in both directions, so output a falsy value, otherwise a truthy one.

Answer 4

Javascript (ES6), 118

slidey=
// code
a=>!a.match(R=/AB+A|BA+B/)||!(a=a.split`
`.map(b=>b.split``))[0].map((_,c)=>a.map(d=>d[c])).some(e=>e.join``.match(R))

// IO
var S =document.getElementById('S');
S.onkeyup = _=> document.getElementById('P').innerText = slidey(S.value);

document.getElementById('P').innerText = slidey(S.value);

<textarea id='S'>BAAAAABB
BBAAABBB
BBBABBBB
BBBABBBB
BBBABBBB
BBBBBBBB
BBBBBBBB</textarea>
<p id='P'></p>

Explanation:

a=> !/* check string horizontally */ || !/* check string vertically by transposing it and
                                            running the same horizontal check */

a=> !a.match(R=/AB+A|BA+B/) || !/* ... */
// check for lines containing something like BAAAAAB or ABBBBBBBA
// this is the only way something can get blocked horizontally
// eg AAAAAAA
//    AAABAAA <<< note the B in the middle of As here
//    AAABBBB <<< blocked from being pulled out horizontally
//    AAAAAAA

a=> /* ... */ ||!( a = a.split('\n').map(b=> b.split('')) ) // split a into 2D array
    [0].map((_,c)=>a.map(d=>d[c])) // transpose it
    .some(e=>e.join``.match(R)) // run the check again using `some` to go line by line
                                // which is shorter than .join().match() outside

a=> !/* returns null if no horizontal obstacles and an array if there are */
    || !/* same thing */
// negate both to cast to a boolean (false if obstacles, true if not)
// an input can only be unslidable if both directions are blocked
// so (no obstacles vertically? || no obstacles horizontally?) gives the answer

Answer 5

JavaScript (ES6) 72 74

Edit 2 bytes saved thx @NotthatCharles

I have the intuitive understanding that if one piece can slide just a fraction of step, then it's free. The current test cases confirm this.

So I check just one step in each direction.

Characters used: 1 and 0
2 bytes more to use any 2 printable characters like A and B

Test running the snippet below in an EcmaScript 6 compliant browser (supporting the spread operator - IE Firefox)

f=s=>[w=~s.search`
`,-w,-1,1].some(o=>![...s].some((x,p)=>x+s[p+o]==10))

// 4 bytes more- for any symbol, not just 1 and 0 (for instance A and B):
g=s=>[w=~s.search`
`,-w,-1,1].some(o=>![...s].some((x,p)=>x+s[p+o]=='AB'))

//TEST
console.log=x=>O.innerHTML+=x+'\n'

testOk = [
 '111\n100\n111',
 '10',
 '0\n1',
 '01\n01',
 '000\n111',
 '00001\n01111',
 '0110\n0110\n0000',
 '000000111111111\n001111111111111\n000000000011111\n001111111111111\n000000000000001',
 '000000000000\n010101010101\n111111111111',
 '10000011\n11000111\n11101111\n11101111\n11101111\n11111111\n11111111',
 '000\n100\n000'
]

testKo = [
 '1111\n1001\n1011',
 '1111\n1001\n0011',
 '1111111\n1111101\n0000001\n1111111',
 '1000\n1010\n1110\n0010\n0000',
 '0000000\n0111110\n0000010\n1111110',
 '10000011\n11000111\n11101111\n11101111\n11100111\n11111111\n11111111',
 '000\n010\n110\n010\n000'
]

console.log('Expecting true')
testOk.forEach(t=>console.log(t+'\n'+f(t)+'\n'))
console.log('Expecting false')
testKo.forEach(t=>console.log(t+'\n'+f(t)+'\n'))

<pre id=O></pre>

Answer 6

Mathematica 100 69 bytes

With a massive 31 bytes saved, thanks to @Martin Buttner,

g=Max[Length/@Split/@#]<3&;g[c=Characters@StringSplit@#]||g@Thread@c&

Formats the input as a matrix of characters; it also makes a transpose of the matrix. If either the matrix or its transpose has no more than 2 runs per row then the puzzle is can slide.

{a,a,b,b,b} has 2 runs of letters.

{a,a,b,a,a} has 3 runs of letters.

{a,a,b,a,a,a,b,b,b,b,b,b,b,b} has 4 runs of letters.

Answer 7

Dyalog APL, 22 bytes

(∨/{∧/2>+/2≠/⍵}¨)⊂∘⍉,⊂

Try it here. This is a function that takes in a 2D array of characters, and returns 1 for sliding instances and 0 for non-sliding ones. The algorithm is similar to most other answers: check for the matrix and its transpose that no row contains more than one adjacent pair of different letters. For the 4x3 input matrix

AAAA
ABBB
AAAB

the function can be invoked as

f ← (∨/{∧/2>+/2≠/⍵}¨)⊂∘⍉,⊂
f 4 3 ⍴ 'AAAAABBBAAAB'

which results in 1.

Explanation

⊂∘⍉,⊂   The matrix and its transpose.
{...}¨   For each of them:
  2≠/⍵   On each row, replace each adjacent pair with 1 if they differ, with 0 otherwise
  2>+/    Take the sum on each row and check that it's less than 2
  ∧/     AND over all rows
∨/      OR over the resulting two values

Answer 8

JavaScript (ES6), 94 bytes

x=>!(y=/AB+A|BA+B/).test(x)|(z=[],x.split`
`.map(b=>b.split``.map((c,i)=>z[i]+=c)),!y.test(z))

Same-size alternate method:

x=>(t=s=>!/AB+A|BA+B/.test(s),z=[],x.split`
`.map(b=>b.split``.map((c,i)=>z[i]+=c)),t(x)|t(z))

This returns 1 for a truthy input and 0 for falsy. I started work on this before any other answers had been posted. I also originally tried using ES7's array comprehensions, but that ended up about 10 chars longer than this method.

Try it out:

a=x=>!(y=/AB+A|BA+B/).test(x)|(z=[],x.split`
`.map(b=>b.split``.map((c,i)=>z[i]+=c)),!y.test(z))

P.onclick=_=>Q.innerHTML='Result: '+a(O.value)

<textarea id=O cols="20" rows="8">AAAAAABBBBBBBBB
AABBBBBBBBBBBBB
AAAAAAAAAABBBBB
AABBBBBBBBBBBBB
AAAAAAAAAAAAAAB</textarea>
<button id=P>Test</button>
<p id=Q>Result: </p>

Suggestions welcome!