Haskell , 228 227 225 224 bajtów
import Data.List
z=zipWith
a!b=div(max(a*a)(a*b))a
l x=z(!)(z(!)x(0:x))$tail x++[0]
s=(\x->length.($x).filter<$>[(>0),(<0)]).nub.(>>=id).(until=<<((==)=<<))((.)>>=id$transpose.map l).z(\i->z(\j x->2^i*j*(2*x-1))[1,3..])[1..]
Wypró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 dla 0
. 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 liczby 1
regionów i wyraźnych liczb ujemnych dla liczby regionów0
regionów.
W kodzie:
s=(\x->length.($x).filter<$>[(>0),(<0)]).nub.(>>=id).(until=<<((==)=<<))((.)>>=id$transpose.map l).z(\i->z(\j x->2^i*j*(2*x-1))[1,3..])[1..]
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ą
z(\i->z(\j x->2^i*j*(2*x-1))[1,3..])[1..]
Który używa z
jako skrótu zipWith
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łkowite j
, możemy pominąć obliczanie 2*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
(until=<<((==)=<<))((.)>>=id$transpose.map l)
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) i transpose.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 jako l 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 listy x
za pomocą listy przesuniętej w prawo 0: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 jako a!b=div(max(a*a)(a*b))a
. To, co chcemy tutaj zrobić, to następujące rozróżnienie wielkości liter:
- Jeśli
sgn(a) = -sgn(b)
mamy dwa przeciwstawne obszary w macierzy i nie chcemy ich ujednolicać, więc a
pozostaje niezmienione
- Jeśli
sgn(b) = 0
mamy skrzynkę narożną, w której b
znajduje się wypełnienie, a zatem a
pozostaje niezmieniona
- Jeśli
sgn(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ędzie 0
. Osiągamy to dzięki podanej formule. Jeśli znaki a
i b
różnią się, a*b
jest mniejsze lub równe zero, a a*a
zawsze jest większe od zera, więc wybieramy je jako maksimum i dzielimy z, a
aby wrócić a
. W przeciwnym razie max(a*a)(a*b)
jest abs(a)*max(abs(a),(abs(b))
i dzieląc to przeza
, otrzymujemy sgn(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
(\x->length.($x).filter<$>[(>0),(<0)]).nub.(>>=id)
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.
[[1,0];[0,1]]