CJam, 33 32 20 19 17 바이트

@ Sp3000 및 @ MartinBüttner의 대규모 지원으로 수정 된 버전 :

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

온라인으로 사용해보십시오

기여

• @ Sp3000은 내 원래 알고리즘에 대한 중요한 단순화를 제안했습니다.
• @ MartinBüttner는 자신의 미친 골프 기술을 수정 된 접근 방식에 적용하여 단순화를 고려한 후에도 얻을 수 있었던 것보다 코드가 짧아졌습니다.

알고리즘 및 증명

다음은 퍼즐이 수평으로 미끄러지는 기준을 설명합니다. 세로 대소 문자는 행 대신 열을 보거나 문자 행렬을 바꾸고 행을 다시 확인하여 확인할 수 있습니다.

동일한 문자의 최대 순서에 대해 “스트레치”라는 용어를 사용하겠습니다. 예를 들어 다음 행에는 각각 1, 2 및 3 개의 스트레치가 있습니다.

AAAAAAAA
BBBAAAAA
AABBBAAA

또한 슬라이드 할 수없는 행 / 퍼즐에는 “인터 로킹”이라는 용어를 사용합니다.

핵심 관찰은 모든 행에 최대 2 개의 스트레치가있는 경우에만 퍼즐이 미끄러질 수 있다는 것입니다 . 또는 반대로, 스트레치가 두 개 이상인 행이있는 경우에만 연동됩니다 .

다음은 엄격한 수학적 증거로 인정되지는 않지만 이것이 왜 그런지 설득력있는 설명을 제공한다고 생각합니다.

퍼즐이 두 개 이상의 줄을 가지고 있으면 퍼즐이 연동되어 있음을 쉽게 알 수 있습니다. 3 개의 뻗기로 줄을 보면 :

BBBAAB

A스트레치가 스트레치 사이에 잠겨 있기 때문에 퍼즐이 미끄러지는 것을 방지하는 것이 분명합니다 B. 이것은 행이 연동되어 전체 퍼즐이 연동됨을 의미합니다.

증거의 반대 방향은 분명하지 않습니다. 모든 행에 1 ~ 2 개의 스트레치 만있는 연동 퍼즐이 없다는 것을 보여 주어야합니다. 몇 가지 관찰로 시작 :

• 1 스트레치 만있는 행은 퍼즐없이 어느 방향 으로든 미끄러질 수 있기 때문에 퍼즐이 맞 물리는 데 기여하지 않습니다.
• 이 뻗어 모든 행의 같은 순서가있는 경우 A와 B, 퍼즐 명확하게 연동되지 않습니다. 이 경우 모든 A셀이 모든 셀의 왼쪽에 B있거나 그 반대의 경우도 있으며 두 조각을 서로 밀 때 충돌이 발생하지 않습니다.

유일한 까다로운 경우는 우리가 다른 순서로 2 개의 스트레치가있는 행이있는 퍼즐입니다. 주어진 퍼즐에 그러한 퍼즐 이 존재하지 않음 을 보여줄 것입니다 . 이를 보여주기 위해이 구성이있는 부분 퍼즐 ( .와일드 카드)을 살펴 보겠습니다 .

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

이제 사양은 모두 말한다 A및 B세포는 단순히 유효한 모든 퍼즐로 연결된다. A위의 부분 퍼즐에서 셀을 연결 하려면 두 가지 옵션이 있습니다.

1. B예를 들어 의 스트레치 중 하나를 반복합니다 .

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

   이렇게하려면 불가피하게 행 중 하나를 확장하여 3 개의 스트레치를 가지므로 모든 행에 최대 2 개의 스트레치가있는 유효한 퍼즐을 만들 수 없습니다.

2. 우리는 직접 경로로 연결합니다 :

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

   A세포는 이제 단순히 연결하고, 2 개 이상의 뻗어 아무 행이 아직 없습니다. 그러나 B셀도 간단하게 연결해야합니다. 직접 경로는 이제 연결된 A셀에 의해 차단되며 셀을 연결하는 유일한 방법은 B셀의 스트레치 중 하나를 반복하는 것입니다 A. 이것은 사례 1로 돌아가서 3 스트레치 행을 만들지 않고는 할 수 없습니다.

스트레치를 계산하기 위해 구현은 CJam RLE 연산자를 사용합니다.

코드 설명

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.

답변

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

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)

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>

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

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>

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

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

AAAA
ABBB
AAAB

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

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