# Euler-Poincaré-Characteristic of Polyhedra

Given a triangulation of the surface of a polyhedron p, calculate its Euler-Poincaré-Characteristic χ(p) = V-E+F, where V is the number of vertices, E the number of edges and F the number of faces.

### Details

The vertices are enumerated as 1,2,...,V. The triangulation is given as a list, where each entry is a list of the vertices of one face, given in clockwise or counterclockwise order.

Despite the name, the triangulation can also contain faces with more than 3 sides. The faces can assumed to be simply connected that means that the boundary of each faces can be drawn using one closed non-self-intersecting loop.

### Examples

Tetrahedron: This tetrahedron is convex and has χ = 2. A possible triangulation is

[[1,2,3], [1,3,4], [1,2,4], [2,3,4]]


Cube: This cube is convex and has χ = 2. A possible triangulation is

[[1,2,3,4], [1,4,8,5], [1,2,6,5], [2,3,7,6], [4,3,7,8],  [5,6,7,8]]


Donut: This donut/toroid shape has χ = 0. A possible triangulation is

[[1,2,5,4], [2,5,6,3], [1,3,6,4], [1,2,7,9], [2,3,8,7], [1,9,8,3], [4,9,8,6], [4,5,7,9], [5,7,8,6]]


Double Donut: This double-donut should have χ = -2. It is constructed by using two copies of the donut above and identifying the sides [1,2,5,4] of the first one with the side [1,3,6,4] of the second one.

[[2,5,6,3], [1,3,6,4], [1,2,7,9], [2,3,8,7], [1,9,8,3], [4,9,8,6], [4,5,7,9], [5,7,8,6], [1,10,11,4], [10,11,5,2], [1,10,12,14], [10,2,13,12], [1,14,13,2], [4,14,13,5], [4,11,12,14], [11,12,13,5]]


(Examples verified using this Haskell program.)

• Can different faces have different numbers of vertices?
– xnor
Mar 14, 2018 at 23:03
• Yes, they can have any number of vertices. Mar 14, 2018 at 23:10

f m=maximum(id=<<m)-sum[0.5|_:_:l<-m,x<-l]


Try it online!

Combines the face and edge terms by subtracting 0.5 for every edge on a face beyond the first two.

Alt 42 bytes:

f m=maximum(id=<<m)-sum(0.5<$(drop 2=<<m))  Try it online! • This is very clever :) Mar 15, 2018 at 9:12 # Haskell, 49 46 bytes u=length f x|j<-x>>=id=maximum j+u x-u jdiv2  Try it online! I get the number of vertices by concating the faces and finding the maximum. I find the number of faces by taking the length. I find the number of edges by summing the lengths of the faces and dividing by 2. # APL (Dyalog Classic), 13 bytes ⌈/∘∊+≢-2÷⍨≢∘∊  Try it online! # Jelly, 18171110 9 bytes 1 byte thanks to Erik the Outgolfer, and 1 more for telling me about Ɗ. FṀ_FLHƊ+L  Try it online! Uses the actually intelligent not-hacked-together solution everybody else is probably using. (Credit to @totallyhuman for the only other solution I could understand enough to reimplement it.) ## Old solution (17 bytes) ṙ€1FżFṢ€QL ;FQL_Ç  Try it online! I hope I got everything right. Assumes that all faces contain at least 3 vertices and that no two faces have the same vertices; I'm not good enough in topology to come up with something that breaks the code. Alternative 17 byte solution: ṙ€1FżFṢ€,;F$QL$€I  ### Explanation ;FQL_Ç Main link. Argument: faces e.g. [[1,2,3],[1,3,4],[1,2,4],[2,3,4]] F Flatten the list. We now have a flat list of vertices. e.g. [1,2,3,1,3,4,1,2,4,2,3,4] ; Append this to the original list. e.g. [[1,2,3],[1,3,4],[1,2,4],[2,3,4],1,2,3,1,3,4,1,2,4,2,3,4] Q Remove duplicates. We now have a list of faces and vertices. e.g. [[1,2,3],[1,3,4],[1,2,4],[2,3,4],1,2,3,4] L Get the length of this list. This is equal to V+F. e.g. 8 Ç Call the helper link on the faces to get E. e.g. 6 _ Subtract the edges from the previous result to get V-E+F. e.g. 2 ṙ€1FżFṢ€QL Helper link. Argument: faces e.g. [[1,2,3],[1,3,4],[1,2,4],[2,3,4]] ṙ€1 Rotate each face 1 position to the left. e.g. [[2,3,1],[3,4,1],[2,4,1],[3,4,2]] F Flatten this result. e.g. [2,3,1,3,4,1,2,4,1,3,4,2] F Flatten the original faces. e.g. [1,2,3,1,3,4,1,2,4,2,3,4] ż Pair the items of the two flattened lists. e.g. [[2,1],[3,2],[1,3],[3,1],[4,3],[1,4],[2,1],[4,2],[1,4],[3,2],[4,3],[2,4]] Ṣ€ Order each edge. e.g. [[1,2],[2,3],[1,3],[1,3],[3,4],[1,4],[1,2],[2,4],[1,4],[2,3],[3,4],[2,4]] Q Remove duplicates. We now have a list of edges. e.g. [[1,2],[2,3],[1,3],[3,4],[1,4],[2,4]] L Get the length of the list to get E. e.g. 6  • Can't you replace ;/ with F? ;-) Mar 14, 2018 at 22:16 • @EriktheOutgolfer Lol, that was apparently left there as some kind of brainfart from a dev version Mar 14, 2018 at 22:17 • In fact, it made the code error in case of empty arrays. Mar 14, 2018 at 22:19 • Will there ever be empty arrays? Mar 14, 2018 at 22:19 • Oh, and 1) your TIO link has a different code and 2) there are new quicks! Mar 14, 2018 at 22:20 # Perl 5-a, 29 bytes This one is tailor made for the perl -a option which does almost all the work already #!/usr/bin/perl -a @V[@F]=$e+=@F}{say$#V+$.-$e/2  Try it online! # Python 2, 47 bytes -1 byte thanks to... user56656 (was Wheat Wizard originally). lambda l:len(l)-len(sum(l,[]))/2+max(sum(l,[]))  Try it online! • I improved my original haskell answer by saving sum(l,[]) to be used twice. I don't know if this could be used in Python as well. Mar 14, 2018 at 22:23 • @user56656 It indeed saves a byte, thanks! Mar 15, 2018 at 10:27 # Wolfram Language (Mathematica), 24 bytes -3 bytes thanks to @att. Max@#-Tr[Tr/@(1^#)/2-1]&  Try it online! • 24: Max@#-Tr[Tr/@(1^#)/2-1]& – att Sep 8, 2023 at 2:20 # Stax, 9 bytes ÑF4╨Ω◙╜#├  Run and debug online It's a straight-forward port of totallyhuman's python solution. % length of input (a) x$Y flatten input and store in y
%h  half of flattened length (b)
-   subtract a - b (c)
y|M maximum value in y (d)
+   add c + d and output


Run this one

# Pari/GP, 28 bytes

x->#x+#Set(y=concat(x))-#y/2


Try it online!

# 05AB1E, 10 9 bytes

ZsgI˜g;-+


Try it online!

Explanation

Z          # push number of vertices (V)
sg        # push number of faces (F)
I˜g;    # push number of edges (E)
-   # subtract (F-E)


# Pyth, 12 bytes

+-eSsQ/lsQ2l


Try it here

# Scala 3, 46 bytes

x=>{val j=x.flatten;j.max+x.length-j.length/2}


Attempt This Online!

# K (ngn/k), 22 bytes

{(#x)+(|/y)--2!#y}/,/\


Try it online!

# Ruby, 35 bytes

->a{a.size+a.flatten!.max-a.size/2}


Try it online!

# Proton, 35 bytes

l=>max(f=sum(l,[]))-len(f)/2+len(l)


Try it online!

## JavaScript (ES6), 60 bytes

a=>a.map(b=>(v=Math.max(v,...b),d+=b.length/2-1),d=v=0)&&v-d


Explanation: Loops over each face, keeping track of the largest vertex seen in v and tracking the number of edges minus the number of faces in d as per @xnor's answer.