Biorąc pod uwagę dwuwymiarową macierz 0 i 1s. Znajdź liczbę wysp dla 1 i 0, gdzie sąsiedzi są tylko w poziomie i pionie.
Given input:
1 1 1 0
1 1 1 0
output = 1 1
Number of 1s island = 1
xxx-
xxx-
Number of 0s island = 1
---x
---x
------------------------------
Given input:
0 0 0 0
1 1 1 1
0 0 0 0
1 1 1 1
output = 2 2
Number of 1s island = 2
----
xxxx <-- an island of 1s
----
xxxx <-- another island of 1s
Number of 0s island = 2
xxxx <-- an island
----
xxxx <-- another island
----
------------------------------
Given input:
1 0 0
0 0 0
0 0 1
output = 2 1
Number for 1's island = 2:
x-- <-- an island of 1s
---
--x <-- an island of 1s
Number of 0's island = 1:
-xx \
xxx > 1 big island of 0s
xx- /
------------------------------
Given input:
1 1 0
1 0 0
output = 1 1
Number for 1's island =1 and number of 0's island = 1
------------------------------
Given input:
1 1
1 1
output = 1 0
Number for 1's island =1 and number of 0's island = 0
code-golf
binary-matrix
KB radość
źródło
źródło
[[1,0];[0,1]]
11111 / 10001 / 10101 / 10001 / 11111
→2 1
Odpowiedzi:
APL (Dyalog Unicode) ,
2928 bajtów SBCS-1 dzięki @ Adám
Wypróbuj online!
⊂,~∘⊂
matryca i jej negacja{
}¨
dla każdego z nich⍸⍵
lista par współrzędnych 1s+/↑|∘.-⍨
macierz odległości manhattan2>
macierz sąsiada∨.∧⍨⍣≡
zamknięcie przechodnie≢∪
liczba unikalnych wierszyźródło
^:_
?J , 57 bajtów
Wypróbuj online!
Jest to jeden z tych, w których pomysł jest niewiarygodnie prosty (i myślę, że fajnie), ale wykonanie go miało pewną mechaniczną długość, która maskuje prostotę ... np. Przesunięcie oryginalnej matrycy we wszystkich kierunkach z wypełnieniem 0 jest pełne
((,-)#:i.3) |.!.0
.Jest prawdopodobne, że tę mechaniczną długość można pograć w golfa i mogę spróbować jutro wieczorem, ale opublikuję sedno tego.
Powiedz, że nasz wkład to:
Zaczynamy od macierzy unikalnych liczb całkowitych tego samego rozmiaru:
Następnie dla każdej komórki znajdujemy maksimum wszystkich jej sąsiadów i mnożymy przez maskę wejściową:
Powtarzamy ten proces, dopóki matryca nie przestanie się zmieniać:
A następnie policz liczbę unikalnych, niezerowych elementów. To mówi nam o liczbie 1 wysp.
Stosujemy ten sam proces do „1 minus dane wejściowe”, aby uzyskać liczbę 0 wysp.
źródło
JavaScript (ES7),
138 ... 107106 bajtówZwraca tablicę
[ones, zeros]
.Wypróbuj online!
W jaki sposób?
Używamy funkcji rekurencyjnej. Podczas wstępnej rozmowy, szukamy0 „si 1 ” s. Ilekroć znajdziemy taki punkt początkowy, zwiększamy odpowiedni licznik wysp ( c[0] lub c[1] ) i wchodzimy w fazę rekurencyjną, aby wypełnić obszar podobnych sąsiednich komórek 2 .
Aby zapisać bajty, dokładnie ten sam kod jest używany zarówno dla iteracji root, jak i iteracji rekurencyjnych, ale zachowuje się nieco inaczej.
Podczas pierwszej iteracji:
Podczas iteracji rekurencyjnych:
c[v ^ 1]++
Skomentował
źródło
MATL ,
1412 bajtówWypróbuj online! Lub sprawdź wszystkie przypadki testowe .
Wyjaśnienie
źródło
K (ngn / k) ,
60 55 51 5046 bajtówWypróbuj online!
~:\
para danych wejściowych i ich negacja (dosłownie: negate iterate-converge){
}'
dla każdego,/x
spłaszcz arg&
gdzie są jedynki? - lista indeksów(0,#*x)\
divmod width (input), aby uzyskać dwie osobne listy dla ys i xsx-\:'x:
odległości między osiami ∆x i ∆yx*x:
wyprostuj je+/
dodaj ∆x² i ∆y²2>
macierz sąsiada{|/'x*\:x}/
zamknięcie przechodnie#?
policz unikalne wierszeźródło
Wolfram Language (Mathematica) ,
6462 bajtówWypróbuj online!
Dzięki attinat : możemy pisać
1<0
zamiastFalse
i zapisywać dwa bajty.wersja bez gry w golfa:
Istnieje oczywiście wbudowana funkcja Mathematica,
MorphologicalComponents
która pobiera tablicę (lub obraz) i zwraca to samo z pikselami każdej morfologicznie połączonej wyspy zastąpionymi indeksem wysp. BiorącMax
ten wynik daje liczbę wysp (zera tła są pozostawione na zero, a indeks wysp zaczyna się od 1). Musimy to zrobić osobno dla tablicy (podając liczbę 1 wysp) i jeden minus tablicy (podając liczbę 0 wysp). Aby upewnić się, że ukośni sąsiedzi nie liczą się jako sąsiedzi,CornerNeighbors->False
należy podać opcję .źródło
Rule
Python 3,
144127 bajtówTo rozwiązanie wykorzystuje
cv2
niesamowitą moc przetwarzania obrazu. Pomimo mniej niesamowitych, bardzo długich i czytelnych nazw cv, cv pokonuje obie inne odpowiedzi w języku Python!Gra w golfa:
Rozszerzony:
źródło
4
zamiastconnectivity=4
in.uint8
zamiast jestdtype=n.uint8
możliwe?cv2.connectedComponents
metodę, więc byłem zdezorientowany i pomyślałem, że mógł istnieć inny powód, aby potrzebować nazw argumentów. Jak powiedziałem, nie znam zbyt dobrze Pythona. Wszystko, czego się nauczyłem, pochodzi stąd z CCGC. ;) Ale warto używać nazw zmiennych, aby pominąć inne opcjonalne argumenty.J ,
46 4443 bajty-1 bajt dzięki @miles
Wypróbuj online!
testy i
,&
-.
opakowanie skradzione z odpowiedzi @ jonah,&
-.
dla danych wejściowych i ich negacji wykonaj:4$.$.
(y, x) współrzędne 1s jako macierz n × 21#.[:|@-"1/~
manhattan odległości: abs (∆x) + abs (∆y)2>
macierz sąsiada[:+./ .*~^:_:
zamknięcie przechodnie#&~.&(
)
liczba unikalnych wierszyźródło
,&#&~.
aby uniknąć limitu[:
Retina 0.8.2 , 155 bajtów
Wypróbuj online! Link zawiera przypadek testowy. Wyjaśnienie:
Jeśli istnieje
1
, zmień go na;
i dodaja
na końcu wejścia, aby nie przeszkadzało.Powódź wypełnić kolejne sąsiednie
1
litery;
s.Powtarzaj, aż wszystkie wyspy
1
s zostaną zamienione w;
s.Jeśli istnieje
0
, zmień go na:
i dodajb
na końcu wejścia, aby nie przeszkadzało.Powódź wypełnić kolejne sąsiednie
0
litery:
s.Powtarzaj, aż wszystkie wyspy
0
s zostaną zamienione w:
s.Osobno policz liczbę wysp
1
s i0
s.źródło
Haskell ,
228227225224 bajtówWypróbuj online!
Wyjaśnienie:
Pomysł na to rozwiązanie jest następujący: Zainicjuj macierz unikalnymi wartościami w każdej komórce, dodatnimi
1
i ujemnymi dla0
. Następnie kilkakrotnie porównaj każdą komórkę z sąsiadami i, jeśli sąsiad ma ten sam znak, ale liczbę o większej wartości bezwzględnej, zamień numer komórki na numer sąsiada. Gdy osiągnie to ustalony punkt, policz liczbę odrębnych liczb dodatnich dla liczby1
regionów i wyraźnych liczb ujemnych dla liczby regionów0
regionów.W kodzie:
można podzielić na przetwarzanie wstępne (przypisywanie liczb do komórek), iterację i przetwarzanie końcowe (zliczanie komórek)
Przetwarzanie wstępne
Część wstępnego przetwarzania jest funkcją
Który używa
z
jako skrótuzipWith
do golenia kilku bajtów. To, co tu robimy, to spakowanie dwuwymiarowej tablicy z indeksami liczb całkowitych w wierszach i nieparzystymi indeksami liczb całkowitych w kolumnach. Robimy to, ponieważ możemy zbudować unikalną liczbę całkowitą z pary liczb całkowitych(i,j)
przy użyciu formuły(2^i)*(2j+1)
. Jeśli generujemy tylko nieparzyste liczby całkowitej
, możemy pominąć obliczanie2*j+1
, oszczędzając trzy bajty.Dzięki unikalnemu numerowi musimy teraz tylko pomnożyć znak w oparciu o wartość w macierzy, która jest uzyskiwana jako
2*x-1
Iteracja
Iteracja jest wykonywana przez
Ponieważ dane wejściowe są w postaci listy list, przeprowadzamy porównanie sąsiadów w każdym wierszu, transponujemy macierz, ponownie wykonujemy porównanie w każdym wierszu (który ze względu na transpozycję było to, co było wcześniej w kolumnach) i transponujemy ponownie. Kod, który wykonuje jeden z tych kroków, to
((.)>>=id$transpose.map l)
gdzie
l
jest funkcja porównawcza (wyszczególniona poniżej) itranspose.map l
wykonuje połowę kroków porównania i transpozycji.(.)>>=id
wykonuje argument dwa razy, ponieważ\f -> f.f
w tym przypadku jest on pozbawiony punktów i o jeden bajt krótszy ze względu na reguły pierwszeństwa operatora.l
jest zdefiniowany w powyższym wierszu jakol x=z(!)(z(!)x(0:x))$tail x++[0]
. Ten kod wykonuje operator porównania(!)
(patrz poniżej) na każdej komórce, najpierw z lewym sąsiadem, a następnie z prawym sąsiadem, poprzez skompresowanie listyx
za pomocą listy przesuniętej w prawo0:x
i listy przesuniętej w lewotail x++[0]
w lewo. Używamy zer do wypełniania przesuniętych list, ponieważ nigdy nie mogą wystąpić w macierzy wstępnie przetworzonej.a!b
jest zdefiniowany w wierszu powyżej tego jakoa!b=div(max(a*a)(a*b))a
. To, co chcemy tutaj zrobić, to następujące rozróżnienie wielkości liter:sgn(a) = -sgn(b)
mamy dwa przeciwstawne obszary w macierzy i nie chcemy ich ujednolicać, więca
pozostaje niezmienionesgn(b) = 0
mamy skrzynkę narożną, w którejb
znajduje się wypełnienie, a zatema
pozostaje niezmienionasgn(a) = sgn(b)
chcemy ujednolicić oba obszary i przyjąć ten o większej wartości bezwzględnej (dla wygody).Zauważ, że
sgn(a)
nigdy nie będzie0
. Osiągamy to dzięki podanej formule. Jeśli znakia
ib
różnią się,a*b
jest mniejsze lub równe zero, aa*a
zawsze jest większe od zera, więc wybieramy je jako maksimum i dzielimy z,a
aby wrócića
. W przeciwnym raziemax(a*a)(a*b)
jestabs(a)*max(abs(a),(abs(b))
i dzieląc to przeza
, otrzymujemysgn(a)*max(abs(a),abs(b))
, co jest liczbą o większej wartości bezwzględnej.Aby iterować funkcję,
((.)>>=id$transpose.map l)
dopóki nie osiągnie ustalonego punktu, używamy(until=<<((==)=<<))
, który jest wzięty z tej odpowiedzi przepełnienia stosu .Przetwarzanie końcowe
Do przetwarzania końcowego używamy tej części
który jest tylko zbiorem kroków.
(>>=id)
zgniata listę list w jedną listę,nub
pozbywa się dubletów,(\x->length.($x).filter<$>[(>0),(<0)])
dzieli listę na parę list, jedną na liczby dodatnie i jedną na liczby ujemne, i oblicza ich długości.źródło
Java 10,
359355281280261246 bajtów-74 bajty dzięki @NahuelFouilleul .
Wypróbuj online.
Wyjaśnienie:
źródło
|=2
: 0 -> 2 i 1 -> 3, jednak>0
zmieniono na==1
|=2
! I nadal mógłbym użyć<2
zamiast==1
bajtu -1, najpierw sprawdzając0
(i dlatego są one zmieniane na2
, a następnie za pomocą<2
sprawdzania1
(które są zmieniane na3
))Python 3 , 167 bajtów
Wypróbuj online!
Python 2 , 168 bajtów
Wypróbuj online!
-2 bajty dzięki Kevin Cruijssen
Poprawka formatowania 2 bajtów
Wyjaśnienie
Licznik jest przechowywany przez 0 i 1 s. Dla każdego wpisu w macierzy wykonywane są następujące działania:
To daje wynik fałszywie dodatni dla przypadków wyrównanych do lewej, takich jak
lub
W takiej sytuacji licznik zmniejsza się o 1.
Zwracana wartość to
[#1, #0]
źródło
[#1, #0]
. Trochę bezsensownego imo, aby to egzekwować, ale na razie to jest to. W każdym razie, można Golf{not c}
do{c^1}
i rozwiązać problem wspomniałem zmieniającn[c]+=
sięn[c^1]+=
w podobnej sprawie. Dobra odpowiedź, +1 ode mnie. :)Perl 5 (
-0777p
), 110 bajtówMoże być ulepszona, używa regex do zastąpienia
1
z3
, następnie0
z2
.TIO
źródło
Galaretka ,
4436 bajtówWypróbuj online!
Link monadyczny przyjmujący listę argumentów liczb całkowitych jako argument i zwracający listę liczby wysp 1 i 0 w tej kolejności.
Wyjaśnienie
Krok 1
Wygeneruj listę wszystkich indeksów macierzowych, każdy z indeksami sąsiada po prawej stronie (chyba że po prawej stronie) i w dół (chyba że na dole)
Krok 2
Podziel te wskaźniki według tego, czy na wejściu było 1 czy 0. Zwraca jedną listę indeksów z sąsiadami dla 1s, a drugą dla 0.
Krok 3
Scal listy z elementami wspólnymi i licznikami wyjściowymi
źródło
T-SQL 2008, 178 bajtów
Dane wejściowe to zmienna tabelowa.
Dane testowe użyte w tym przykładzie:
Wypróbuj online
źródło
R ,
194172 bajtówWypróbuj online!
Wykonaj wyszukiwanie od pierwszej głębokości, zaczynając od każdej komórki macierzy, która jest równa 1 (lub zero).
źródło