Haskell, 228 bytes
import Data.List
n=length;z=zipWith
a!b=div(max(a*a)(a*b))a
l x=z(!)(z(!)x(0:x))$tail x++[0]
s=(\(a,b)->(n a,n b)).partition(>0).nub.(>>=id).(until=<<((==)=<<))((.)>>=id$transpose.map l).z(\i->z(\j x->2^i*j*(2*x-1))[1,3..])[1..]
Explanation:
The idea for this solution is as follows: Initialise the matrix with unique values in each cell, positive for 1
and negative for 0
. Then repeatedly compare each cell with its neighbours and, if the neighbour has the same sign but a number with a larger absolute value, replace the cell's number wit the neighbour's number. Once this hits a fixed point, count the number of distinct positive numbers for the number of 1
regions and the distinct negative numbers for the number of 0
regions.
In code:
s=(\(a,b)->(n a,n b)).partition(>0).nub.(>>=id).(until=<<((==)=<<))((.)>>=id$transpose.map l).z(\i->z(\j x->2^i*j*(2*x-1))[1,3..])[1..]
can be separated into the preprocessing (assigning numbers to cells), the iteration, and the postprocessing (counting cells)
Preprocessing
The preprocessing part is the function
z(\i->z(\j x->2^i*j*(2*x-1))[1,3..])[1..]
Which uses z
as abbreviation for zipWith
to shave off a few bytes.
What we do here is zip the two dimensional array with integer indices at the rows and odd integer indices at the columns. We do this since we can build a unique integer from a pair of integers (i,j)
using the formula (2^i)*(2j+1)
. If we generate only odd integers for j
, we can skip calculating the 2*j+1
, saving three bytes.
With the unique number, we now only have to multiply in a sign based on the value in the matrix, which is obtained as 2*x-1
Iteration
Since the input is in the form of a list of lists, we perform the neighbour comparison on each row, transpose the matrix, perform the comparison on each row again (which due to the transpose is what was the columns before) and transpose again. The code that accomplishes one of these steps is
((.)>>=id$transpose.map l)
where l
is the comparison function (detailed below) and transpose.map l
performs one half of the comparison and transposition steps. (.)>>=id
performs its argument twice, being the pointfree form of \f -> f.f
and by one byte shorter in this case due to operator precedence rules.
l
is defined in the row above as l x=z(!)(z(!)x(0:x))$tail x++[0]
. This code performs a comparison operator (!)
(see below) on every cell with first its left neighbour, and then with its right neighbour, by zipping the list x
with the right shifted list 0:x
and the left shifted list tail x++[0]
in turn. We use zeroes to pad the shifted lists, since they can never occur in the preprocessed matrix.
a!b
is defined in the row above this as a!b=div(max(a*a)(a*b))a
. What we want to do here is the following case distinction:
- If
sgn(a) = -sgn(b)
, we have two opposing areas in the matrix and do not wish to unify them, soa
stays unchanged - If
sgn(b) = 0
, we have the corner case whereb
is padding and thereforea
stays unchanged - If
sgn(a) = sgn(b)
, we wish to unify the two areas and take the one with the bigger absolute value (for convenience's sake).
Note that sgn(a)
can never be 0
. We accomplish this with the formula given. If the signs of a
and b
differ, a*b
is less or equal to zero, while a*a
is always greater than zero, so we pick it as the maximum and divide with a
to get back a
. Otherwise, max(a*a)(a*b)
is abs(a)*max(abs(a),(abs(b))
, and by dividing this by a
, we get sgn(a)*max(abs(a),abs(b))
, which is the number with the larger absolute value.
To iterate the function ((.)>>=id$transpose.map l)
until it reached a fixed point, we use (until=<<((==)=<<))
, which is taken from this stackoverflow answer.
Postprocessing
For postprocessing, we use the part (\(a,b)->(n a,n b)).partition(>0).nub.(>>=id)
,
which is just a collection of steps.
(>>=id)
squashes the list of lists into a single list,
nub
gets rid of doubles,
partition(>0)
partitions the list into a pair of lists, one for positive and one for negative numbers,
(\(a,b)->(n a,n b))
gives the lengths of both lists, rather than the lists themselves, with the n
shorthand defined in line two to shave off a few bytes.