퍼즐을 떨어 뜨릴 수 있습니까? 모든 B세포는 간단하게 연결된 다른 모양을

모든 셀이 Aa 또는 a 인 직사각형 텍스트 격자를 취하는 프로그램 또는 함수를 작성하십시오 B. 모든 A셀은 간단하게 연결된 모양을 형성합니다. 즉, 구멍없이 직교 적으로 연결 됩니다 (대각선 인접 문자는 연결된 것으로 계산되지 않음). 마찬가지로, 모든 B세포는 간단하게 연결된 다른 모양을 형성합니다. 그리드는 항상 적어도 하나 포함 A하고 적어도 하나 B.

그리드는 얇은 플라스틱으로 표시 실제로 두 괴상 형상 조각 상상 AB부. 탁자 위에 평평하게 놓인 경우 탁자 위에 완전히 평평하게 유지하면서 두 조각을 미끄러 뜨릴 수 있습니까?

두 모양 과 모양을 단순히 분리하여 분리 할 수 있으면 진실한 값을 인쇄하거나 반환하십시오 . 그렇지 않으면 잘못된 값을 인쇄하거나 반환하십시오 .AB

예를 들어, 입력

AAA
ABB
AAA

truthy 때문이다 BB부분이 부분에서 분리 오른쪽으로 슬라이딩 할 수 A의 :

AAA
A    BB
AAA

그러나 입력

AAAA
ABBA
ABAA

AB부분을 ​​겹치지 않고 밀어 넣을 방법이 없기 때문에 거짓 입니다.

바이트 단위의 가장 짧은 코드가 이깁니다. 원하는 경우 및 대신 두 개의 구별 가능한 인쇄 가능 ASCII 문자를 사용할 수 있습니다 .AB

참신한 예 (빈 줄로 구분)

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

거짓 예

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



답변

달팽이, 14

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

퍼즐을 미끄러 뜨릴 수 있으면 입력 영역을 인쇄합니다. 그렇지 않으면 0을 인쇄합니다.

더 큰 예제의 경우 그리드 영역에서 시간이 걸리기 때문에 약간 느립니다.

         ,, 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 바이트

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

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

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

이제 사양은 모두 말한다 AB세포는 단순히 유효한 모든 퍼즐로 연결된다. 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.


답변

자바 스크립트 (ES6) 108 107 98 91 82 바이트

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

라이브 데모 . Firefox에서 테스트되었습니다. 줄 바꿈으로 구분 된 문자열로 입력을받습니다.

편집 :

  • \n리터럴 개행 으로 변경 하여 1 바이트를 절약했습니다 .
  • 배열로 변환하는 대신 여러 줄 문자열에서 직접 RegExp 테스트를 수행하여 9 바이트를 절약했습니다.
  • 배열 이해를 사용하여 문자열을 분할하고 이동하여 또 다른 9 바이트를 제거했습니다! 를 g사용하는 대신 배열에서 직접 RegExp를 호출 하고 함수를 호출 find합니다.
  • 다른 9 바이트를 저장하여 arthetic 시퀀스를 계속했습니다. 조옮김 전에 배열을 줄 바꿈으로 나누는 대신 인덱스에서 계수를 수행했습니다.

작동 원리

이전 버전:

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. 입력을 받아서 a줄 바꿈으로 문자열 배열로 나눕니다.
  2. 전치 a하여에 저장하십시오 T. 의 map각 요소를 반복 a하고 문자열을 문자형 배열로 분할 한 다음 map다시 사용 i하여 행 의 th 문자를의 ith 행에 추가 T합니다. 의 각 요소 T는 초기화되지 "undefinedAAABBA"않았기 때문에 결국과 같이 보이지만 이것은 중요하지 않습니다.
  3. g패턴과 일치 하는 RegExp 기반 테스트 기능 을 작성하십시오 /AB+A|BA+B/. 일치하면 조각이 주어진 방향으로 잠기므로 B두 개 이상 A또는 그 사이에 샌드위치 세트가 끼워져 있기 때문 입니다.
  4. 테스트 기능을 사용하여 g모든 블록의 요소를 테스트 a하고 전치 T사용하여 일치를 find. 둘 다 일치하면 조각이 양방향으로 잠기므로 잘못된 값을 출력하고 그렇지 않으면 잘못된 값을 출력합니다.

답변

자바 스크립트 (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>

설명:

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


답변

자바 스크립트 (ES6) 72 74

2 바이트 저장된 @NotthatCharles 편집

한 조각이 조금만 움직일 수 있다면 자유 롭다는 직관적 인 이해가 있습니다. 현재 테스트 사례가이를 확인합니다.

각 방향에서 한 걸음 만 확인합니다.

사용 된 문자 :
A 및 B와 같은 2 개의 인쇄 가능한 문자를 사용하기 위해 1 및 0 2 바이트 이상

EcmaScript 6 호환 브라우저에서 아래 스 니펫 실행 테스트 (스프레드 연산자 지원-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 바이트

@Martin Buttner 덕분에 엄청난 31 바이트가 절약되었습니다.

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

입력을 문자 매트릭스로 형식화합니다. 또한 행렬의 전치를 만듭니다. 행렬 또는 그 조옮김이 행당 2 회 이하인 경우 퍼즐을 슬라이드 할 수 있습니다.

{a,a,b,b,b} 2 줄의 문자가 있습니다.

{a,a,b,a,a} 3 줄의 문자가 있습니다.

{a,a,b,a,a,a,b,b,b,b,b,b,b,b} 4 줄의 문자가 있습니다.


답변

Dyalog APL, 22 바이트

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

여기에서 시도하십시오.
이것은 2D 문자 배열을 가져 와서 1슬라이딩 인스턴스와 0비 슬라이드 인스턴스에 대해 반환하는 함수 입니다. 이 알고리즘은 대부분의 다른 답변과 유사합니다. 행렬을 확인하고 행에 서로 다른 문자 쌍이 하나 이상 포함되어 있지 않은지 조옮김하십시오. 4×3 입력 매트릭스

AAAA
ABBB
AAAB

함수는 다음과 같이 호출 될 수 있습니다

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

결과 1.

설명

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