Escreva um programa ou função que receba uma grade retangular de texto em que cada célula seja um Aou a B. Todas as Acélulas formarão uma forma simplesmente conectada , ou seja, serão conectadas ortogonalmente sem furos (as letras vizinhas na diagonal não contam como conectadas). Da mesma forma, todas as Bcélulas formarão outra forma simplesmente conectada. A grade sempre conterá pelo menos um Ae pelo menos um B.

Imagine que a grade é na verdade dois pedaços de plástico fino em forma de bloco, representados pelas porções Ae B. Se ela fosse colocada sobre uma mesa, as duas peças poderiam ser separadas, mantendo as duas completamente sobre a mesa?

Imprima ou retorne um valor verdadeiro se os dois Ae as Bformas puderem ser separados assim, simplesmente separando-os. Caso contrário, imprima ou retorne um valor falso .

Por exemplo, a entrada

AAA
ABB
AAA

é verdade porque a BBseção pode ser deslizada para a direita, separando-a Ada:

AAA
A    BB
AAA

No entanto, a entrada

AAAA
ABBA
ABAA

é falso porque não há como separar as partes Ae Bsem que elas se sobreponham.

O código mais curto em bytes vence. Se desejar, você pode usar dois caracteres ASCII imprimíveis no lugar de Ae B.

Exemplos de verdade (separados por linhas vazias)

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

Exemplos de falsidade

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

Caracóis, 14

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

Se o quebra-cabeça puder ser deslizado, ele imprime a área da entrada. Caso contrário, ele imprime 0.

É um pouco lento para os exemplos maiores, pois leva tempo fatorial na área da grade.

         ,, 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'

CJam, 33 32 20 19 17 bytes

Versão revisada, com suporte massivo do @ Sp3000 e do @ MartinBüttner:

qN/_z]{:e`z,3<}/|

Experimente online

Contribuições

• O @ Sp3000 sugeriu uma simplificação crítica ao meu algoritmo original.
• @ MartinBüttner aplicou suas habilidades malucas de golfe à abordagem revisada, que quase certamente resultou em um código mais curto do que eu teria pensado mesmo depois de considerar a simplificação.

Algoritmo e Prova

A seguir, são apresentados os critérios para o quebra-cabeça se separar horizontalmente. O caso vertical pode ser determinado olhando para colunas em vez de linhas ou transpondo a matriz de caracteres e olhando para as linhas novamente.

Vou usar o termo "esticar" para uma sequência máxima das mesmas letras. Por exemplo, as seguintes linhas têm 1, 2 e 3 trechos, respectivamente:

AAAAAAAA
BBBAAAAA
AABBBAAA

Também usarei o termo "intertravado" para uma linha / quebra-cabeça que não pode se separar.

A observação principal é que o quebra-cabeça pode se separar se e somente se todas as linhas tiverem no máximo 2 trechos . Ou invertida, é intertravada se e somente se houver alguma linha com mais de 2 trechos .

O que se segue pode não se qualificar como uma prova matemática estrita, mas acredito que é uma explicação convincente do porquê disso.

É fácil ver que o quebra-cabeça está intertravado se tiver linhas de mais de 2 trechos. Olhando para uma linha com 3 trechos:

BBBAAB

é claro que impede que o quebra-cabeça se afaste porque o Atrecho está travado entre os Btrechos. Isso significa que a linha está intertravada, o que, por sua vez, torna todo o quebra-cabeça intertravado.

A direção oposta da prova não é tão óbvia. Precisamos mostrar que não há quebra-cabeças interligados em que todas as linhas tenham apenas 1 ou 2 trechos. Começando com algumas observações:

• Linhas com apenas 1 trecho não contribuem para o bloqueio de um quebra-cabeça, pois podem deslizar em qualquer direção sem colisões.
• Se todas as linhas com 2 trechos tiverem a mesma ordem de Ae B, o quebra-cabeça claramente não está intertravado. Nesse caso, todas as Acélulas são deixadas de todas as Bcélulas, ou vice-versa, e não há colisões ao deslizar as duas peças.

O único caso complicado seria quebra-cabeças em que temos linhas com 2 trechos de ordem diferente. Vou mostrar que esses quebra-cabeças não existem sob as especificações fornecidas. Para mostrar isso, vejamos um quebra-cabeça parcial que possui essa configuração, onde .estão os curingas:

.......
AAABBBB
.......
BBAAAAA
.......

Agora, a especificação diz que as células Ae Bsão simplesmente conectadas em todos os quebra-cabeças válidos. Para fazer as Acélulas conectadas no quebra-cabeça parcial acima, temos duas opções:

1. Nós contornamos um dos trechos de B, por exemplo:

   ..AAAAAA
   AAABBBBA
   .......A
   BBAAAAAA
   ........
   

   Para fazer isso, inevitavelmente estendemos uma das linhas para ter 3 trechos, portanto isso nunca nos dará um quebra-cabeça válido, onde todas as linhas têm no máximo 2 trechos.

2. Nós os conectamos em um caminho direto:

   .......
   AAABBBB
   ..A....
   BBAAAAA
   .......
   

   As Acélulas agora estão simplesmente conectadas e ainda não há linhas com mais de 2 trechos. No entanto, as Bcélulas também precisam ser simplesmente conectadas. O caminho direto agora está bloqueado pelas Acélulas conectadas e a única maneira de conectar as Bcélulas é fazer um loop em torno de um dos trechos de Acélulas. Isso leva ao caso 1, onde não podemos fazer isso sem criar linhas de três trechos.

Para contar as extensões, a implementação usa o operador CJam RLE.

Explicação do Código

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.

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)

Demonstração ao vivo . Testado no Firefox. Recebe a entrada como uma sequência delimitada por nova linha.

Edições:

• Economizou 1 byte mudando \npara uma nova linha literal.
• Economizou 9 bytes executando o teste RegExp diretamente na cadeia de linhas multilinhas, em vez de converter em uma matriz.
• Eliminou outros 9 bytes usando a compreensão do array para dividir a string, movendo-se! em gfunção e chamando RegExp diretamente na matriz em vez de usar find.
• Continuou a sequência arthmetic salvando outros 9 bytes. Fez um módulo no índice em vez de dividir a matriz por novas linhas antes de fazer a transposição.

Como funciona

Versão anterior:

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. Pegue a entrada ae divida-a por novas linhas em uma matriz de cadeias.
2. Transponha ae armazene-o T. Use mappara iterar sobre cada elemento de a, divida a sequência em uma matriz de caracteres e use mapnovamente para anexar o icaractere na linha à ilinha th de T. Como cada elemento de Tnão é inicializado, ele acabará parecendo algo como "undefinedAAABBA", mas isso não importa.
3. Crie uma função de teste baseada em RegExp gque corresponda ao padrão /AB+A|BA+B/. Se corresponder, as peças serão bloqueadas na direção especificada, pois haverá um conjunto de Bs imprensado entre dois ou mais As ou vice-versa.
4. Use a função gde teste para testar todos os elementos do bloco ae sua transposição Tpara uma correspondência usando find. Se os dois coincidirem, as peças serão bloqueadas nas duas direções; portanto, produza um valor falso, caso contrário, verdadeiro.

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>

Explicação:

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

JavaScript (ES6) 72 74

Editar 2 bytes salvos thx @NotthatCharles

Tenho o entendimento intuitivo de que, se uma peça pode deslizar apenas uma fração do passo, ela é gratuita. Os casos de teste atuais confirmam isso.

Então eu verifico apenas um passo em cada direção.

Caracteres usados: 1 e 0
2 bytes a mais para usar quaisquer 2 caracteres imprimíveis como A e B

Teste a execução do snippet abaixo em um navegador compatível com EcmaScript 6 (compatível com o operador de propagação - 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>

Mathematica 100 69 bytes

Com enormes 31 bytes salvos, graças a @Martin Buttner,

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

Formata a entrada como uma matriz de caracteres; também faz uma transposição da matriz. Se a matriz ou sua transposição não tiver mais de 2 execuções por linha, o quebra-cabeça pode deslizar.

{a,a,b,b,b} tem 2 séries de letras.

{a,a,b,a,a} tem 3 séries de letras.

{a,a,b,a,a,a,b,b,b,b,b,b,b,b} tem 4 séries de letras.

Dyalog APL, 22 bytes

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

Experimente aqui. Essa é uma função que recebe uma matriz 2D de caracteres e retorna 1para instâncias deslizantes e 0não instáveis. O algoritmo é semelhante à maioria das outras respostas: verifique a matriz e sua transposição para que nenhuma linha contenha mais de um par adjacente de letras diferentes. Para a matriz de entrada 4x3

AAAA
ABBB
AAAB

a função pode ser chamada como

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

o que resulta em 1.

Explicação

⊂∘⍉,⊂   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

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))

Método alternativo do mesmo tamanho:

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))

Isso retorna 1para uma entrada 0verdadeira e para falsidade. Comecei a trabalhar nisso antes que outras respostas fossem postadas. Originalmente, também tentei usar as compreensões de matriz do ES7, mas isso acabou em cerca de 10 caracteres a mais que esse método.

Experimente:

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>

Sugestões são bem-vindas!