Euler characteristic of a binary matrix

Question

A binary matrix represents a shape in the plane. 1 means a unit square at that position. 0 means nothing. The background is 0.

For example, the matrix [[0,1,0],[0,0,1],[1,1,1]] represents the following shape:

     o----o
     |////|
     |////|
     o----o----o
          |////|
          |////|
o----o----o----o
|////|////|////|
|////|////|////|
o----o----o----o

There are several equivalent ways to define the Euler characteristic.

One way is finding all the vertices and edges of these squares, and defining the Euler characteristic to be \$\chi=V-E+F\$, where \$V\$ is the number of vertices, \$E\$ is the number of edges, and \$F\$ is the number of tiles.

For example, the above shape has \$13\$ vertices, \$17\$ edges, and \$5\$ tiles. So its Euler characteristic is \$13-17+5=1\$.

An equivalent definition is the total number of connected regions in the shape, minus the number of holes that occur inside those regions. Regions that connected diagonally are considered connected, while holes that are connected diagonally are considered disconnected.

For example, the above shape has \$1\$ connected region, and \$0\$ hole. So its Euler characteristic is \$1-0=1\$.

Note that there is an alternative but non-equivalent definition of the Euler characteristic, where regions that connected diagonally are considered disconnected, while holes that are connected diagonally are considered connected. The Euler characteristic of the above shape would be \$2\$ using that definition.

Task

Given a binary matrix, find its Euler characteristic.

You can use any two consistent values instead of 0 and 1 for the binary matrix.

This is code-golf, so the shortest code in bytes wins.

Testcases

[[1]] -> 1
[[1,0,1]] -> 2
[[1,0],[0,1]] -> 1
[[0,1,0],[0,0,1],[1,1,1]] -> 1
[[0,1,1,0],[1,0,1,1],[1,1,0,1],[0,1,1,0]] -> -1
[[0,0,1,1,0],[0,1,1,1,1],[1,1,0,1,1],[0,1,1,0,0]] -> 0
[[1,1,1,0,1,1,1],[1,0,1,0,1,0,1],[1,1,1,0,1,1,1]] -> 0
[[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]] -> 1

Answer 1

Charcoal, 36 bytes

ＦＡ«Ｆι«ＦκＵＯ³@#¶#@→→»⸿⸿»≔⁻№ＫＡ@№ＫＡ#θ⎚Ｉθ

Try it online! Link is to verbose version of code. Explanation:

ＦＡ«Ｆι«ＦκＵＯ³@#¶#@→→»⸿⸿»

Draw the shape represented by the matrix, except using a 3×3 square with @s at the vertices and faces and #s at the edges.

≔⁻№ＫＡ@№ＫＡ#θ

Subtract the final number of edges from the number of vertices and faces.

⎚Ｉθ

Clear the canvas and output the result.

Example: The last test case [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]] results in the following drawing:

@#@#@#@#@#@
#@#@#@#@#@#
@#@#@#@#@#@
#@#     #@#
@#@ @#@ @#@
#@# #@# #@#
@#@ @#@ @#@
#@#     #@#
@#@#@#@#@#@
#@#@#@#@#@#
@#@#@#@#@#@

This has 53 @s and 52 #s so its characteristic is 1.

Answer 2

Python NumPy, 79 bytes

lambda A:sum(g(g(pad(A,1)).T))
g=lambda A:r_[-A,A|roll(A,1)]
from numpy import*

Attempt This Online!

Old Python NumPy, 85 bytes

lambda A:sum([A:=r_[A:=pad(A.T,1),-A[1:]|-A[:-1]]for i in"12"][1])
from numpy import*

Attempt This Online!

How?

This is essentially a golfed version of the formula V-E+F given in OP. Our criterion to find edges (vertices) is that at least one of the 2 (4) adjacent squares is marked.

Little trick:

We make a sizeable saving by folding squares and vertical edges into one matrix. It turns out that the expression that computes and appends vertical edges from the squares alone can be reused verbatim to get and append horizontal edges and vertices in just one more step.

Answer 3

R, 74 68 67 bytes

Edit: -1 byte thanks to pajonk

function(m,`^`=cbind)sum(w<--t(m^0|0^m),-(t(m)^0|0^t(m)),w^0|0^w,m)

Try it online!

Gets vertical edges by adding a row of 0s to the first or last column of the matrix m, and summing the non-zero elements when these two matrices are added together:
sum(cbind(m,0)+cbind(0,m)>0), which is golfed (by substituting the cbind function) to sum(m^0+0^m>0).

Repeats the same operation with the transpose of m to get horizontal edges:
sum(cbind(t(m),0)+cbind(0,t(m))>0), golfed to sum(t(m)^0+0^t(m)>0).

We then recycle the added-together vertical-edge matrix, transposed (saved inline as w<-t(...)), and repeat the operation again to get the vertices:
sum(cbind(w,0)+cbind(0,w)>0), golfed to sum(w^0+0^w>0).

Finally, the sum of m gives us the tiles, and we can wrap it all together using only a single call to sum.

Answer 4

Octave with Image Package, 7 bytes

bweuler

Try it online!

A built-in.

---

Octave, 49 bytes

@(m)sum(conv2(m,[1,2;4,8])(:)==[1,6,7])*[1;-1;-1]

Try it online!

Based on this blog article. The Euler characteristic is \$M_1-M_2-M_3\$, where \$M_1\$, \$M_2\$, \$M_3\$ are the numbers of \$2\times2\$ submatrices of the form \$\bigl(\begin{smallmatrix}1&0\\0&0\end{smallmatrix}\bigr)\$, \$\bigl(\begin{smallmatrix}1&1\\1&0\end{smallmatrix}\bigr)\$, \$\bigl(\begin{smallmatrix}0&1\\1&0\end{smallmatrix}\bigr)\$ respectively.

Thanks @Cris Luengo for pointing out that this is Gray's algorithm.

Answer 5

Python with numpy, 79 77 bytes

lambda m:sum(sign(diff(diff(pad(kron(m,eye(2)-.5),1)).T)))
from numpy import*

Attempt This Online!

This is based on my answer to "Expand a matrix goo-ily".

kron expands each 1 into eye(2)-.5, which is \$ \begin{array}{|c|c|} \hline 0.5 & -0.5 \\ \hline -0.5 & 0.5 \\ \hline \end{array} \$. After pad adds a border of zeroes, taking diff in both directions (with a transpose in between because that's shorter than specifying a different direction for diff; the rearrangement doesn't change anything in the end) is equivalent to a sum with multipliers \$ \begin{array}{|c|c|} \hline 1 & -1 \\ \hline -1 & 1 \\ \hline \end{array} \$ on each 2-by-2 square (overlapping). The nonzero terms (before summing) are positive at even positions (by sum of coordinates), which correspond to faces and vertices, and negative at odd positions, which correspond to edges. sign produces 1 or -1, correspondingly, for each part that is present, and sum gives the Euler characteristic.

Answer 6

Python3, 606 bytes:

E=enumerate
def V(m,x,y):
 if x>=0 and y>=0:
  try:return m[x][y]
  except:return 0
def f(m):
 s,R=[],[0,0]
 while(O:=[(x,y)for x,b in E(m)for y,_ in E(b)if m[x][y]and(x,y)not in s]):
  q=[O[0]]
  while q:
   x,y=q.pop(0)
   M,D=[(0,1),(0,-1),(1,0),(-1,0)],[(-1,-1),(-1,1),(1,-1),(1,1)]
   if(x,y)in s:continue
   s+=[(x,y)]
   for u,v in M:
    R[1]+=(p:=(x+u,y+v))not in s
    if V(m,*p)and p not in s:q+=[p]
   for u,v in D:
    R[0]+=(p:=(x+u,y+v))not in s and all((x+u+j,y+v+k)not in s for j,k in[(0,[-1,1][v<1]),([-1,1][u<1],0)])
    if V(m,*p)and p not in s:q+=[p] 
 return R[0]-R[1]+sum(map(sum,m))

Try it online!

Answer 7

JavaScript (ES7), 105 bytes

This is based on the simple yet brilliant method used by Neil. It's probably not the shortest approach in JS, though.

m=>[...7**8+'23'].map(n=>m.map((r,y)=>r.map((v,x)=>!v|m[k=[x*2+n%3,y*2+n/3|0]]?0:o-=m[k]=n&1||-1)),o=0)|o

Try it online!

Commented

m =>                     // m[] = input binary matrix, reused as an object
                         //       to store the cells of the expanded matrix
[...7 ** 8 + '23']       // all digits from 0 to 8 (order doesn't matter):
                         // [ '5', '7', '6', '4', '8', '0', '1', '2', '3' ]
.map(n =>                // for each n in the above list:
  m.map((r, y) =>        //   for each row r[] at position y in m[]:
    r.map((v, x) =>      //     for each value v at position x in r[]:
      !v |               //       if v = 0
      m[                 //       or the cell at ...
        k = [            //       ... the key position k defined as ...
          x * 2 + n % 3, //         [ 2x + (n mod 3),
          y * 2 + n / 3  //           2y + floor(n / 3) ]
          | 0            //
        ]                //
      ] ?                //       ... is already set:
        0                //         do nothing
      :                  //       else:
        o -= m[k] =      //         set m[k] and update o:
          n & 1          //           -1 if n is odd (edges)
          || -1          //           +1 otherwise (vertices and faces)
    )                    //     end of map()
  ),                     //   end of map()
  o = 0                  //   start with o = 0
) | o                    // end of map(); return o