Kim jest ten wielokąt?

14

Wygodnym i użytecznym sposobem przedstawienia powierzchni topologicznych jest fundamentalny wielokąt . Każda strona wielokąta jest dopasowana do innej strony i może być równoległa lub antyrównoległa. Na przykład tutaj jest podstawowy wielokąt torusa :

Torus

Aby dowiedzieć się, dlaczego jest to torus, możemy sobie wyobrazić, że naszym wielokątem jest kartka papieru. Aby uzyskać odpowiednią powierzchnię, chcemy wygiąć papier, tak aby odpowiadające mu krawędzie zrównały się ze strzałkami w tę samą stronę. W naszym przykładzie torusa możemy zacząć od zrolowania papieru do cylindra, aby połączyć dwie niebieskie krawędzie (oznaczone b). Teraz bierzemy naszą rurkę i wyginamy ją tak, aby dwie czerwone krawędzie (oznaczone a) łączyły się ze sobą. Powinniśmy mieć kształt pączka, zwany także torusem.

Może to być nieco trudniejsze. Jeśli spróbujesz zrobić to samo z następującym wielokątem, w którym jedna z krawędzi biegnie w przeciwnym kierunku:

Butelka Kleina

możesz mieć kłopoty. Wynika to z faktu, że ten wielokąt reprezentuje butelkę Kleina, której nie można osadzić w trzech wymiarach. Oto schemat z wikipedii pokazujący, jak możesz złożyć ten wielokąt w butelkę Kleina:

Składanie butelki Kleina


Jak można się domyślać, zadaniem tutaj jest wzięcie podstawowego wielokąta i określenie, która to powierzchnia. W przypadku wielokątów czworokątnych (jedyne powierzchnie, które będziesz musiał obsługiwać) istnieją 4 różne powierzchnie.

Oni są

  • Torus

  • Butelka Kleina

  • Kula

  • Samolot projekcyjny

Teraz nie jest to więc nie oczekuję, że weźmiesz obraz jako dane wejściowe, zamiast tego użyjemy wygodnej notacji do przedstawienia podstawowego wielokąta. Być może zauważyłeś w dwóch powyższych przykładach, że nazwałem odpowiednie krawędzie tą samą literą (albo a lub b) i że nadałem skręconej krawędzi dodatkowy znak, aby pokazać jej skręcenie. Jeśli zaczniemy od górnej krawędzi i zapiszemy etykietę dla każdej krawędzi, postępując zgodnie z ruchem wskazówek zegara, możemy otrzymać notację reprezentującą każdy fundamentalny wielokąt.

Na przykład Torus warunkiem staną abab a Bottle Klein staną abab . Dla naszego wyzwania sprawimy, że będzie to jeszcze prostsze, zamiast oznaczać skręcone krawędzie znakiem minus, zamiast tego litery te będą pisane wielką literą.

Zadanie

Biorąc pod uwagę ciąg, określ, czy reprezentuje on podstawowy wielokąt, i wypisz wartość odpowiadającą jego właściwej powierzchni. Nie trzeba dokładnie nazywać powierzchni, wystarczy 4 wyjściowe odrębne wartości, każda reprezentująca jedną z 4 powierzchni, a piąta wartość reprezentuje nieprawidłowe dane wejściowe. Wszystkie podstawowe przypadki są omówione w części Proste testy , każdy samochód będzie izomorficzny w stosunku do jednego lub nieważny.

Zasady

  • Strony nie zawsze będą oznaczone a i b, ale zawsze będą oznaczone literami.

  • Prawidłowe dane wejściowe będą się składały z 4 liter, dwóch jednego typu i dwóch innych. Zawsze należy wyprowadzać poprawną powierzchnię dla poprawnego wprowadzania.

  • Należy odrzucić (nie wypisać żadnej z 4 wartości reprezentujących powierzchnie) nieprawidłowe dane wejściowe. Możesz zrobić wszystko, odrzucając dane wejściowe, o ile można je odróżnić od 4 powierzchni

  • To jest więc celem jest zminimalizowanie liczby bajtów w kodzie źródłowym.

Testy

Proste testy

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

Trudniejsze testy

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
źródło
Dlaczego ababtorus i aabbbutelka Kleina?
Neil,
@ Neil ababjest przykładem z pierwszego akapitu, możesz tam znaleźć wyjaśnienie. Oto obraz pokazujący, dlaczego aabbjest taki sam, jak abAbbutelka Kleina.
Post Rock Garf Hunter
1
Jakie złe dane musimy traktować i zidentyfikować jako złe? Wszystkie możliwe ciągi znaków? ASCII do druku? Jakieś ograniczenia długości? Jeśli napiszemy funkcję, to czy może ona zostać przekazana do obiektu niebędącego łańcuchem? Naprawdę cały ten proces przetwarzania danych wejściowych wydaje mi się wyzwaniem dla kameleona.
xnor
1
@WheatWizard W takim przypadku, czy możesz to wyjaśnić w tytule i treści? Czyta to przez matematykę aż do reguł, a nawet tam łatwo jest przeoczyć wymóg zmiany gry, aby sprawdzić, a nie tylko sklasyfikować.
xnor
2
Osobno wydaje mi się, że brakuje wyjaśnienia, co sprawia, że ​​ciąg należy zaklasyfikować do danej kategorii, ponieważ wydaje się, że nie oczekujesz, że ludzie będą robić matematykę za klasyfikacją. Wydaje mi się, że potrafiłbym ustalić zasady z przypadków testowych, ale nie jest to idealne rozwiązanie.
xnor

Odpowiedzi:

6

Siatkówka , 123 bajty

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

Wypróbuj online! Dzięki @JonathanAllen za wskazanie błędu w moim kodzie, a także za zapisanie niektórych bajtów; Grałem też w trochę więcej bajtów, więc nie mogę mu przypisać określonej liczby. Wyjaśnienie:

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

Jeśli dwie pierwsze litery są takie same (ignorując wielkość liter), przenieś pierwszą literę na czwartą. Zmniejsza to liczbę przypadków, które muszę przetestować.

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

Jeśli nie ma dokładnie czterech liter lub dwie pierwsze litery są takie same lub dwie ostatnie litery nie duplikują pierwszych dwóch, usuń wszystko.

(..)\1
T

Torus jest łatwym przypadkiem: para liter, powtarzająca się wielkość liter.

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

Jeśli jedna z par pasuje do skrzynki (w którym to przypadku druga para musi niedopasować skrzynkę), to jest to butelka Kleina. Alternatywnie, jeśli para pasuje do wielkości liter, ale jest odwrócona, oznacza to również butelkę Kleina.

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

Jeśli z drugiej strony para jest odwrócona, ale tylko jedna z nich pasuje do wielkości liter, oznacza to, że jest to płaszczyzna rzutowa.

i`(.)..\1
S

A jeśli para jest odwrócona, ale nie pasuje do wielkości liter, to jest to kula. ( i`.(.)\1.również by działało.)

....
P

Cała reszta to płaszczyzna rzutowa.

Neil
źródło
1
@JonathanAllan Dzięki za wskazówkę; mam nadzieję, że ta wersja ma lepszą walidację.
Neil
Gdybym tylko mógł sam wypracować logikę: p
Jonathan Allan
1

Galaretka , 52 51 58 bajtów

+7 bajtów, odkryłem, że mapowanie, którego użyłem, nie działało w niektórych (poza przykładowych) scenariuszach zmiany wielkości liter.

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

Monadyczny link pobierający ciąg znaków i zwracający pięć następujących spójnych wartości:

  • [-1,-1] - nieprawidłowe wejście
  • [0,0] - płaszczyzna rzutowa
  • [1,0] - Butelka Kleina
  • [2,0] - kula
  • [2,1] - torus

Wypróbuj online! lub zobacz pakiet testowy .

W jaki sposób?

Każdy fundamentalny wielokąt to:

  • niezmieniony podczas obrotu - można obrócić papier jak kierownicę
  • niezmieniony pod odbiciem - można przewrócić papier
  • niezmienione w przypadku odwrócenia przypadku - można zamienić as i Asi i / lub bsw i Bs bez efektu - ponieważ chcemy dopasować kierunki, w których rzeczywista etykieta jest nieistotna.

Jako takie istnieje dziewięć klas równoważności. Kod tworzy listy czterech liczb całkowitych, z których każda reprezentuje przykład jednej z dziewięciu klas równoważności, tworzy cztery obroty każdej z nich, odzwierciedla każdą z nich, a następnie sprawdza, czy na każdej liście istnieje przetłumaczona postać danych wejściowych. Klas są sortowane P,P,P,K,K,K,S,S,T, więc przyjmując całkowitą indeks 0 opartych podzieloną przez każdy z [3,8]wydajnością czterech poprawnych wyników (indeksowania 1 opartych i atom epowraca 0do nieistnienie tak odjęcie 1i całkowitą podzielenie przez każdy z [3,8]wydajnością [-1,-1]dla nieprawidłowej przypadku ).

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

Uwaga: 11 bajtów ( ŒlĠL€⁼2,2ȧ⁸) sprawdza tylko poprawność wejściowego ciągu znaków - bez tego kodu każdy przykładowy przypadek przechodzi, z wyjątkiem tego, że ab1ajest oceniany tak, jakby był abBapłaszczyzną rzutową.

Jonathan Allan
źródło