Napisz program lub funkcję, która pobiera prostokątną siatkę tekstu, w którym każda komórka ma postać a A
lub a B
. Wszystkie A
komó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 B
komórki utworzą kolejny, łatwo połączony kształt. Siatka zawsze będzie zawierać co najmniej jeden A
i co najmniej jeden B
.
Wyobraź sobie, że siatka to w rzeczywistości dwa blokowe kawałki cienkiego plastiku, reprezentowane przez części A
i 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 A
i B
kształ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ż BB
sekcję 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 A
i B
częś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 A
i 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
CJam,
3332201917 bajtówZmieniona wersja, z ogromną obsługą @ Sp3000 i @ MartinBüttner:
Wypróbuj online
Składki
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:
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:
jasne jest, że zapobiega to rozkładaniu się puzzli, ponieważ
A
odcinek jest zablokowany międzyB
odcinkami. 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:
A
iB
, łamigłówka wyraźnie nie jest zablokowana. W takim przypadku wszystkieA
komórki są pozostawione ze wszystkichB
komó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:Teraz specyfikacja mówi, że obie komórki
A
iB
są po prostu połączone we wszystkie ważne łamigłówki. Aby połączyćA
komórki w powyższej częściowej układance, mamy dwie opcje:Pętlimy wokół jednego z odcinków
B
, na przykład: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.
Łączymy je na bezpośredniej ścieżce:
Te
A
komórki są teraz po prostu podłączyć i nadal istnieją żadne wiersze z więcej niż 2 odcinkach. JednakB
komórki również muszą być po prostu połączone. Bezpośrednia ścieżka jest teraz blokowana przez połączoneA
komórki, a jedynym sposobem na połączenieB
komórek jest pętla wokół jednego z odcinkówA
komó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
źródło
JavaScript (ES6),
108107989182 bajtówDemo na żywo . Testowane w przeglądarce Firefox. Pobiera dane wejściowe jako ciąg rozdzielany znakiem nowej linii.
Edycje:
\n
literał na nowy wiersz.g
funkcji i wywoływanie RegExp bezpośrednio na tablicy zamiast używaniafind
.Jak to działa
Poprzednia wersja:
a
i podziel je znakami nowej linii na tablicę ciągów.a
i przechowuj wT
. Użyj,map
aby iterować po każdym elemenciea
, podziel ciąg na tablicę znaków i użyjmap
ponownie, aby dołączyći
th znak w linii doi
th liniiT
. Ponieważ każdy elementT
jest niezainicjowany, będzie wyglądał podobnie"undefinedAAABBA"
, ale to nie będzie miało znaczenia.g
która pasuje do wzorca/AB+A|BA+B/
. Jeśli pasuje, elementy są blokowane w danym kierunku, ponieważ wtedy jest zestawB
s umieszczony pomiędzy dwoma lub więcejA
s lub odwrotnie.g
do przetestowania wszystkich elementów blokua
i jego transpozycji podT
kątem dopasowaniafind
. Jeśli oba pasują do siebie, elementy są blokowane w obu kierunkach, więc wyślij wartość fałszowania, w przeciwnym razie prawdziwą.źródło
JavaScript (ES6), 118
Wyjaśnienie:
źródło
JavaScript (ES6) 72
74Edytuj 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)
źródło
s[p+o]=='0'
wydaje się trochę długi. Czy można to zastąpić1-s[p+o]
, a przynajmniejs[p+o]==0
?=='A'
można zastąpić<'B'
. To samo dotyczy=='B'
x+s[p+o]=='AB'
?Mathematica
10069 bajtówDzięki oszczędności 31 bajtów dzięki @Martin Buttner,
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.źródło
Dyalog APL, 22 bajty
Wypróbuj tutaj. Jest to funkcja, która pobiera tablicę znaków 2D i zwraca
1
dla instancji przesuwnych i0
nie-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 4x3funkcję można wywołać jako
co powoduje
1
.Wyjaśnienie
źródło
JavaScript (ES6), 94 bajty
Metoda alternatywna tego samego rozmiaru:
To powraca
1
do prawdziwych danych wejściowych i0
do 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:
Sugestie mile widziane!
źródło