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
    \$\begingroup\$ Can different faces have different numbers of vertices? \$\endgroup\$ – xnor Mar 14 '18 at 23:03
  • 1
    \$\begingroup\$ Yes, they can have any number of vertices. \$\endgroup\$ – flawr Mar 14 '18 at 23:10

14 Answers 14

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\$
5
\$\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\$
  • \$\begingroup\$ This is very clever :) \$\endgroup\$ – flawr Mar 15 '18 at 9:12
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\$
  • \$\begingroup\$ Can't you replace ;/ with F? ;-) \$\endgroup\$ – Erik the Outgolfer Mar 14 '18 at 22:16
  • \$\begingroup\$ @EriktheOutgolfer Lol, that was apparently left there as some kind of brainfart from a dev version \$\endgroup\$ – PurkkaKoodari Mar 14 '18 at 22:17
  • \$\begingroup\$ In fact, it made the code error in case of empty arrays. \$\endgroup\$ – Erik the Outgolfer Mar 14 '18 at 22:19
  • \$\begingroup\$ Will there ever be empty arrays? \$\endgroup\$ – PurkkaKoodari Mar 14 '18 at 22:19
  • \$\begingroup\$ Oh, and 1) your TIO link has a different code and 2) there are new quicks! \$\endgroup\$ – Erik the Outgolfer Mar 14 '18 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\$
  • 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\$ – Sriotchilism O'Zaic Mar 14 '18 at 22:23
  • \$\begingroup\$ @user56656 It indeed saves a byte, thanks! \$\endgroup\$ – totallyhuman Mar 15 '18 at 10:27
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\$

Wolfram Language (Mathematica), 27 bytes

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

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\$
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, privacy policy and cookie policy

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