_{Diese Herausforderung ist von dieser App inspiriert .}

Dies ist eine viel einfachere Version dieser Herausforderung . Diese Herausforderung ist Code-Golf , während die andere der schnellste Code ist .

Sie erhalten ein quadratisches Eingaberaster mit den Abmessungen 6 x 6, das in 6 Bereiche unterteilt ist, in denen die Zellen jedes Bereichs eine eindeutige Kennung haben (ich werde hier im Text Kleinbuchstaben von af verwenden). Sie können jedoch wählen, was Sie möchten, z. B. Ganzzahlen 1-6 ).

Die Eingabe kann folgendermaßen aussehen (optionales Eingabeformat):

aabbbb
aabbbb
aaccbb
acccdb
ecccdb
eeefff

Oder einfacher zu visualisieren:

Herausforderung:

Sie müssen 6 Bäume in diesem Park nach den folgenden Regeln platzieren:

• Es soll genau 1 Baum pro Spalte und 1 Baum pro Zeile geben
• Alle Bereiche müssen genau 1 Baum haben.
• Kein Baum darf vertikal, horizontal oder diagonal an einen anderen Baum angrenzen

Die Lösung für das obige Layout lautet:

Hinweis: Für jedes Rätsel gibt es nur eine Lösung

Zusätzliche Regeln:

• Die Eingabe- und Ausgabeformate sind optional
  • Die Ausgabe kann beispielsweise eine Liste von Indizes, ein Raster mit 1/0 sein, das angibt, ob sich an dieser Position ein Baum befindet, oder eine modifizierte Version der Eingabe, in der die Bäume angezeigt werden
• Die Ausführungszeit muss deterministisch sein
• Das Programm muss auf einem vernünftigen modernen Laptop innerhalb von 1 Minute beendet sein
• Brownie zeigt, wenn Sie keine rohe Gewalt anwenden!

Testfälle:

aabbbb
aabbbb
aaccbb
acccdb
ecccdb
eeefff
---
aAbbbb
aabbbB
aaCcbb
acccDb
Ecccdb
eeeFff
----------
aabccc
aacccc
aaddce
aeeeee
aeeefe
eeeeee
---
aaBccc
aacccC
aadDce
Aeeeee
aeeeFe
eEeeee
----------
aaaabb
aacbbb
aadddb
addeef
ddddee
dddeee
---
aaaaBb
aaCbbb
Aadddb
addeeF
dDddee
dddEee
----------
abbbcd
abebcd
addddd
dddddd
effdff
eeffff
---
abBbcd
abebCd
Addddd
dddDdd
effdfF
eEffff

Gleiche Testfälle in einem Format, das etwas einfacher zu analysieren ist:

Test case 1:
[1,1,2,2,2,2;1,1,2,2,2,2;1,1,3,3,2,2;1,3,3,3,4,2;5,3,3,3,4,2;5,5,5,6,6,6]
Test case 2:
[1,1,2,3,3,3;1,1,3,3,3,3;1,1,4,4,3,5;1,5,5,5,5,5;1,5,5,5,6,5;5,5,5,5,5,5]
Test case 3:
[1,1,1,1,2,2;1,1,3,2,2,2;1,1,4,4,4,2;1,4,4,5,5,6;4,4,4,4,5,5;4,4,4,5,5,5]
Test case 4:
[1,2,2,2,3,4;1,2,5,2,3,4;1,4,4,4,4,4;4,4,4,4,4,4;5,6,6,4,6,6;5,5,6,6,6,6]

C 223 182 Bytes

O[15],U;main(y,v)char**v;{if(y>7)for(;y-->2;printf("%06o\n",O[y]));else for(int*r,x=1,X=8;X<14;U&x|*r|O[10-y]*9&x*9?0:(U^=O[9-y]=*r=x,*r=main(y+1,v),U^=x),x*=8)r=O+v[1][y*7-++X]-88;}

Nimmt die Eingabe als Argument in dem in der Frage angegebenen Format auf. Schreibt die Ausgabe als Raster von 0s mit 1s in stdout, wohin die Bäume gehen.

./TreesMin 'aabbbb
aabbbb
aaccbb
acccdb
ecccdb
eeefff'

Beispielausgabe:

010000
000001
001000
000010
100000
000100

Nervenzusammenbruch

O[15],                                  // Tree positions & region usage
U;                                      // Column usage (bitmask)
main(y,v)char**v;{                      // Recursive main function
  if(y>7)                               // Finished grid?
    for(;y-->2;printf("%06o\n",O[y]));  //  Print it (rows are padded octal)
  else                                  // Not finished:
    for(int*r,x=1,X=8;X<14;             //  Loop over columns
      U&x|*r|O[10-y]*9&x*9              //   Current cell violates rules?
        ?0                              //    Do nothing
        :(U^=O[9-y]=*r=x,               //   Else: mark cell
          *r=main(y+1,v),               //    Recurse
          U^=x)                         //    Unmark cell
      ,x*=8)                            //   Advance to next column
      r=O+v[1][y*7-++X]-88;             //   Region pointer for current iteration
}

Es ist eine Anpassung meiner Antwort an die schnellste Codeversion dieser Frage . Hat nicht so viel Kurzschluss, ist aber schnell genug für 6x6-Gitter.

Clingo , 66 Bytes

1{t(X,Y):c(X,Y,Z)}:-Z=1..n.:-t(X,Y),2{t(X,J;I,Y;X-1..X+1,Y..Y+1)}.

Führen Sie mit clingo plant.lp - -c n=<n>dem <n>ist die Rastergröße. Das Eingabeformat ist eine Liste von c(X,Y,Z).Anweisungen für jede Zelle ( X, Y) gefärbt Z, mit 1 ≤ X, Y, Z≤ ndurch Leerzeichen getrennt optional. Die Ausgabe enthält t(X,Y)für jeden Baum at ( X, Y).

Demo

$ clingo plant.lp - -c n=6 <<EOF
> c(1,1,1). c(2,1,1). c(3,1,2). c(4,1,2). c(5,1,2). c(6,1,2).
> c(1,2,1). c(2,2,1). c(3,2,2). c(4,2,2). c(5,2,2). c(6,2,2).
> c(1,3,1). c(2,3,1). c(3,3,3). c(4,3,3). c(5,3,2). c(6,3,2).
> c(1,4,1). c(2,4,3). c(3,4,3). c(4,4,3). c(5,4,4). c(6,4,2).
> c(1,5,5). c(2,5,3). c(3,5,3). c(4,5,3). c(5,5,4). c(6,5,2).
> c(1,6,5). c(2,6,5). c(3,6,5). c(4,6,6). c(5,6,6). c(6,6,6).
> EOF
clingo version 5.1.0
Reading from plant.lp ...
Solving...
Answer: 1
c(1,1,1) c(2,1,1) c(3,1,2) c(4,1,2) c(5,1,2) c(6,1,2) c(1,2,1) c(2,2,1) c(3,2,2) c(4,2,2) c(5,2,2) c(6,2,2) c(1,3,1) c(2,3,1) c(3,3,3) c(4,3,3) c(5,3,2) c(6,3,2) c(1,4,1) c(2,4,3) c(3,4,3) c(4,4,3) c(5,4,4) c(6,4,2) c(1,5,5) c(2,5,3) c(3,5,3) c(4,5,3) c(5,5,4) c(6,5,2) c(1,6,5) c(2,6,5) c(3,6,5) c(4,6,6) c(5,6,6) c(6,6,6) t(1,5) t(2,1) t(6,2) t(3,3) t(5,4) t(4,6)
SATISFIABLE

Models       : 1+
Calls        : 1
Time         : 0.045s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 0.000s

Um die Eingabe des Eingabe- / Ausgabeformats zu vereinfachen, finden Sie hier Python-Programme, die von und in das in der Herausforderung angegebene Format konvertiert werden können.

Eingang

import sys
print(' '.join("c({},{},{}).".format(x + 1, y + 1, ord(cell) - ord('a') + 1) for y, row in enumerate(sys.stdin.read().splitlines()) for x, cell in enumerate(row)))

Ausgabe

import re
import sys
for line in sys.stdin:
    c = {(int(x), int(y)): int(z) for x, y, z in re.findall(r'\bc\((\d+),(\d+),(\d+)\)', line)}
    if c:
        t = {(int(x), int(y)) for x, y in re.findall(r'\bt\((\d+),(\d+)\)', line)}
        n, n = max(c)
        for y in range(1, n + 1):
            print(''.join(chr(ord('aA'[(x, y) in t]) + c[x, y] - 1) for x in range(1, n + 1)))
        print()