Ułóż szachownicę w czterokolorowe triomino

12

Zadanie:

Rozważ problem: „biorąc pod uwagę szachownicę z brakiem jednego kwadratu, pokrój ją w 21 L-triomino”. Istnieje dobrze znany konstruktywny dowód na to, że można to zrobić dla dowolnej kwadratowej wielkości szachownicy o sile dwóch. Działa poprzez podzielenie szachownicy na mniejszą szachownicę z otworem i jednym dużym triomino, a następnie zaobserwowanie, że to triomino można rekurencyjnie pokroić na cztery triomino.

W tym zadaniu musisz wyciąć szachownicę 8x8 w triomino w kształcie litery L, a następnie pokolorować je czterema kolorami, tak aby żadne dwa sąsiednie triomino nie miały tego samego koloru.

Specyfikacja:

Twoje dane wejściowe to pozycja dołka podana jako para liczb całkowitych. Możesz wybrać, który jest indeksem kolumny, a który indeksem wiersza. Możesz wybrać, czy każdy zaczyna się od 0, czy od 1 i dalej, od którego rogu zwiększa się. Możesz wymagać A..H jako pierwszej współrzędnej zamiast 0..7 lub 1..8. Możesz także zaakceptować obie współrzędne spakowane w jedną liczbę całkowitą 0..63 lub 1..64 w porządku leksykograficznym (major-row lub major-column, od lewej do prawej lub od prawej do lewej, od góry do dołu lub od dołu do góry). Możesz napisać pełny program lub funkcję.

Możesz wyprowadzać kafelki jako ASCII, jako kolorowe ASCII lub jako prymitywy graficzne. Jeśli wybierzesz wyjście ASCII, możesz wybrać dowolne cztery drukowane znaki ASCII, które reprezentują cztery kolory. Jeśli wybierzesz kolorowe ASCII, możesz wybrać dowolne cztery drukowane znaki ASCII lub tylko jeden znak inny niż spacja. Otwór musi być reprezentowany przez znak spacji. Jeśli jedna z twoich postaci jest postacią spacji, żadne triomino sąsiadujące z dziurą lub na krawędzi szachownicy nie może być w tym kolorze.

Jeśli wybierzesz kolorowe ASCII lub wyjście graficzne, możesz wybrać dowolne cztery kolory spośród # 000, # 00F, # 0F0, # 0FF, # F00, # F0F, # FF0, #FFF lub ich najbliższych odpowiedników dostępnych w twoim środowisku. W przypadku wybrania wyjścia graficznego prymitywy graficzne muszą być wypełnione kwadratami o wielkości co najmniej 32 x 32 piksele i oddzielone nie więcej niż dwoma pikselami innego koloru. Jeśli powyższe wartości przekraczają rozdzielczość ekranu środowiska, minimalny rozmiar jest zmniejszany do największego rozmiaru kwadratu, który nadal mieści się na ekranie.

Możesz wybrać dowolny prawidłowy kafelek danej szachownicy. Możesz wybrać dowolne cztery kolory wybranego kafelka. Twój wybór czterech kolorów musi być taki sam na wszystkich wydrukach, ale nie musisz używać każdego koloru na każdym wydruku.

Przykłady:

Możliwe dane wyjściowe = [0, 0] (lewy górny róg)

 #??##??
##.?#..?
?..#??.#
??##.?##
##?..#??
#.??##.?
?..#?..#
??##??##

Kolejne możliwe wyjście tego samego programu (input = [0, 7]):

??#??#?
?##?##??
..xx..xx
.?x#.?x#
??##??##
..xx..xx
.?x#.?x#
??##??##

Inny program może również produkować, dla wprowadzenia „D1” (zwróć uwagę na niestandardową, ale dozwoloną orientację szachownicy),

AABBCCAA
ACBACBAC
CCAABBCC
 ABBAADD
AABDABDC
BBDDBBCC
BABBACAA
AABAACCA
John Dvorak
źródło
4
Jeśli jest jakiś wkład, to nie jest tak naprawdę złożonością Kołmogorowa
Jonathan Allan
@JathanathanAllan w opisie znacznika używa tego pokemona jako przykładu pytania złożoności Kołmogorowa, które wymaga danych wejściowych. Od Ciebie zależy, czy chcesz skompresować zestaw 64 stałych rozwiązań, czy też chcesz wdrożyć procedurę kafelkowania szachownicy, a następnie pokolorowania jej.
John Dvorak,
1
Czy trzy kolory nie są wystarczające?
Arnauld
1
@Arnauld Pozwolę na to. Będę edytować.
John Dvorak,

Odpowiedzi:

22

JavaScript (ES6),  184 ... 171  163 bajtów

(x)(y)0x70y7012)

h=>v=>(a=[...'3232132031021010'],a[5+(v&4|h>3)]^=3,a[v/2<<2|h/2]=v%2*2+h%2,g=x=>y&8?'':(x<8?x-h|y-v?a[y/2<<2|x/2]^y%2*2+x%2?(x^y)&2:1:' ':`
`)+g(-~x%9||!++y))(y=0)

Wypróbuj online!

metoda

4×4

(t0t1t2)t3)t4t5t6t7t8t9t10t11t12t13t14t15)

Każde triomino jest jednym z:

triominoes

Początkowa konfiguracja macierzy jest następująca:

(3)2)3)2)13)2)03)102)1010)

Przeplatamy pierwsze 2 kolory tak jak na każdej szachownicy, co daje:

matryca 0

Kolejne kroki to:

  1. t5t6t9t10
  2. Obracamy triomino, na którym znajduje się otwór (może to być takie samo triomino, jak w kroku # 1), aby nie zakryło otworu.
  3. Dziury wypełniamy 3. kolorem (oprócz „prawdziwej” dziury).

(3),0)

matryca 1

W takim przypadku ostatnia matryca to:

(3)13)2)102)03)102)1010)

Skomentował

h => v => (                       // (h, v) = hole coordinates
  a = [...'3232132031021010'],    // a[] = flat representation of the 4x4 matrix
  a[5 + (v & 4 | h > 3)] ^= 3,    // first rotation, achieved by XOR'ing with 3
  a[v / 2 << 2 | h / 2] =         // second rotation according to the
    v % 2 * 2 + h % 2,            // position of the hole within the triomino's square
  g = x =>                        // g is a recursive function that converts the 4x4
                                  // matrix into a 8x8 ASCII art
    y & 8 ?                       // if y = 8:
      ''                          //   stop recursion and return an empty string
    :                             // else:
      ( x < 8 ?                   //   if this is not the end of the row:
          x - h | y - v ?         //     if this is not the position of the hole:
            a[y / 2 << 2 | x / 2] //       if this part of the triomino located at this
            ^ y % 2 * 2 + x % 2 ? //       position is 'solid':
              (x ^ y) & 2         //         use either color #0 or color #2
            :                     //       else:
              1                   //         use color #1
          :                       //     else:
            ' '                   //       the hole is represented with a space
        :                         //   else:
          `\n`                    //     append a linefeed
      ) + g(-~x % 9 || !++y)      //   append the result of a recursive call
)(y = 0)                          // initial call to g with x = y = 0

Wyjście graficzne

Kliknij na zdjęcie, aby ustawić pozycję otworu.

Arnauld
źródło
Konstruktywny dowód, że trzy kolory są zawsze wystarczające, bardzo ładne!
John Dvorak,
6
Uwielbiam klikalne wyjście graficzne!
Kevin Cruijssen
3

Węgiel drzewny , 78 bajtów

NθNη”{⊞⊟¦≦⁶q×fΣ\⊙t×_⊟✳-Y⁴℅=⁶υ”≔›θ³ζ≔›η³εFζ≦⁻⁷θFε≦⁻⁷ηJ⊕÷θ²⊕÷粧#$⁺ⅈⅉJθη Fζ‖Fε‖↓

Wypróbuj online! Link jest do pełnej wersji kodu. Wyjścia za pomocą #$%znaków. Wyjaśnienie:

NθNη

Wprowadź współrzędne pustego kwadratu.

”{⊞⊟¦≦⁶q×fΣ\⊙t×_⊟✳-Y⁴℅=⁶υ”

Wyprowadza skompresowany ciąg. Zawiera znaki nowej linii, aby uniknąć przerywania przepływu tego objaśnienia, łańcuch znajdziesz na końcu odpowiedzi.

≔›θ³ζ≔›η³εFζ≦⁻⁷θFε≦⁻⁷η

Jeśli którakolwiek ze współrzędnych jest większa niż 3wtedy, pamiętaj o tym fakcie i odejmij współrzędną od 7.

J⊕÷θ²⊕÷粧#$⁺ⅈⅉ

Przeskocz do najbliższego %lewego górnego kwadratu %s i zastąp go odpowiednim #lub $. (Ale to zostanie zastąpione spacją, jeśli było już w tym kwadracie).

Jθη Fζ‖Fε‖↓

Wyczyść kwadrat przy zmniejszonych współrzędnych, a następnie odpowiednio odzwierciedl dane wyjściowe, aby ustawić puste miejsce w pierwotnej pozycji.

##$$##$$
#%%$#%%$
$%%#$$%#
$$##%$##
##$%%#$$
#%$$##%$
$%%#$%%#
$$##$$##

Próbowałem zacząć od kwadratu %s pośrodku i wypracowałem drogę do pożądanych współrzędnych, ale zajęło to 90 bajtów.

Neil
źródło