Napisz program lub funkcję, która pobiera wieloliniowy ciąg 0
„s 1
” i „s”. Żadne inne znaki nie będą w ciągu, a ciąg będzie zawsze prostokątny (wszystkie linie będą miały tę samą liczbę znaków), o wymiarach tak małych jak 1 × 1, ale w przeciwnym razie 0
„i 1
” mogą być ustawione dowolnie.
Możesz założyć, że ciąg ma opcjonalny końcowy znak nowej linii, a jeśli chcesz, możesz użyć dwóch różnych drukowalnych znaków ASCII zamiast 0
i 1
.
Drukuj lub zwróci wartość truthy jeśli wszystko z drogi połączone regiony zarówno 0
's i 1
jest w struny są stałe prostokąty , wyjście inny Wartość falsy .
Ścieżka połączony obszar od 0
„s oznacza, że z jednego 0
regionu, wszyscy inni 0
” s może być osiągnięty tylko przez przesunięcie w górę, w dół, w lewo iw prawo, aby inny 0
„s (a nie w ruchu po przekątnej, nie porusza się każdy 1
, a nie wychodząc poza granice łańcucha). Ten sam pomysł dotyczy 1
regionów połączonych ze ścieżką.
Stałe prostokąt o 0
„s oznacza cały obszar prostokąta jest wypełniona 0
” S i nie 1
jest. Ten sam pomysł dotyczy 1
stałych prostokątów.
Najkrótszy kod w bajtach wygrywa. Tiebreaker to wcześniejsza odpowiedź.
(Należy zauważyć, że łańcuch nie zawija się w toroidalnych warunkach brzegowych .)
Przykłady
1) Ten ciąg wejściowy ma 3 regiony połączone ścieżką (2 dla 0
i 1 dla 1
). Tylko prawy dolny 00
obszar jest jednak stałym prostokątem, więc wynik byłby fałszywy.
0011
0111
0100
2) Ten ciąg wejściowy ma 4 regiony połączone ścieżką (2 dla obu 0
i 1
). Wszystkie są solidnymi prostokątami, więc wynik byłby prawdziwy.
0011
0011
1100
3) To wejście ma 2 obszary połączone ścieżką, ale tylko jeden z nich jest stałym prostokątem, więc wynik byłby fałszywy.
00000000
01111110
00000000
4) To wejście ma tylko 1 region połączony ze ścieżką i jest trywialnie prostym prostokątem, więc dane wyjściowe są zgodne z prawdą.
11111111
11111111
11111111
Przypadki testowe
T
Tuż poniżej truthy środki ciąg wejściowy, F
środki falsy.
0
T
1
T
00
T
01
T
10
T
11
T
0000000
T
1111111
T
011100100100101100110100100100101010100011100101
T
00
11
T
01
10
T
01
11
F
00
01
F
11
11
T
110
100
F
111
000
T
111
101
111
F
101
010
101
T
1101
0010
1101
0010
T
1101
0010
1111
0010
F
0011
0111
0100
F
0011
0011
1100
T
00000000
01111110
00000000
F
11111111
11111111
11111111
T
0000001111
0000001111
T
0000001111
0000011111
F
0000001111
1000001111
F
1000001111
1000001111
T
1110100110101010110100010111011101000101111
1010100100101010100100010101010101100101000
1110100110010010110101010111010101010101011
1010100100101010010101010110010101001101001
1010110110101010110111110101011101000101111
F
Ruby, 76
Na każdej siatce złożonej w całości z prostokątów każda linia musi być identyczna z linią przed lub musi mieć wszystkie bity odwrócone od 0 do 1 i odwrotnie.
Łatwo to udowodnić. Weź kawałek papieru i narysuj na nim dowolne pionowe i poziome linie. Teraz pokoloruj prostokąty używając tylko 2 kolorów. Skończysz ze zniekształconą szachownicą, w której wszystkie kolory odwracają się w każdej linii.
Chcesz narysować prostokąty z liniami tylko częściowo w poprzek? spróbuj usunąć fragment dowolnej linii. Będziesz potrzebował więcej niż 2 kolorów, aby pokolorować swój projekt, ponieważ będziesz miał punkty, w których spotykają się 3 prostokąty (2 rogi i krawędź). Takie projekty nie mają zatem znaczenia dla tego pytania.
Jestem zaskoczony, że jak dotąd odpowiedzi tego nie zauważyłem.
Myślę, że ten algorytm powinien być znacznie krótszy w innym języku.
Niegolfowany w programie testowym
źródło
s.scan(/^?.*\n/)
że użycie pomogłoby zaoszczędzić bajty.Ślimaki , 20 bajtów
Drukuje obszar siatki, jeśli nie ma kwadratu 2x2 z 3 zerami i jednym lub 3 zerami i zero, lub
0
jeśli taki kwadrat 2x2 istnieje.źródło
MATL , 12 bajtów
Ten sam algorytm jak świetna odpowiedź @ sp3000 .
Aby umożliwić wprowadzanie danych wielowierszowych, MATL wymaga jawnej budowy tablicy znaków (łańcucha) przy użyciu znaku
10
nowej linii. Tak więc danymi wejściowymi czterech przykładów są (zauważ, że[]
jest to konkatenacja, więc każdy z nich to tablica wierszy znaków):a ostatnie trzy przypadki testowe to
Prawdziwe dane wyjściowe to tablica zawierająca tylko jedynki.
Wypróbuj online!
Wyjaśnienie
Wykorzystuje to fakt, że parzystość znaków
'0'
i'1'
jest taka sama jak liczb,0
a1
więc nie trzeba konwertować z znaku na cyfrę, którą reprezentuje,źródło
['first line' 10 'second llne']
, gdzie10
jest ASCII dla nowego wiersza. Czy to jest dopuszczalne?'0011 0111 0100'
JavaScript (ES6), 69 bajtów
Uważam, że kryterium prostokąta połączenia ścieżki jest równoważne wymaganiu, aby biorąc pod uwagę dowolne cztery punkty tworzące rogi dowolnego prostokąta, że istnieje parzysta liczba
1
s. Zauważ, że parzystość prostokąta (0, b), (x, y) jest taka sama jak (0, b), (a, y)^
(a, b), (x, y), więc muszę tylko sprawdzić prostokąty, których lewy górny róg ma wartość (0, 0). Również według praw De Morgana!.some()
jest to samo,.every(!)
co oszczędza mi kilka bajtów.Edycja: Zauważam, że rozwiązanie Galaretka sprawdza parzystość narożników wszystkich prostokątów 2 × 2, które można wykazać jako równoważne.
źródło
JavaScript (ES6), 79
Ten sam algorytm odpowiedzi Jelly z @ Sp3000 (i szczęśliwy, że nie muszę udowadniać, że działa). Tylko 8 razy dłużej
Mniej golfa
Zestaw testowy
źródło
Grime v0.1, 31 bajtów
Drukuje
1
dla dopasowania i0
bez dopasowania. Wypróbuj online!Wyjaśnienie
Grime to mój język dopasowywania wzorów 2D. Zmodyfikowałem go dzisiaj, ale tylko po to, aby zmienić charakter elementu składniowego (
`
zamiast,
), więc nie wpływa to na mój wynik.Używam podobnego podejścia do Sp3000 : dane wejściowe są fałszowane, jeśli zawierają prostokąt 2 × N, którego jeden rząd zawiera oba
0
i1
, a drugi nie.źródło
JavaScript (ES6), 64 bajty
Na podstawie obserwacji @ LevelRiverSt, że każda linia musi być taka sama lub przeciwna do pierwszej.
źródło