Solución normalizadora Pentomino 6x10

19

Como probablemente ahora, hay 2339 soluciones para el rompecabezas pentomino en una cuadrícula de 6x10. Existen diferentes esquemas de etiquetado para los 12 pentominoes, dos de ellos se muestran en la imagen a continuación:

ingrese la descripción de la imagen aquí

Crédito de imagen: Wikipedia

A los fines de la tarea actual, diremos que una solución pentomino normalizada es una solución que utiliza el segundo esquema de etiquetado (Conway).

Ejemplo:

O O O O O S S S Z Z
P P R R S S W W Z V
P P P R R W W Z Z V
U U X R T W Y V V V
U X X X T Y Y Y Y Q
U U X T T T Q Q Q Q

La pieza con 5 cuadrados en fila se denota con letras O, de acuerdo con el esquema. Lo mismo es cierto para todas las piezas.

Tarea:

Dada una solución para el pentomino 6x10 en el que las piezas están etiquetadas con un sheme aleatorio, normalícelo para que todas las piezas estén etiquetadas en el esquema de etiquetado de Conway. Debe reconocer las piezas y marcar cada cuadrado de una pieza en particular con el símbolo de la pieza.

Entrada:

La solución a normalizar, en cualquier formato que sea conveniente para usted, por ejemplo:

  • Una cuerda multilínea

  • Una lista de cadenas

  • Una lista de listas de personajes.

y así

Salida:

La misma solución (todas las posiciones y orientación de las piezas preservadas), pero cada pieza etiquetada de acuerdo con el esquema de etiquetado de Conway. Nota: La salida DEBE IMPRIMIRSE como una cuadrícula de caracteres de 6x10. Se permiten nuevas líneas y espacios iniciales y finales. También puede imprimir un espacio entre los caracteres (pero no las líneas vacías), como en el ejemplo anterior.

Casos de prueba:

1. Entrada:

6623338888
6222344478
66A234BB70
1AAA94B770
11A99BB700
1199555550

Salida:

UURTTTQQQQ
URRRTVVVSQ
UUXRTVZZSY
PXXXWVZSSY
PPXWWZZSYY
PPWWOOOOOY

2. Entrada:

45ookkkk00
455ooogk00
4a55gggdd0
4aaa3gnnd.
4am333ndd.
mmmm3nn...

Salida:

OWSSQQQQPP
OWWSSSRQPP
OTWWRRRUUP
OTTTXRZZUV
OTYXXXZUUV
YYYYXZZVVV

Criterios ganadores:

La solución más corta en bytes en cada idioma gana. No se desanime por los idiomas de golf. Las explicaciones de los algoritmos y las implementaciones son bienvenidas.

Galen Ivanov
fuente
@KevinCruijssen ¡Gracias! (No busqué preguntas relacionadas con los tetromonoes)
Galen Ivanov el

Respuestas:

12

APL (Dyalog Classic) , 54 53 50 bytes

⍴⍴{'OXRYTPZQUWSV'[⌊5÷⍨⍋⍋,{×/+⌿↑|(⊢-+/÷≢)⍸⍵}¨⍵=⊂⍵]}

Pruébalo en línea!

Calcule un invariante para cada pentomino en la entrada: mida (∆x, ∆y) desde cada uno de sus cuadrados hasta su centro de gravedad, tome abs (∆x) y abs (∆y), sume los componentes x y separe los y componentes, y multiplicar las dos sumas. Esto da 12 resultados distintos. Luego, encuentre el índice de cada invariante de pentomino en la colección ordenada de todos los invariantes. Reemplace 0 con 'O', 1 con 'X', 2 con 'R', etc.

ngn
fuente
¡Gracias por la respuesta rápida y la explicación, +1 de mi parte! Quise decir que la solución se imprimiera explícitamente como una cuadrícula de 6x10. Cambié la descripción, actualice su solución. Disculpe las molestias.
Galen Ivanov el
@GalenIvanov pero ... es una cuadrícula . Mis pruebas muestran "ok" en lugar de imprimir el resultado, ¿tal vez eso es demasiado confuso?
ngn
Sí, estaba confundido por las pruebas.
Galen Ivanov el
3
Ahora que imprimen el resultado antes de validarlo
NGN
4

Jalea , 37 bytes

ŒĠZÆmạƊ€ḅı§AỤỤị“æṂ⁾+’Œ?¤+78Ọ,@FQṢƊyⱮY

Un programa completo que toma una lista de cadenas (porque debemos imprimir; de lo contrario, elimine el final Yy tendrá una mónada tomando una lista de listas de números o caracteres que devuelve una lista de listas de caracteres).

Pruébalo en línea!

¿Cómo?

Creo que esto funciona usando la misma categorización de pentominos que la solución APL de ngn , aunque de una manera ligeramente diferente (tampoco conozco APL, así que no estoy seguro de cuán similar es el método más allá de la categorización).

(¡Tenga en cuenta que “æṂ⁾+’Œ?¤+78Ọsolo se ahorra un byte “XRPTZWUYSVQO”!)

ŒĠZÆmạƊ€ḅı§AỤỤị“æṂ⁾+’Œ?¤+78Ọ,@FQṢƊyⱮY - Main Link: list of lists of characters L
ŒĠ                                    - group multidimensional indices by value
      Ɗ€                              - last three links as a monad for €ach i.e. f(x):
  Z                                   -   transpose x
   Æm                                 -   mean (vectorises) (i.e. the average of the coordinates)
     ạ                                -   absolute difference with x (vectorises) (i.e. [dx, dy])
         ı                            - square root of -1 (i)
        ḅ                             - convert from base (vectorises) (i.e a list of (i*dx+dy)s)
          §                           - sum each
           A                          - absolute value (i.e. norm of the complex number)
            Ụ                         - grade up (sort indices by value)
             Ụ                        - grade up (...getting the order from the result of A back,
                                      -              but now with one through to 12)
                       ¤              - nilad followed by links as a nilad:
               “æṂ⁾+’                 -   base 250 literal = 370660794
                     Œ?               -   permutation@lex-index = [10,4,2,6,12,9,7,11,5,8,3,1]
              ị                       - index into
                        +78           - add seventy-eight
                           Ọ          - cast to characters (character(1+78)='O', etc...)
                                 Ɗ    - last three links as a monad (i.e. f(L)):
                              F       -   flatten
                               Q      -   de-duplicate
                                Ṣ     -    sort
                            ,@        - pair (with sw@pped @rguments) (giving a list of 2 lists)
                                   Ɱ  - Ɱap across L with:
                                  y   -   translate i.e. swap the letters as per the the pair)
                                    Y - join with new lines
                                      - implicit print
Jonathan Allan
fuente
2

Wolfram Language (Mathematica) , 103 bytes

""<>Riffle[(t=#)/.Thread[SortBy[Union@@t,Tr@Kurtosis@Position[t,#]&]->Characters@"UPSWZVRTQXYO"],"\n"]&

Toma entrada como una lista de listas de caracteres.

Pruébalo en línea!

La idea principal aquí es que para cada carácter en la entrada, encontramos las coordenadas donde ocurre, tomamos la curtosis y sumamos sus coordenadas. Esto nos da una invariante para cada pieza.

(La curtosis es un operador mayormente irrelevante de las estadísticas; la clave es que es invariante bajo traducción, mientras que la reflexión y la rotación pueden cambiar el orden de las coordenadas como máximo. Sumamos las coordenadas, por lo que la invariante nunca cambia).

De todos modos, aparte de la extraña invariante, esta solución es similar a las demás: clasificamos los caracteres y las piezas por cada invariante, luego reemplazamos cada personaje por el carácter correspondiente de "UPSWZVRTQXYO": las piezas, ordenadas por suma de curtosis.

Finalmente, ""<>Riffle[...,"\n"]es el código de imprimir como una cuadrícula.

Misha Lavrov
fuente
+1 por conocer una operación de la que nunca había oído hablar y darle un buen uso
Black Owl Kai
Mi primer intento de solución tuvo Sort@Variancelugar Tr@Kurtosis, y probablemente más personas hayan oído hablar de la variación. Pero Tr@Varianceno funciona porque varios pentominoes (como P y X) tienen la misma suma de varianza x y varianza y. Así que busqué en la documentación de Mathematica algo más elegante.
Misha Lavrov
2

Python 2 , 191 bytes

def y(o):print"".join(['XPRTWZUYSVQO\n'[[w for v,w in sorted([sum(abs(u-sum(t)/5)for t in[[complex(r%11,r/11)for r,q in enumerate(o)if q==p]]for u in t),p]for p in o)].index(x)/5]for x in o])

Pruébalo en línea!

Toma una cadena de varias líneas con una nueva línea final y realiza seis comprensiones de listas anidadas.

Versión sin golf

def pentomino_normalizer(input_string):
    # input_string is a multi-line string with a trailing newline

    results = []  # For saving the results of the for loop
    for current_char in input_string:
        # current_char = p in the golfed version

        # The python data type complex stores a real and a imaginary value and
        # is used for storing the x and y coordinates.
        # In the end, the positions list contains a complex number for every
        # occurence of current_char in the string
        # positions_list = t in the golfed version
        positions_list = [complex(i % 11, i / 11) for i, c
                          in enumerate(input_string) if c == current_char]
        # average_pos is the midpoint of all occurences of current_char, 
        # to get rid of translations
        average_pos = sum(positions_list)/5
        # Calculates a value for each tile that is invariant under 
        # translations and rotations,
        # simply the sum of all the distances between the midpoint
        # and the positions
        invariant = sum(abs(pos - average_pos) for pos in positions_list)

        # Saves the invariant value to a list
        results.append(invariant, current_char)

    # This new list contains the characters occuring in the string, sorted
    # by the invariant value. Because this was done with each char in the 
    # input string, this lists contains every value five times and also 
    # contains six newlines
    # at the end of the list
    sorted_results = [w for v, w in sorted(results)]

    # This code snippet maps each char from the input string to its according
    # output and prints to stdout
    chars = ['XPRTWZUYSVQO\n'[sorted_results.index(c)/5] for c in input_string]
    print "".join(chars)
Black Owl Kai
fuente