Qui est ce polygone?

14

Un moyen pratique et utile de représenter des surfaces topologiques est d'utiliser un polygone fondamental . Chaque côté d'un polygone correspond à un autre côté et peut être parallèle ou anti-parallèle. Par exemple, voici le polygone fondamental d'un tore :

Torus

Pour comprendre pourquoi il s'agit d'un tore, nous pourrions imaginer que notre polygone est une feuille de papier. Pour faire la bonne surface, nous voulons plier notre papier afin que les bords correspondants soient alignés avec leurs flèches dans le même sens. Pour notre exemple de tore, nous pouvons commencer par rouler le papier dans un cylindre afin que les deux bords bleus (étiquetés b) soient connectés. Maintenant, nous prenons notre tube et le plions de sorte que les deux bords rouges (étiquetés a) se connectent l'un à l'autre. Nous devrions avoir une forme de beignet, également appelée tore.

Cela peut devenir un peu plus délicat. Si vous essayez de faire de même avec le polygone suivant où l'une des arêtes va dans la direction opposée:

Bouteille Klein

vous pourriez avoir des ennuis. En effet, ce polygone représente la bouteille de Klein qui ne peut pas être incrustée en trois dimensions. Voici un diagramme de wikipedia montrant comment vous pouvez plier ce polygone en une bouteille de Klein:

Plier une bouteille Klein


Comme vous l'avez peut-être deviné, la tâche consiste à prendre un polygone fondamental et à déterminer de quelle surface il s'agit. Pour les polygones à quatre côtés (les seules surfaces que vous devrez manipuler), il existe 4 surfaces différentes.

Elles sont

  • Torus

  • Bouteille Klein

  • Sphère

  • Plan projectif

Maintenant, ce n'est pas donc je ne m'attends pas à ce que vous preniez une image en entrée à la place, nous utiliserons une notation pratique pour représenter le polygone fondamental. Vous avez peut-être remarqué dans les deux exemples ci-dessus que j'ai nommé les bords correspondants avec la même lettre (a ou b), et que j'ai donné au bord torsadé une marque supplémentaire pour montrer son torsion. Si nous commençons au bord supérieur et notons l'étiquette pour chaque bord dans le sens des aiguilles d'une montre, nous pouvons obtenir une notation qui représente chaque polygone fondamental.

Par exemple, le Torus fourni deviendrait abab et la bouteille Klein deviendrait ab - ab . Pour notre défi, nous allons le rendre encore plus simple, au lieu de marquer les bords torsadés avec un négatif, nous allons plutôt mettre ces lettres en majuscule.

Tâche

Étant donné une chaîne, déterminez si elle représente un polygone fondamental et affichez une valeur correspondant à la surface appropriée de celui-ci. Vous n'avez pas besoin de nommer les surfaces exactement, vous avez juste besoin de 4 valeurs distinctes de sortie représentant chacune l'une des 4 surfaces avec une cinquième valeur représentant une entrée incorrecte. Tous les cas de base sont traités dans les tests simples section , chaque voiture sera isomorphe à l'un des ou invalide.

Règles

  • Les côtés ne seront pas toujours étiquetés avec a et b, mais ils seront toujours étiquetés avec des lettres.

  • Une entrée valide se composera de 4 lettres, deux d'un type et deux d'un autre. Vous devez toujours sortir la surface correcte pour une entrée valide.

  • Vous devez rejeter (ne pas afficher l'une des 4 valeurs représentant les surfaces) une entrée non valide. Vous pouvez faire n'importe quoi lorsque vous rejetez une entrée, tant qu'elle est distincte des 4 surfaces

  • C'est du donc l'objectif est de minimiser le nombre d'octets dans votre code source.

Les tests

Tests simples

abab Torus
abAb Klein Bottle
abaB Klein Bottle
abAB Projective Plane
aabb Klein Bottle
aAbb Projective Plane
aabB Projective Plane
aAbB Sphere
abba Klein Bottle
abBa Projective Plane
abbA Projective Plane
abBA Sphere

Des tests plus difficiles

ABAB  Torus
acAc  Klein Bottle
Emme  Projective Plane
zxXZ  Sphere
aaab  Bad input
abca  Bad input
abbaa Bad input
ab1a  Bad input
Post Rock Garf Hunter
la source
Pourquoi ababun tore et aabbune bouteille Klein?
Neil
@Neil ababest l'exemple du premier paragraphe, vous pouvez y chercher une explication. Voici une image montrant pourquoi aabbest la même que celle abAbqui est une bouteille Klein.
Post Rock Garf Hunter
1
Quelles mauvaises entrées devons-nous gérer et identifier comme mauvaises? Toutes les chaînes possibles? ASCII imprimable? Des limites de longueur? Si nous écrivons une fonction, pourrait-on lui passer un objet non chaîne? Vraiment, toute cette entreprise de traitement des entrées me semble être un défi pour les caméléons.
xnor
1
@WheatWizard Dans ce cas, pouvez-vous préciser cela dans le titre et le corps? Cela se lit comme des mathématiques jusqu'aux règles, et même là, il est facile de manquer l'exigence de changement de jeu pour valider plutôt que simplement classer.
xnor
2
Séparément, je pense qu'il manque une explication de ce qui fait qu'une chaîne est classée dans une catégorie donnée, car vous ne semblez pas vous attendre à ce que les gens fassent le calcul derrière la classification. Je pense que je pourrais dérober les règles des cas de test, mais c'est loin d'être idéal.
xnor

Réponses:

6

Rétine , 123 octets

i`(.)(\1..)
$2$1
iG`^([a-z])(?!\1)([a-z])(\1\2|\2\1)$
(..)\1
T
.*(.).\1.*|(.)(.)\3\2
B
(.)..\1|.(.)\2.
P
i`(.)..\1
S
....
P

Essayez-le en ligne! Merci à @JonathanAllen d'avoir signalé un bogue dans mon code et aussi comment économiser quelques octets; J'ai également joué au golf quelques octets de plus, donc je ne peux pas lui attribuer un chiffre spécifique. Explication:

i`(.)(\1..)
$2$1

Si les deux premières lettres sont identiques (en ignorant la casse), placez la première lettre en quatrième position. Cela réduit le nombre de cas que je dois tester.

iG`^([a-z])(?!\1)([a-z])(\1\2|\2\1)$

S'il n'y a pas exactement quatre lettres, ou si les deux premières lettres sont identiques, ou si les deux dernières lettres ne dupliquent pas les deux premières, supprimez tout.

(..)\1
T

Le tore est le cas facile: une paire de lettres, un cas de correspondance répété.

.*(.).\1.*|(.)(.)\3\2
B

Si l'une des paires correspond au boîtier (auquel cas l'autre de la paire doit ne pas correspondre au boîtier), il s'agit d'une bouteille de Klein. Alternativement, si la paire correspond au boîtier mais est inversée, il s'agit également d'une bouteille de Klein.

(.)..\1|.(.)\2.
P

Si par contre la paire est inversée, mais qu'une seule de la paire correspond au cas, alors c'est un plan projectif.

i`(.)..\1
S

Et si la paire est inversée mais ne correspond pas à la casse, alors c'est une sphère. ( i`.(.)\1.fonctionnerait également.)

....
P

Tout le reste est un plan projectif.

Neil
la source
1
@JonathanAllan Merci pour l'astuce; j'espère que cette version a une meilleure validation.
Neil
Si seulement je pouvais trouver la logique moi-même: p
Jonathan Allan
1

Gelée , 52 51 58 octets

+7 octets, j'ai trouvé que le mappage que j'avais utilisé ne fonctionnait pas pour certains scénarios (hors exemple) de changement de cas.

“nḲ⁾⁶ƥ¦ṃṗḋ’b4s4‘µṙJ;U$µ€
,ŒsṢÞṪµŒlĠL€⁼2,2ȧ⁸i@€ṢeЀ¢TṪ’:3,8

Un lien monadique prenant une chaîne et renvoyant les cinq valeurs distinctes et cohérentes suivantes:

  • [-1,-1] - entrée invalide
  • [0,0] - plan projectif
  • [1,0] - Bouteille Klein
  • [2,0] - sphère
  • [2,1] - tore

Essayez-le en ligne! ou consultez la suite de tests .

Comment?

Tout polygone fondamental est:

  • inchangé en rotation - on peut tourner le papier comme un volant
  • inchangé à la réflexion - on peut retourner le papier
  • inchangé en cas d'inversion de cas - on peut échanger as et As et / ou échanger bs et Bs sans effet - car nous voulons faire correspondre les directions de l'étiquette réelle est sans conséquence.

À ce titre, il existe neuf classes d'équivalence. Le code crée des listes de quatre entiers représentant chacun un exemple de l'une des neuf classes d'équivalence, crée les quatre rotations de chacune, reflète chacune d'elles et vérifie ensuite si une forme traduite de l'entrée existe dans chaque liste. Les classes sont ordonnées P,P,P,K,K,K,S,S,T, donc en prenant l'entier d'index basé sur 0 divisé par chacun des [3,8]rendements, les quatre sorties valides (l'indexation est basée sur 1 et l'atome erevient 0pour la non-existence, donc soustraire 1et diviser l'entier par chacun des [3,8]rendements [-1,-1]pour le cas invalide ).

“nḲ⁾⁶ƥ¦ṃṗḋ’b4s4‘µṙJ;U$µ€ - Link 1, symmetries of the 9 equivalence classes: no arguments
“nḲ⁾⁶ƥ¦ṃṗḋ’              - base 250 number                 1704624888339951310984
           b4            - convert to base 4               [1,1,3,0,1,2,2,0,1,2,3,0,0,2,2,0,1,3,1,0,2,1,2,0,2,3,1,0,3,1,2,0,2,0,2,0]
             s4          - split into 4s                   [[1,1,3,0],[1,2,2,0],[1,2,3,0],[0,2,2,0],[1,3,1,0],[2,1,2,0],[2,3,1,0],[3,1,2,0],[2,0,2,0]]
               ‘         - increment (vectorises)          [[2,2,4,1],[2,3,3,1],[2,3,4,1],[1,3,3,1],[2,4,2,1],[3,2,3,1],[3,4,2,1],[4,2,3,1],[3,1,3,1]]
                µ     µ€ - for €ach:                       ...e.g. [2,2,4,1]:
                  J      -   range of length               [1,2,3,4]
                 ṙ       -   rotate left by (vectorises)   [[2,4,1,2],[4,1,2,2],[1,2,2,4],[2,2,4,1]]
                     $   -   last two links as a monad:
                    U    -     upend (reverse each)        [[2,1,4,2],[2,2,1,4],[4,2,2,1],[1,4,2,2]]
                   ;     -     concatenate                 [[2,4,1,2],[4,1,2,2],[1,2,2,4],[2,2,4,1],[2,1,4,2],[2,2,1,4],[4,2,2,1],[1,4,2,2]]

,ŒsṢÞṪµŒlĠL€⁼2,2ȧ⁸i@€ṢeЀ¢TṪ’:3,8 - Main link: string s      e.g. "xOxO"
 Œs                               - swap case                     "XoXo"
,                                 - pair with s                   ["xOxO","XoXo"]
    Þ                             - sort by:
   Ṣ                              -   sort                        ["xOxO","XoXo"]
     Ṫ                            - tail                          "XoXo"
      µ                           - monadic chain separation, call that v
       Œl                         - convert to lowercase          "xoxo"
         Ġ                        - group indices by value        [[2,4],[1,3]]
          L€                      - length of each                [2,2]
             2,2                  - 2 pair 2                      [2,2]
            ⁼                     - equal? (1 if so, 0 if not)    1
                 ⁸                - link's left argument, v       "XoXo"
                ȧ                 - and (v if equal, 0 if not)    "XoXo"
                     Ṣ            - sort v                        "XoXo"
                  i@€             - first index for €ach          [1,3,1,3]
                         ¢        - call the last link (1) as a nilad
                       Ѐ         - map over right:
                      e           -   exists in?                  [0,0,0,0,0,0,0,0,1]
                          T       - truthy indexes                [                9]
                           Ṫ      - tail (empty list yields 0)    9
                            ’     - decrement                     8
                              3,8 - 3 pair 8                      [3,8]
                             :    - integer division (vectorises) [2,1]

Remarque: 11 octets ( ŒlĠL€⁼2,2ȧ⁸) valident uniquement la chaîne d'entrée comme étant de la forme correcte - sans ce code, chaque cas d'exemple passe sauf qu'il ab1aest évalué comme s'il s'agissait d' abBaun plan projectif.

Jonathan Allan
la source