Napisz program lub funkcję, która pobiera prostokątną siatkę tekstu, w którym każda komórka ma postać a Alub a B. Wszystkie Akomórki utworzą prosty łączony kształt, tzn. Wszystkie będą połączone prostopadle bez otworów (litery po przekątnej nie liczą się jako połączone). Podobnie, wszystkie Bkomórki utworzą kolejny, łatwo połączony kształt. Siatka zawsze będzie zawierać co najmniej jeden Ai co najmniej jeden B.

Wyobraź sobie, że siatka to w rzeczywistości dwa blokowe kawałki cienkiego plastiku, reprezentowane przez części Ai B. Gdyby zostały umieszczone płasko na stole, czy te dwa elementy można by rozłożyć, utrzymując oba całkowicie płasko na stole?

Drukuj lub zwrócić truthy wartości, jeśli obie Ai Bkształty mogą być rozdzielone tak, po prostu wyciągając je od siebie. Jeśli nie, wydrukuj lub zwróć wartość fałszowania .

Na przykład dane wejściowe

AAA
ABB
AAA

jest prawdą, ponieważ BBsekcję można przesunąć w prawo, oddzielając ją od A:

AAA
A    BB
AAA

Jednak dane wejściowe

AAAA
ABBA
ABAA

jest fałszem, ponieważ nie ma sposobu na rozsuwanie części Ai Bczęści bez nakładania się.

Najkrótszy kod w bajtach wygrywa. W razie potrzeby możesz użyć dowolnych dwóch wyraźnych drukowalnych znaków ASCII zamiast Ai B.

Prawdziwe przykłady (oddzielone pustymi liniami)

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

Przykłady Falsy

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

Ślimaki, 14

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

Jeśli łamigłówka może zostać rozłożona, drukuje obszar wejścia. W przeciwnym razie drukuje 0.

W przypadku większych przykładów jest to nieco powolne, ponieważ zajmuje silną część czasu w obszarze siatki.

         ,, 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 bajtów

Zmieniona wersja, z ogromną obsługą @ Sp3000 i @ MartinBüttner:

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

Wypróbuj online

Składki

• @ Sp3000 zasugerował krytyczne uproszczenie mojego oryginalnego algorytmu.
• @ MartinBüttner zastosował swoje szalone umiejętności gry w golfa w zmienionym podejściu, co prawie na pewno zaowocowało krótszym kodem, niż wymyśliłbym nawet po rozważeniu uproszczenia.

Algorytm i dowód

Poniżej wyjaśniono kryteria układania puzzli w poziomie. Przypadek pionowy można określić, patrząc na kolumny zamiast wierszy lub transponując matrycę znaków i ponownie patrząc na rzędy.

Użyję terminu „stretch” dla maksymalnej sekwencji tych samych liter. Na przykład następujące rzędy mają odpowiednio 1, 2 i 3 odcinki:

AAAAAAAA
BBBAAAAA
AABBBAAA

Użyję również terminu „blokowane” dla rzędu / układanki, które nie mogą się rozsuwać.

Kluczową obserwacją jest to, że łamigłówka może się rozsuwać, tylko wtedy, gdy wszystkie rzędy mają co najwyżej 2 odcinki . Lub odwrotnie, jest blokowany wtedy i tylko wtedy, gdy jest jakiś rząd z więcej niż 2 odcinkami .

Poniższe może nie kwalifikować się jako ścisły dowód matematyczny, ale uważam, że stanowi to przekonujące wyjaśnienie, dlaczego tak się dzieje.

Łatwo zauważyć, że układanka jest zablokowana, jeśli ma rzędy dłuższe niż 2 odcinki. Patrząc na wiersz z 3 odcinkami:

BBBAAB

jasne jest, że zapobiega to rozkładaniu się puzzli, ponieważ Aodcinek jest zablokowany między Bodcinkami. Oznacza to, że rząd jest zablokowany, co z kolei powoduje, że cała łamigłówka jest zablokowana.

Odwrotny kierunek dowodu nie jest tak oczywisty. Musimy pokazać, że nie ma powiązanych ze sobą łamigłówek, w których wszystkie rzędy mają tylko 1 lub 2 odcinki. Zaczynając od kilku obserwacji:

• Rzędy o tylko 1 odcinku nie przyczyniają się do blokowania łamigłówki, ponieważ mogą przesuwać się w dowolnym kierunku bez kolizji.
• Jeśli wszystkie rzędy z 2 odcinkami mają tę samą kolejność Ai B, łamigłówka wyraźnie nie jest zablokowana. W takim przypadku wszystkie Akomórki są pozostawione ze wszystkich Bkomórek lub odwrotnie, i nie ma kolizji podczas rozsuwania dwóch kawałków.

Jedynym trudnym przypadkiem byłyby puzzle, w których mamy rzędy z 2 odcinkami o różnej kolejności. Pokażę, że takie łamigłówki nie istnieją w podanych specyfikacjach. Aby to pokazać, spójrzmy na częściową układankę, która ma tę konfigurację, w której .znajdują się symbole wieloznaczne:

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

Teraz specyfikacja mówi, że obie komórki Ai Bsą po prostu połączone we wszystkie ważne łamigłówki. Aby połączyć Akomórki w powyższej częściowej układance, mamy dwie opcje:

1. Pętlimy wokół jednego z odcinków B, na przykład:

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

   Aby to zrobić, nieuchronnie przedłużamy jeden z rzędów, aby miał 3 odcinki, więc nigdy nie da nam to prawidłowej układanki, w której wszystkie rzędy mają maksymalnie 2 odcinki.

2. Łączymy je na bezpośredniej ścieżce:

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

   Te Akomórki są teraz po prostu podłączyć i nadal istnieją żadne wiersze z więcej niż 2 odcinkach. Jednak Bkomórki również muszą być po prostu połączone. Bezpośrednia ścieżka jest teraz blokowana przez połączone Akomórki, a jedynym sposobem na połączenie Bkomórek jest pętla wokół jednego z odcinków Akomórek. Prowadzi to z powrotem do przypadku 1, w którym nie możemy tego zrobić bez tworzenia rzędów 3 odcinków.

Aby policzyć odcinki, implementacja używa operatora CLEJ RLE.

Objaśnienie kodu

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 bajtów

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

Demo na żywo . Testowane w przeglądarce Firefox. Pobiera dane wejściowe jako ciąg rozdzielany znakiem nowej linii.

Edycje:

• Zaoszczędzono 1 bajt, zmieniając \nliterał na nowy wiersz.
• Zapisano 9 bajtów, wykonując test RegExp bezpośrednio na łańcuchu wieloliniowym zamiast konwertować na tablicę.
• Wyeliminowano kolejne 9 bajtów, używając wyrażeń tablicowych do podziału łańcucha, w ruchu! do gfunkcji i wywoływanie RegExp bezpośrednio na tablicy zamiast używania find.
• Kontynuowano sekwencję artmetyczną, zapisując kolejne 9 bajtów. Zrobił moduł indeksu zamiast dzielić tablicę na nowe linie przed podjęciem transpozycji.

Jak to działa

Poprzednia wersja:

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. Weź dane wejściowe ai podziel je znakami nowej linii na tablicę ciągów.
2. Transponuj ai przechowuj w T. Użyj, mapaby iterować po każdym elemencie a, podziel ciąg na tablicę znaków i użyj mapponownie, aby dołączyć ith znak w linii do ith linii T. Ponieważ każdy element Tjest niezainicjowany, będzie wyglądał podobnie "undefinedAAABBA", ale to nie będzie miało znaczenia.
3. Utwórz funkcję testową opartą na RegExp, gktóra pasuje do wzorca /AB+A|BA+B/. Jeśli pasuje, elementy są blokowane w danym kierunku, ponieważ wtedy jest zestaw Bs umieszczony pomiędzy dwoma lub więcej As lub odwrotnie.
4. Użyj funkcji testowania gdo przetestowania wszystkich elementów bloku ai jego transpozycji pod Tkątem dopasowania find. Jeśli oba pasują do siebie, elementy są blokowane w obu kierunkach, więc wyślij wartość fałszowania, w przeciwnym razie prawdziwą.

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>

Wyjaśnienie:

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

Edytuj 2 bajty zapisane thx @NotthatCharles

Rozumiem intuicyjnie, że jeśli jeden kawałek może przesunąć się tylko o ułamek kroku, to jest bezpłatny. Obecne przypadki testowe to potwierdzają.

Sprawdzam więc tylko jeden krok w każdym kierunku.

Użyte znaki: 1 i 0
2 bajty więcej, aby użyć dowolnych 2 drukowalnych znaków, takich jak A i B.

Przetestuj poniższy fragment kodu w przeglądarce zgodnej z EcmaScript 6 (obsługa operatora rozprzestrzeniania - 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 bajtów

Dzięki oszczędności 31 bajtów dzięki @Martin Buttner,

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

Formatuje dane wejściowe jako macierz znaków; dokonuje także transpozycji macierzy. Jeśli matryca lub jej transpozycja ma nie więcej niż 2 przebiegi w rzędzie, łamigłówka może się przesuwać.

{a,a,b,b,b} ma 2 serie liter.

{a,a,b,a,a} ma 3 serie liter.

{a,a,b,a,a,a,b,b,b,b,b,b,b,b} ma 4 serie liter.

Dyalog APL, 22 bajty

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

Wypróbuj tutaj. Jest to funkcja, która pobiera tablicę znaków 2D i zwraca 1dla instancji przesuwnych i 0nie-przesuwnych. Algorytm jest podobny do większości innych odpowiedzi: sprawdź macierz i jej transpozycję, aby żaden wiersz nie zawierał więcej niż jednej sąsiedniej pary różnych liter. Dla matrycy wejściowej 4x3

AAAA
ABBB
AAAB

funkcję można wywołać jako

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

co powoduje 1.

Wyjaśnienie

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

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

Metoda alternatywna tego samego rozmiaru:

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

To powraca 1 do prawdziwych danych wejściowych i 0do fałszowania. Rozpocząłem prace nad tym, zanim pojawiły się jakiekolwiek inne odpowiedzi. Początkowo próbowałem również użyć wyrażeń tablicowych ES7, ale skończyło się to około 10 znakami dłużej niż ta metoda.

Wypróbuj to:

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>

Sugestie mile widziane!