12
\$\begingroup\$

This question is an extension of Who's that Polygon? to arbitrary numbers of sides.

A fundamental polygon for a surface is an polygon with a prescribed pairing for all its \$2n\$ sides, each marked with an arrow, such that identifying the sides according to this pairing and the arrow directions produces the surface (up to homeomorphism).

This pairing can be described as a cyclic fundamental word with two each of \$n\$ distinct symbols, where any symbol may be inverted to represent an arrow pointing opposite to the direction of travel around the polygon. For example, the word \$abab^{-1}\$ describes the Klein bottle:

In light of the classification theorem for surfaces, which states that every closed 3D surface is homeomorphic to either the connect-sum of \$g\ge0\$ tori (including the sphere at \$g=0\$) or the connect-sum of \$k>0\$ cross-caps, it may not be immediately obvious what surface a fundamental polygon represents. Fortunately canonical forms and a canonicalisation process exist – the material below comes from Gerhard Ringel's Map Color Theorem.

Canonical words for surfaces

The canonical fundamental word for the connect-sum of \$g\ge0\$ tori, with genus \$g\$, is $$a_1b_1a_1^{-1}b_1^{-1}a_2b_2a_2^{-1}b_2^{-1}\dots a_gb_ga_g^{-1}b_g^{-1}$$ So the sphere's canonical word is the empty string, the normal torus's is \$aba^{-1}b^{-1}\$ and so on.

The canonical fundamental word for the connect-sum of \$k>0\$ cross-caps, with genus \$-k\$ (although this is incorrect, this definition is used here because then the integers bijectively correspond to surface types) is $$a_1a_1a_2a_2\dots a_ka_k$$ The real projective plane and Klein bottle are the \$k=1\$ and \$k=2\$ cases of this sequence, so their canonical words are \$aa\$ and \$aabb\$ respectively.

Canonicalisation

The surface represented by a fundamental word is unchanged if

  • the word is cyclically rotated: \$aabb\to abba\$
  • a symbol is inverted: \$aabb\to aab^{-1}b^{-1}\$
  • a symbol and its adjacent inverse are cancelled: \$caba^{-1}b^{-1}c^{-1}\to aba^{-1}b^{-1}\$

The surface is orientable iff each symbol appears once inverted and once uninverted in the word. In that case a "handle" can be extracted by the following word transformation, where \$Q,R,S\$ are not all empty: $$PaQbRa^{-1}Sb^{-1}T\to PSRQTaba^{-1}b^{-1}$$ Repeating this process with intermediate cancellation leads to the canonical form for orientable surfaces described above.

If the two occurrences of a symbol are both inverted or both uninverted, the surface is non-orientable. In this case a cross-cap may be extracted by the following word transformation, where \$Q^{-1}\$ is the group-theoretic inverse (so e.g. \$(abc)^{-1}=c^{-1}b^{-1}a^{-1}\$): $$PaQaR\to aaPQ^{-1}R$$ Do this as many times as possible to get a word of the form \$a_1a_1\dots a_ia_iO\$, where \$O\$ is the fundamental word of an orientable surface. Canonicalise \$O\$ as above and determine its genus \$g\$; the canonical form of the full non-invertible surface is then \$a_1a_1\dots a_{i+2g}a_{i+2g}\$, because a handle turns into two cross-caps in the presence of another cross-cap.

Example

This picture from one of my MathsSE answers is an embedding of the Johnson graph \$J(5,2)\$:

The star-shaped border represents a fundamental polygon where

  • each black (dark blue) arc matches the grey (light blue) arc 5 steps away going counterclockwise
  • each golden yellow arc matches the light yellow arc 7 steps away going clockwise
  • in all cases the matching is parallel (as hinted by the faded exterior), so the surface is orientable

Thus the corresponding fundamental word is $$ah^{-1}bf^{-1}ca^{-1}db^{-1}ei^{-1}fd^{-1}ge^{-1}hc^{-1}ig^{-1}$$ which reduces as follows: $$(a)h^{-1}(b)f^{-1}c(a^{-1})d(b^{-1})ei^{-1}fd^{-1}ge^{-1}hc^{-1}ig^{-1}$$ $$\to (d)f^{-1}(c)h^{-1}ei^{-1}f(d^{-1})ge^{-1}h(c^{-1})ig^{-1}aba^{-1}b^{-1}$$ $$\to ge^{-1}[hh^{-1}]ei^{-1}[ff^{-1}]ig^{-1}aba^{-1}b^{-1}dcd^{-1}c^{-1}$$ $$\to g[e^{-1}e][i^{-1}i]g^{-1}aba^{-1}b^{-1}dcd^{-1}c^{-1}$$ $$\to[gg^{-1}]aba^{-1}b^{-1}dcd^{-1}c^{-1}$$ $$\to aba^{-1}b^{-1}dcd^{-1}c^{-1}$$ Thus the surface has genus 2, which matched my expectation when I constructed the embedding based on a triangulation with 10 vertices and 36 edges – by Euler's formula such a triangular embedding, if orientable, must live on the genus-2 surface. Indeed (glue the three ends of the open surface below in a Y-shape so that the colours match):

Task

Given a list of nonzero integers where the magnitudes from 1 to \$n\$ appear exactly twice each, representing a fundamental word with a negative number marking an inverted symbol, output the genus of the surface corresponding to that fundamental word, using the definition above where a negative genus \$-k\$ means "connect-sum of \$k\$ cross-caps".

This is ; fewest bytes wins.

Test cases

[] -> 0
[1, -1] -> 0
[1, 1] -> -1
[1, 2, -2, -1] -> 0
[1, 2, -1, -2] -> 1
[1, 2, 1, -2] -> -2
[1, 2, 1, 2] -> -1
[-2, -2, -1, 1] -> -1
[1, 2, 3, -1, -2, -3] -> 1
[-3, 1, 3, -2, 1, 2] -> -2
[1, 2, 3, 4, -1, -2, -3, -4] -> 2
[1, 2, 4, 4, -2, -3, 1, -3] -> -2
[1, -8, 2, -6, 3, -1, 4, -2, 5, -9, 6, -4, 7, -5, 8, -3, 9, -7] -> 2
[1, -8, 2, -9, 3, -1, 4, -2, 5, -3, 6, -4, 7, -5, 8, -6, 9, -7] -> 3
[4, 3, 2, 1, 1, 2, 3, 4] -> -4
[3, 4, 1, 2, 6, 7, -4, 5, -2, -3, -7, -1, -5, -6] -> 3
[1, 2, 3, 3, -1, -2] -> -3
\$\endgroup\$
0

2 Answers 2

5
\$\begingroup\$

Curry (PAKCS), 159 bytes

f[]=0
f(p++a:b:q)|a+b==0=f$p++q
f(p++a:q++a:r)=g$f$p++reverse[-x|x<-q]++r
f(p++a:q++b:r++c:s++d:t)=(a+c)!(b+d)$f$p++s++r++q++t
g x=min(-2*x)x-1
(0!0)x|x>=0=x+1

Attempt This Online!

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

Vyxal, 56 49 46 bytes

(ṫ~c[€ɖ‡ṘNf&›|p;ȧ:(ṫ€:ḣt↔h:ḃ∇v€ÞfḣṘJf)W∑¥[d¥+N

Try it Online!

First we extract all cross-caps. This is done by looking at the last symbol. If it occurs in the same orientation twice, the cross-cap is extracted by taking a word \$PaQa\$ and transforming it into \$PQ^{-1}\$, incrementing the register each time it happens. Otherwise the word is rotated to the left. This is repeated as many times as the number of symbols in the input.

(ṫ~c[€ɖ‡ṘNf&›|p;
(              ; # run the following once for each symbol in the input:
                                               [1, 2, 3, 1, -2, 3]
 ṫ               #   tail extract              [1, 2, 3, 1, -2], 3
  ~c             #   contains? without popping [1, 2, 3, 1, -2], 3, 1
    [            #   if:
     €           #     split on                [[1, 2], [1, -2]]
      ɖ‡--       #     apply the following to the second item:
        ṘN       #       reverse and negate
                                               [[1, 2], [2, -1]]
          f      #     flatten                 [1, 2, 2, -1]
           &›    #     increment register
             |   #   else:
              p  #     prepend

Now we are left with a word of an orientable surface so we can forget which symbols are inverted.

Now we extract handles and remove adjacent inverses. This is done by looking at the last symbol. We write the word as \$PaQa\$. If there is a common symbol in \$P\$ and \$Q\$ there exists a handle \$RbSaTbUa\$ so we transform the word into \$RUTS\$, leaving a 1 on the stack each time it happens. If there are no common symbols in \$P\$ and \$Q\$ then \$a\$ will eventually become adjacent with itself so we can delete it, leaving a 0 on the stack each time it happens. This is repeated as many times as the number symbols left in the word after extracting cross-caps.

ȧ:(ṫ€:ḣt↔h:ḃ∇v€ÞfḣṘJf)
ȧ                      # absolute value
 :(                  ) # run the following once for each symbol in the word:
   ṫ                   #   tail extract
    €                  #   split on
     :                 #   duplicate
      ḣ                #   head extract
       t               #   tail
        ↔              #   intersection
         h             #   head
          :            #   duplicate
           ḃ           #   boolify
            ∇          #   shift (leave it on the stack for later)
             v€        #   vectorise split on
               Þf      #   flatten by one level
                 ḣ     #   head extract
                  Ṙ    #   reverse
                   Jf  #   join and flatten

All that's left is to combine the number of cross-caps extracted and number of handles extracted.

W∑¥[d¥+N
W        # wrap stack in a list
 ∑       # sum
  ¥[     # if register is non-zero
    d    #   double
     ¥+  #   add register
       N #   negate
\$\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.