Wer ist das Polygon?

14

Eine bequeme und nützliche Art, topologische Oberflächen darzustellen, ist die Verwendung eines Grundpolygons . Jede Seite eines Polygons stimmt mit einer anderen Seite überein und kann entweder parallel oder antiparallel sein. Das Hier ist zum Beispiel das Grundpolygon eines Torus :

Torus

Um herauszufinden, warum dies ein Torus ist, können wir uns vorstellen, dass unser Polygon ein Blatt Papier ist. Um die richtige Oberfläche zu erhalten, möchten wir unser Papier so biegen, dass die entsprechenden Kanten mit den Pfeilen in gleicher Richtung ausgerichtet sind. Für unser Torus-Beispiel können wir das Papier zunächst in einen Zylinder rollen, sodass die beiden blauen Ränder (mit b gekennzeichnet) verbunden sind. Jetzt nehmen wir unser Rohr und biegen es so, dass die beiden roten Kanten (mit a gekennzeichnet) miteinander verbunden sind. Wir sollten eine Donutform haben, auch Torus genannt.

Das kann etwas kniffliger werden. Wenn Sie versuchen, dasselbe mit dem folgenden Polygon zu tun, bei dem eine der Kanten in die entgegengesetzte Richtung zeigt:

Klein Flasche

Sie könnten in Schwierigkeiten geraten. Dies liegt daran, dass dieses Polygon die Klein-Flasche darstellt, die nicht in drei Dimensionen eingebettet werden kann. Hier ist ein Diagramm aus Wikipedia, das zeigt, wie Sie dieses Polygon in eine Klein-Flasche falten können:

Eine Klein-Flasche falten


Wie Sie vielleicht erraten haben, besteht die Aufgabe hier darin, ein grundlegendes Polygon zu nehmen und zu bestimmen, um welche Oberfläche es sich handelt. Für vierseitige Polygone (die einzigen Flächen, die Sie bearbeiten müssen) gibt es 4 verschiedene Flächen.

Sie sind

  • Torus

  • Klein Flasche

  • Kugel

  • Projektives Flugzeug

Dies ist keine daher erwarte ich nicht, dass Sie ein Bild als Eingabe verwenden. Stattdessen verwenden wir eine praktische Notation, um das grundlegende Polygon darzustellen. Möglicherweise haben Sie in den beiden obigen Beispielen bemerkt, dass ich die entsprechenden Kanten mit demselben Buchstaben (entweder a oder b) benannt und der verdrehten Kante eine zusätzliche Markierung gegeben habe, um ihre Verdrehung anzuzeigen. Wenn wir an der oberen Kante beginnen und die Beschriftung für jede Kante im Uhrzeigersinn notieren, erhalten wir eine Notation, die jedes grundlegende Polygon darstellt.

Zum Beispiel vorausgesetzt , dass der Torus würde abab und die Klein - Flasche würde abab . Für unsere Herausforderung werden wir es noch einfacher machen, anstatt verdrehte Kanten mit einem Negativ zu markieren, werden wir stattdessen diese Buchstaben groß schreiben.

Aufgabe

Bestimmen Sie anhand einer gegebenen Zeichenfolge, ob sie ein grundlegendes Polygon darstellt, und geben Sie einen Wert aus, der der richtigen Oberfläche entspricht. Sie müssen die Flächen nicht genau benennen, sondern benötigen nur 4 unterschiedliche Ausgabewerte, die jeweils eine der 4 Flächen darstellen, wobei ein fünfter Wert eine falsche Eingabe darstellt. Alle grundlegenden Fälle werden im Abschnitt Einfache Tests behandelt . Jedes Auto ist isomorph zu einem der oder ungültig.

Regeln

  • Seiten werden nicht immer mit a und b gekennzeichnet, aber sie werden immer mit Buchstaben gekennzeichnet.

  • Gültige Eingaben bestehen aus 4 Buchstaben, zwei von einem Typ und zwei von einem anderen. Sie müssen immer die richtige Oberfläche für eine gültige Eingabe ausgeben.

  • Sie sollten ungültige Eingaben ablehnen (keinen der 4 Werte ausgeben, die Oberflächen darstellen). Sie können alles tun, wenn Sie eine Eingabe ablehnen, solange diese von den 4 Oberflächen unterscheidbar ist

  • Dies ist daher besteht das Ziel darin, die Anzahl der Bytes in Ihrem Quellcode zu minimieren.

Tests

Einfache Tests

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

Schwierigere Tests

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
quelle
Warum ist ababein Torus und aabbeine Klein-Flasche?
Neil
@Neil ababist das Beispiel im ersten Absatz, Sie können dort nach einer Erklärung suchen. Hier ist ein Bild, das zeigt, warum aabbdas gleiche ist wie abAbbei einer Klein-Flasche.
Post Rock Garf Hunter
1
Welche schlechten Eingaben müssen wir behandeln und als schlecht identifizieren? Alle möglichen Saiten? Druckbares ASCII? Irgendwelche Längenbeschränkungen? Wenn wir eine Funktion schreiben, wird ihr möglicherweise ein Objekt übergeben, das keine Zeichenfolge ist? Wirklich, dieses ganze Geschäft mit der Eingabeverarbeitung scheint mir eine Herausforderung für Chamäleons zu sein.
21.
1
@ WheatWizard Kannst du das in diesem Fall bitte in Titel und Text klarstellen? Es liest sich bis zu Rules wie Mathematik und selbst dort ist es leicht, die Spieländerungsanforderung zu übersehen, um zu validieren, anstatt nur zu klassifizieren.
21.
2
Unabhängig davon fehlt meines Erachtens eine Erklärung dafür, warum ein String in eine bestimmte Kategorie eingeteilt wird, da Sie anscheinend nicht erwarten, dass die Leute die Mathematik hinter der Klassifizierung ausführen. Ich denke, ich könnte die Regeln aus Testfällen herausfinden, aber das ist alles andere als ideal.
21.

Antworten:

6

Netzhaut , 123 Bytes

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

Probieren Sie es online! Vielen Dank an @JonathanAllen für den Hinweis auf einen Fehler in meinem Code und auch für das Speichern einiger Bytes. Ich habe auch selbst ein paar Bytes mehr golfen, daher kann ich ihm keine bestimmte Zahl zuordnen. Erläuterung:

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

Wenn die ersten beiden Buchstaben gleich sind (Groß- und Kleinschreibung wird ignoriert), verschieben Sie den ersten Buchstaben auf den vierten. Dies reduziert die Anzahl der Fälle, die ich testen muss.

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

Wenn es nicht genau vier Buchstaben gibt oder die ersten beiden Buchstaben gleich sind oder die letzten beiden Buchstaben die ersten beiden nicht duplizieren, löschen Sie alles.

(..)\1
T

Der Torus ist der einfache Fall: ein Paar Buchstaben, wiederholter passender Fall.

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

Wenn einer der beiden Fälle übereinstimmt (in diesem Fall muss der andere Fall nicht übereinstimmen), handelt es sich um eine Klein-Flasche. Wenn das Paar mit der Groß- / Kleinschreibung übereinstimmt, aber umgekehrt ist, handelt es sich ebenfalls um eine Klein-Flasche.

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

Wenn andererseits das Paar umgekehrt ist, aber nur eines der Paare mit dem Fall übereinstimmt, dann ist das eine projektive Ebene.

i`(.)..\1
S

Und wenn das Paar umgekehrt ist, aber keiner der beiden Fälle entspricht, dann ist das eine Kugel. ( i`.(.)\1.würde auch funktionieren.)

....
P

Alles andere ist eine projektive Ebene.

Neil
quelle
1
@ JonathanAllan Danke für den Tipp; Hoffentlich hat diese Version eine bessere Validierung.
Neil
Wenn ich nur die Logik selbst ausarbeiten könnte: p
Jonathan Allan
1

Jelly , 52 51 58 Bytes

Bei +7 Bytes stellte ich fest, dass die Zuordnung, die ich verwendet hatte, für einige Szenarien (ohne Beispiel) mit Falländerungen nicht funktionierte.

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

Eine monadische Verknüpfung, die eine Zeichenfolge verwendet und die folgenden fünf unterschiedlichen, konsistenten Werte zurückgibt:

  • [-1,-1] - Ungültige Eingabe
  • [0,0] - Projektionsfläche
  • [1,0] - Klein Flasche
  • [2,0] - Kugel
  • [2,1] - Torus

Probieren Sie es online! oder sehen Sie die Testsuite an .

Wie?

Jedes grundlegende Polygon ist:

  • unverändert unter Drehung - man kann das Papier wie ein Lenkrad drehen
  • unverändert unter Reflektion - man kann das Papier umdrehen
  • unverändert unter case reverse - man kann as und As tauschen und / oder bs und Bs ohne Auswirkung tauschen - da wir die Richtungen angleichen wollen, ist das tatsächliche Etikett belanglos.

Als solche gibt es neun Äquivalenzklassen. Der Code erstellt Listen mit vier ganzen Zahlen, die jeweils ein Beispiel für eine der neun Äquivalenzklassen darstellen, erstellt die vier Rotationen von jeder, spiegelt jede von diesen wider und prüft dann, ob eine übersetzte Form der Eingabe in jeder Liste vorhanden ist. Die Klassen sind geordnet P,P,P,K,K,K,S,S,T, dh die 0-basierte Index-Ganzzahl dividiert durch jede der [3,8]Ausbeuten ergibt die vier gültigen Ausgaben (die Indexierung basiert auf 1 und das Atom ekehrt 0bei Nichtexistenz zurück, also subtrahieren 1und ganzzahlig dividieren durch jede der [3,8]Ausbeuten [-1,-1]für den ungültigen Fall ).

“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]

Hinweis: 11 bytes ( ŒlĠL€⁼2,2ȧ⁸) validieren nur die Eingabezeichenfolge als korrekt - ohne diesen Code wird jeder Beispielfall bestanden, mit der Ausnahme, dass dies ab1awie abBaeine projektive Ebene ausgewertet wird .

Jonathan Allan
quelle