Normalizator rozwiązania Pentomino 6x10


19

Jak zapewne teraz, istnieje 2339 rozwiązań pentomino w siatce 6x10. Istnieją różne schematy znakowania dla 12 pentominoów, dwa z nich pokazano na poniższym obrazku:

wprowadź opis zdjęcia tutaj

Źródło zdjęcia: Wikipedia

Na potrzeby bieżącego zadania powiemy, że znormalizowane rozwiązanie pentomino to rozwiązanie, które wykorzystuje drugi schemat znakowania (Conwaya).

Przykład:

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

Kawałek z 5 kwadratami z rzędu jest oznaczony literami O, zgodnie ze schematem. To samo dotyczy wszystkich elementów.

Zadanie:

Biorąc pod uwagę rozwiązanie pentomino 6x10, w którym kawałki są oznaczone losowym sheem, znormalizuj je, aby wszystkie kawałki były oznaczone w schemacie znakowania Conwaya. Musisz rozpoznać elementy i oznaczyć każdy kwadrat danego elementu symbolem tego elementu.

Wejście:

Rozwiązanie, które należy znormalizować w dowolnym dogodnym dla Ciebie formacie, na przykład:

  • Ciąg wieloliniowy

  • Lista ciągów

  • Lista list znaków

i tak dalej

Wynik:

To samo rozwiązanie (wszystkie pozycje i orientacja sztuk zachowane), ale każda sztuka jest oznakowana zgodnie ze schematem znakowania Conwaya. Uwaga: Dane wyjściowe MUSZĄ BYĆ WYDRUKOWANE jako siatka znaków 6x10. Wiodące i końcowe znaki nowej linii i spacje są dozwolone. Możesz także wydrukować spację między znakami (ale nie puste linie), jak w powyższym przykładzie.

Przypadki testowe:

1. Wejście:

6623338888
6222344478
66A234BB70
1AAA94B770
11A99BB700
1199555550

Wynik:

UURTTTQQQQ
URRRTVVVSQ
UUXRTVZZSY
PXXXWVZSSY
PPXWWZZSYY
PPWWOOOOOY

2. Dane wejściowe:

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

Wynik:

OWSSQQQQPP
OWWSSSRQPP
OTWWRRRUUP
OTTTXRZZUV
OTYXXXZUUV
YYYYXZZVVV

Kryteria wygranej:

Najkrótsze rozwiązanie w bajtach w każdym języku wygrywa. Nie zniechęcaj się językami golfa. Wyjaśnienia algorytmów i implementacji są mile widziane.



@KevinCruijssen Dziękujemy! (Nie sprawdzałem pytań związanych z tetromonosem)
Galen Iwanow

Odpowiedzi:


12

APL (Dyalog Classic) , 54 53 50 bajtów

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

Wypróbuj online!

Oblicz niezmiennik dla każdego pentomina na wejściu: zmierz (∆x, ∆y) od każdego z jego kwadratów do środka ciężkości, weź abs (∆x) i abs (∆y), zsumuj składniki x i osobno y składniki i pomnóż dwie sumy. Daje to 12 wyraźnych wyników. Następnie znajdź indeks niezmiennika każdego pentomina w posortowanym zbiorze wszystkich niezmienników. Zamień 0 na 'O', 1 na 'X', 2 na 'R'itp.


Dziękuję za szybką odpowiedź i wyjaśnienie, +1 ode mnie! Miałem na myśli to rozwiązanie, które ma być wydrukowane wprost jako siatka 6x10. Zmieniłem opis, zaktualizuj swoje rozwiązanie - przepraszam za niedogodności.
Galen Iwanow

@GalenIvanov, ale ... to jest siatka . Moje testy dają wynik „ok” zamiast drukowania wyniku - może to zbyt mylące?
ngn

Tak, byłem zdezorientowany testami.
Galen Iwanow

3
teraz drukują wynik przed zatwierdzeniem
ngn

4

Galaretka , 37 bajtów

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

Pełny program pobierający listę ciągów (ponieważ musimy wydrukować - w przeciwnym razie usuń końcowy Yciąg, a masz monadę pobierającą listę liczb lub znaków, która zwraca listę list znaków).

Wypróbuj online!

W jaki sposób?

Wierzę, że działa to przy użyciu tej samej kategoryzacji pentominos, co rozwiązanie APN ngn , choć w nieco inny sposób (również nie znam APL, więc nie jestem pewien, jak podobna jest metoda poza kategoryzacją).

(Pamiętaj, że “æṂ⁾+’Œ?¤+78Ọto tylko jednobajtowe zapisywanie “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

2

Wolfram Language (Mathematica) , 103 bajty

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

Pobiera dane wejściowe jako listę list znaków.

Wypróbuj online!

Główną ideą jest to, że dla każdego znaku na wejściu znajdujemy współrzędne, w których występuje, bierzemy kurtozę i sumujemy jej współrzędne. To daje nam niezmienność dla każdego elementu.

(Kurtoza jest jakimś najczęściej nieistotnym operatorem w statystykach - kluczem jest to, że pod translacją jest niezmienna, podczas gdy odbicie i obrót mogą co najwyżej zmienić kolejność współrzędnych. Sumujemy współrzędne, więc niezmiennik nigdy się nie zmienia).

W każdym razie, oprócz dziwnego niezmiennika, to rozwiązanie jest podobne do pozostałych: sortujemy postacie i elementy według każdego niezmiennika, a następnie zastępujemy każdy znak odpowiadającym mu znakiem "UPSWZVRTQXYO": elementów posortowanych według sumy kurtozy.

Wreszcie ""<>Riffle[...,"\n"]jest kod drukuj jako siatkę.


+1 za znajomość operacji, o której nawet nie słyszałem, i dobre wykorzystanie
Black Owl Kai

Moja pierwsza próba rozwiązania miała Sort@Variancemiejsce Tr@Kurtosisi prawdopodobnie więcej osób słyszało o wariancji. Ale Tr@Variancenie działa, ponieważ kilka pentomino (takich jak P i X) ma tę samą sumę wariancji x i wariancji y. Przeszukałem więc dokumentację Mathematiki w poszukiwaniu czegoś bardziej wymyślnego.
Misza Ławrow

2

Python 2 , 191 bajtów

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

Wypróbuj online!

Pobiera wielowierszowy ciąg z końcowym znakiem nowej linii i wykonuje sześć zagnieżdżonych list.

Wersja bez golfa

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)
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.