15
\$\begingroup\$

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.)

\$\endgroup\$
2
  • 2
    \$\begingroup\$ Can different faces have different numbers of vertices? \$\endgroup\$
    – xnor
    Mar 14, 2018 at 23:03
  • 1
    \$\begingroup\$ Yes, they can have any number of vertices. \$\endgroup\$
    – flawr
    Mar 14, 2018 at 23:10

16 Answers 16

6
\$\begingroup\$

Haskell, 42 bytes

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!

\$\endgroup\$
1
  • \$\begingroup\$ This is very clever :) \$\endgroup\$
    – flawr
    Mar 15, 2018 at 9:12
5
\$\begingroup\$

Haskell, 49 46 bytes

u=length
f x|j<-x>>=id=maximum j+u x-u j`div`2

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.

\$\endgroup\$
4
\$\begingroup\$

APL (Dyalog Classic), 13 bytes

⌈/∘∊+≢-2÷⍨≢∘∊

Try it online!

\$\endgroup\$
4
\$\begingroup\$

Jelly, 18 17 11 10 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
\$\endgroup\$
5
  • \$\begingroup\$ Can't you replace ;/ with F? ;-) \$\endgroup\$ Mar 14, 2018 at 22:16
  • \$\begingroup\$ @EriktheOutgolfer Lol, that was apparently left there as some kind of brainfart from a dev version \$\endgroup\$ Mar 14, 2018 at 22:17
  • \$\begingroup\$ In fact, it made the code error in case of empty arrays. \$\endgroup\$ Mar 14, 2018 at 22:19
  • \$\begingroup\$ Will there ever be empty arrays? \$\endgroup\$ Mar 14, 2018 at 22:19
  • \$\begingroup\$ Oh, and 1) your TIO link has a different code and 2) there are new quicks! \$\endgroup\$ Mar 14, 2018 at 22:20
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Wheat Wizard
    Mar 14, 2018 at 22:23
  • \$\begingroup\$ @user56656 It indeed saves a byte, thanks! \$\endgroup\$ Mar 15, 2018 at 10:27
2
\$\begingroup\$

Wolfram Language (Mathematica), 24 bytes

-3 bytes thanks to @att.

Max@#-Tr[Tr/@(1^#)/2-1]&

Try it online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 24: Max@#-Tr[Tr/@(1^#)/2-1]& \$\endgroup\$
    – att
    Sep 8, 2023 at 2:20
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

Pari/GP, 28 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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)
        +  # add (F-E+V)
\$\endgroup\$
1
\$\begingroup\$

Pyth, 12 bytes

+-eSsQ/lsQ2l

Try it here

\$\endgroup\$
1
\$\begingroup\$

Scala 3, 46 bytes

A port of @Wheat Wizard♦'s Haskell answer in Scala.


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

Attempt This Online!

\$\endgroup\$
1
\$\begingroup\$

K (ngn/k), 22 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Ruby, 35 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Proton, 35 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.