Fliesen Sie das Schachbrett mit vierfarbigen Triominoes

11

Aufgabe:

Betrachten Sie das Problem: "Wenn ein Schachbrett mit einem fehlenden Quadrat vorhanden ist, schneiden Sie es in 21 L-Triominoes". Es gibt einen bekannten konstruktiven Beweis dafür, dass dies für jede quadratische Schachbrettgröße mit einer Zweierpotenz möglich ist. Es funktioniert, indem das Schachbrett in ein kleineres Schachbrett mit dem Loch darin und einem großen Triomino aufgeteilt wird und dann beobachtet wird, dass dieses Triomino rekursiv in vier Triominos geschnitten werden kann.

In dieser Aufgabe müssen Sie ein 8x8-Schachbrett in L-förmige Triominoes schneiden und diese dann mit vier Farben färben, sodass keine zwei benachbarten Triominoes dieselbe Farbe haben.

Spezifikation:

Ihre Eingabe ist die Position des Lochs, angegeben als Paar von ganzen Zahlen. Sie können wählen, welcher der Spaltenindex und welcher der Zeilenindex ist. Sie können wählen, ob jede bei 0 oder bei 1 beginnt und von welcher Ecke sie zunimmt. Möglicherweise benötigen Sie A..H als erste Koordinate anstelle von 0..7 oder 1..8. Sie können auch beide Koordinaten akzeptieren, die in einer einzigen Ganzzahl 0..63 oder 1..64 in lexikografischer Reihenfolge gepackt sind (Zeilen- oder Spaltenmajor, von links nach rechts oder von rechts nach links, von oben nach unten oder von unten nach oben). Sie können ein vollständiges Programm oder eine Funktion schreiben.

Sie können die Kacheln als ASCII, als farbiges ASCII oder als grafische Grundelemente ausgeben. Wenn Sie die ASCII-Ausgabe auswählen, können Sie vier beliebige druckbare ASCII-Zeichen auswählen, um die vier Farben darzustellen. Wenn Sie farbiges ASCII auswählen, können Sie vier beliebige druckbare ASCII-Zeichen oder nur ein anderes Zeichen als Leerzeichen auswählen. Das Loch muss durch das Leerzeichen dargestellt werden. Wenn einer Ihrer Charaktere der Leerzeichencharakter ist, darf kein Triomino neben dem Loch oder am Schachbrettrand diese Farbe haben.

Wenn Sie eine farbige ASCII- oder grafische Ausgabe auswählen, können Sie vier beliebige Farben aus # 000, # 00F, # 0F0, # 0FF, # F00, # F0F, # FF0, #FFF oder deren nächstgelegenen Entsprechungen auswählen, die in Ihrer Umgebung verfügbar sind. Wenn Sie sich für eine grafische Ausgabe entscheiden, müssen Ihre grafischen Grundelemente mit mindestens 32 x 32 Pixel großen Quadraten gefüllt und durch nicht mehr als zwei Pixel einer anderen Farbe getrennt sein. Wenn das oben Gesagte die Bildschirmauflösung Ihrer Umgebung überschreitet, wird die Mindestgröße auf die größte quadratische Größe reduziert, die noch auf den Bildschirm passt.

Sie können eine beliebige gültige Kachelung des angegebenen Schachbretts auswählen. Sie können eine beliebige vierfarbige Kachel wählen. Die Auswahl von vier Farben muss für alle Ausgaben gleich sein, Sie müssen jedoch nicht jede Farbe in jeder Ausgabe verwenden.

Beispiele:

Mögliche Ausgabe für Eingabe = [0, 0] (obere linke Ecke)

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

Eine weitere mögliche Ausgabe desselben Programms (Eingabe = [0, 7]):

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

Ein anderes Programm kann auch für die Eingabe von "D1" (beachten Sie die nicht standardmäßige, aber erlaubte Schachbrettausrichtung) Folgendes erzeugen:

AABBCCAA
ACBACBAC
CCAABBCC
 ABBAADD
AABDABDC
BBDDBBCC
BABBACAA
AABAACCA
John Dvorak
quelle
4
Wenn es Input gibt, ist es nicht wirklich Kolmogorov Komplexität
Jonathan Allan
@JonathanAllan In der Tag-Beschreibung wird verwendet, wer dieses Pokemon ist, als Beispiel für eine Kolmogorov-Komplexitätsfrage, die Eingaben enthält. Es liegt an Ihnen, ob Sie einen Satz von 64 konstanten Lösungen komprimieren oder eine Prozedur implementieren möchten, um das Schachbrett zu kacheln und dann zu färben.
John Dvorak
1
Sind drei Farben nicht genug?
Arnauld
1
@Arnauld Das werde ich zulassen. Ich werde bearbeiten.
John Dvorak

Antworten:

22

JavaScript (ES6),  184 ... 171  163 Byte

Nimmt die Eingabe (x)(y)mit und . Gibt als Zeichenfolge mit 3 Farben aus (markiert als , und ).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)

Probieren Sie es online aus!

Methode

Wir arbeiten an einer Matrix von Triominoes:4×4

(t0t1t2t3t4t5t6t7t8t9t10t11t12t13t14t15)

Jeder Triomino ist einer von:

Triominoes

Die anfängliche Konfiguration der Matrix ist wie folgt:

(3232132031021010)

Wir wechseln die ersten beiden Farben wie auf jedem Schachbrett, was Folgendes ergibt:

matrix0

Die nächsten Schritte sind:

  1. t5t6t9t10
  2. Wir drehen den Triomino, auf dem sich das Loch befindet (es kann der gleiche Triomino wie in Schritt 1 sein), so dass er das Loch nicht bedeckt.
  3. Wir füllen die Löcher mit der 3. Farbe (außer dem "echten" Loch).

(3,0)

Matrix1

In diesem Fall lautet die endgültige Matrix:

(3132102031021010)

Kommentiert

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

Grafische Ausgabe

Klicken Sie auf das Bild, um die Position des Lochs festzulegen.

Arnauld
quelle
Konstruktiver Beweis, dass drei Farben immer ausreichen, sehr schön!
John Dvorak
6
Ich liebe die anklickbare grafische Ausgabe!
Kevin Cruijssen
3

Holzkohle , 78 Bytes

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

Probieren Sie es online aus! Der Link führt zur ausführlichen Version des Codes. Ausgaben mit #$%Zeichen. Erläuterung:

NθNη

Geben Sie die Koordinaten des leeren Quadrats ein.

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

Geben Sie eine komprimierte Zeichenfolge aus. Es enthält Zeilenumbrüche, damit der Ablauf dieser Erklärung nicht unterbrochen wird. Die Zeichenfolge befindet sich am Ende der Antwort.

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

Wenn eine der Koordinaten größer ist als diese, 3merken Sie sich diese Tatsache und subtrahieren Sie die Koordinate von 7.

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

Springe zum nächsten %des oberen linken Quadrats von %s und überschreibe es mit einem #oder $entsprechend. (Dies wird jedoch durch das Leerzeichen überschrieben, wenn es sich bereits auf diesem Feld befand.)

Jθη Fζ‖Fε‖↓

Blenden Sie das Quadrat an den reduzierten Koordinaten aus und reflektieren Sie dann die Ausgabe nach Bedarf, um den Rohling an die ursprüngliche Position zu bringen.

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

Ich habe versucht, mit dem Quadrat von %s in der Mitte zu beginnen und mich zu den gewünschten Koordinaten herauszuarbeiten, aber das dauerte 90 Bytes.

Neil
quelle