¿Quién es ese polígono?

14

Una forma conveniente y útil de representar superficies topológicas es con un polígono fundamental . Cada lado de un polígono coincide con otro lado y puede ser paralelo o antiparalelo. Por ejemplo, el aquí es el polígono fundamental de un toro :

Toro

Para descubrir por qué esto es un toro, podríamos imaginar que nuestro polígono es una hoja de papel. Para hacer la superficie adecuada, queremos doblar nuestro papel para que los bordes correspondientes se alineen con sus flechas en la misma dirección. Para nuestro ejemplo de toro, podemos comenzar enrollando el papel en un cilindro para que los dos bordes azules (etiquetados como b) estén conectados. Ahora tomamos nuestro tubo y lo doblamos para que los dos bordes rojos (etiquetados como a) se conecten entre sí. Deberíamos tener forma de rosquilla, también llamada toro.

Esto puede ser un poco más complicado. Si intenta hacer lo mismo con el siguiente polígono donde uno de los bordes va en la dirección opuesta:

Botella Klein

puede que te encuentres en problemas. Esto se debe a que este polígono representa la botella de Klein que no se puede incrustar en tres dimensiones. Aquí hay un diagrama de Wikipedia que muestra cómo puedes doblar este polígono en una botella de Klein:

Doblar una botella de Klein


Como habrás adivinado, la tarea aquí es tomar un polígono fundamental y determinar qué superficie es. Para los polígonos de cuatro lados (las únicas superficies que deberá manejar) hay 4 superficies diferentes.

Son

  • Toro

  • Botella Klein

  • Esfera

  • Plano proyectivo

Ahora, esto no es así que no espero que tomes una imagen como entrada, en su lugar usaremos una notación conveniente para representar el polígono fundamental. Es posible que haya notado en los dos ejemplos anteriores que nombré los bordes correspondientes con la misma letra (ya sea aob), y que le di al borde torcido una marca adicional para mostrar su torcido. Si comenzamos en el borde superior y escribimos la etiqueta para cada borde a medida que avanzamos, podemos obtener una notación que representa cada polígono fundamental.

Por ejemplo, el Torus proporcionado se convertiría en abab y la Botella Klein se convertiría en ab - ab . Para nuestro desafío, lo haremos aún más simple, en lugar de marcar los bordes retorcidos con un negativo, haremos que esas letras se pongan en mayúscula.

Tarea

Dada una cadena, determine si representa un polígono fundamental y genere un valor que corresponda a la superficie adecuada del mismo. No necesita nombrar las superficies exactamente, solo necesita 4 valores distintos de salida, cada uno de los cuales representa una de las 4 superficies con un quinto valor que representa una entrada incorrecta. Todos los casos básicos están cubiertos en la sección de Pruebas simples , cada automóvil será isomorfo a uno de los o inválido.

Reglas

  • Los lados no siempre se etiquetarán con a y b, pero siempre se etiquetarán con letras.

  • La entrada válida constará de 4 letras, dos de un tipo y dos de otro. Siempre debe generar la superficie correcta para una entrada válida.

  • Debe rechazar (no emitir ninguno de los 4 valores que representan superficies) entradas no válidas. Puede hacer cualquier cosa al rechazar una entrada, siempre que sea distinguible de las 4 superficies

  • Este es el por lo que el objetivo es minimizar el número de bytes en su código fuente.

Pruebas

Pruebas 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

Pruebas más difíciles

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
fuente
¿Por qué hay ababun toro y aabbuna botella de Klein?
Neil
@Neil ababes el ejemplo en el primer párrafo, puede buscar una explicación. Aquí hay una imagen que muestra por qué aabbes lo mismo abAbque una botella de Klein.
Post Rock Garf Hunter
1
¿Qué entradas malas tenemos que manejar e identificar como malas? Todas las cadenas posibles? ASCII imprimible? ¿Algún límite de longitud? Si escribimos una función, ¿podría pasarle un objeto que no sea de cadena? Realmente, todo este negocio de procesamiento de insumos me parece un desafío de camaleón.
xnor
1
@WheatWizard En ese caso, ¿puedes dejar eso claro en el título y el cuerpo? Se lee como matemáticas hasta las Reglas, e incluso allí es fácil pasar por alto el requisito de cambio de juego para validar en lugar de simplemente clasificar.
xnor
2
Por separado, creo que falta una explicación de lo que hace que una cadena se clasifique en una categoría dada, ya que parece que no se espera que las personas hagan los cálculos matemáticos detrás de la clasificación. Creo que podría descifrar las reglas de los casos de prueba, pero eso está lejos de ser ideal.
xnor

Respuestas:

6

Retina , 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

Pruébalo en línea! Gracias a @JonathanAllen por señalar un error en mi código y también cómo guardar algunos bytes; También jugué algunos bytes más, así que no puedo darle crédito por una cifra específica. Explicación:

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

Si las dos primeras letras son iguales (ignorando mayúsculas y minúsculas), mueva la primera letra para ser la cuarta. Esto reduce la cantidad de casos que necesito probar.

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

Si no hay exactamente cuatro letras, o las dos primeras letras son iguales, o las dos últimas letras no duplican las dos primeras, elimine todo.

(..)\1
T

El toro es el caso fácil: un par de letras, caso coincidente repetido.

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

Si uno de los pares coincide con mayúsculas y minúsculas (en cuyo caso otro del par no coincide), entonces esa es una botella de Klein. Alternativamente, si el par coincide con el caso pero se invierte, entonces también es una botella de Klein.

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

Si, por otro lado, el par se invierte, pero solo uno de los pares coincide con mayúsculas y minúsculas, entonces ese es un plano proyectivo.

i`(.)..\1
S

Y si el par se invierte pero ninguno de los dos coincide con mayúsculas y minúsculas, entonces esa es una esfera. ( i`.(.)\1.también funcionaría)

....
P

Todo lo demás es un plano proyectivo.

Neil
fuente
1
@ JonathanAllan Gracias por la sugerencia; Esperemos que esta versión tenga una mejor validación.
Neil
Si tan solo pudiera resolver la lógica yo mismo: p
Jonathan Allan
1

Jalea , 52 51 58 bytes

+7 bytes, descubrí que el mapeo que había usado no funcionaba para algunos (fuera de ejemplo) escenarios de cambio de caso.

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

Un enlace monádico que toma una cadena y devuelve los siguientes cinco valores distintos y consistentes:

  • [-1,-1] - entrada inválida
  • [0,0] - plano proyectivo
  • [1,0] - botella de Klein
  • [2,0] - esfera
  • [2,1] toro

Pruébalo en línea! o ver el conjunto de pruebas .

¿Cómo?

Cualquier polígono fundamental es:

  • sin cambios bajo rotación: se puede girar el papel como un volante
  • sin cambios bajo reflexión - uno puede voltear el papel
  • sin cambios bajo la inversión de mayúsculas y minúsculas: se pueden intercambiar asy As y / o intercambiar bsy Bsin efecto, ya que queremos coincidir con las direcciones en las que la etiqueta real no tiene consecuencias.

Como tal, hay nueve clases de equivalencia. El código crea listas de cuatro enteros, cada uno de los cuales representa un ejemplo de una de las nueve clases de equivalencia, crea las cuatro rotaciones de cada una, refleja cada una de ellas y luego verifica si existe una forma traducida de la entrada en cada lista. Las clases están ordenadas P,P,P,K,K,K,S,S,T, por lo que tomar el entero de índice basado en 0 dividido por cada uno de los [3,8]rendimientos de las cuatro salidas válidas (la indexación está basada en 1 y el átomo edevuelve 0por inexistencia, por lo que restando 1y el entero dividiendo por cada uno de los [3,8]rendimientos [-1,-1]para el caso no válido )

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

Nota: 11 bytes ( ŒlĠL€⁼2,2ȧ⁸) solo validan la cadena de entrada ab1acomo si tuviera la forma correcta; sin este código, cada caso de ejemplo pasa, excepto que se evalúa como si fuera abBaun plano proyectivo.

Jonathan Allan
fuente