Das Brettspiel

Im Brettspiel " Carcassonne " platzieren die Spieler Kacheln, indem sie ihre Kanten aufeinander abstimmen, und erzielen die höchsten Punktzahlen, indem sie große, zusammenhängende Geländeflächen erstellen. Das Folgende sind (ungefähr) die Arten und Mengen der im Spiel enthaltenen Kacheln:

#01 x4 #02 x5 #03 x8 #04 x2

#05 x9 #06 x4 #07 x1 #08 x3

#09 x3 #10 x3 #11 x4 #12 x5

#13 x3 #14 x3 #15 x2 #16 x5

#17 x5 #18 x2 #19 x3 #20 x1

#21 x5 #22 x2 #23 x1 #24 x1

#25 x1

Die Aufgabe

Sie müssen eine Kachel durch Anpassen der Kanten platzieren und gleichzeitig versuchen, die größtmöglichen zusammenhängenden Geländeflächen beizubehalten.

Platzierung

• Spielsteine ​​können nur auf eine der (bis zu 4) freien Stellen neben einem vorhandenen Spielstein (oder vorhandenen Spielsteinen) im Spielbereich gelegt werden.
• Fliesen können um 90, 180 oder 270 Grad gedreht werden.

Kantenanpassung

• Die Kanten einer platzierten Kachel müssen mit den Berührungskanten der (bis zu 4) benachbarten Kacheln übereinstimmen, dh berührende Pixel haben dieselbe Farbe.

Angrenzendes Gelände

• "Schließen eines Geländebereichs" bezieht sich auf das Platzieren einer Kachel, sodass ein zusammenhängender Farbbereich nicht mit weiteren Kachelplatzierungen fortgesetzt werden kann.
• Wenn eine alternative Platzierung möglich ist, muss sie über jeder Platzierung von Kacheln ausgewählt werden, die einen Geländebereich schließen würde.
• Wenn Sie zwischen mehreren Abschlussplatzierungen wählen müssen, wählen Sie eine beliebige. Wenn Sie zwischen mehreren nicht abschließenden Placements wählen müssen, wählen Sie eines aus.
• Ignorieren Sie # ff00ff (die Eckpixel), wenn Sie zusammenhängende Bereiche berechnen. Ignorieren Sie auch Gebäude, dh Farbbereiche, die bereits vollständig von einer Fliese umschlossen sind.

Eingang

• Die Eingabe besteht aus zwei Bildern:

  1. Der Spielbereich.

     • Der anfängliche Spielbereich besteht aus einem Plättchen #11(einem einzelnen Plättchen).
     • Der als Ausgabe erstellte erweiterte Wiedergabebereich muss auch als Eingabe unterstützt werden.

  2. Die zu platzierende Kachel.

     • Alle Beispielkacheln müssen als Eingabe unterstützt werden.

• Bestimmen Sie übereinstimmende Kanten / zusammenhängendes Gelände nur anhand dieser Bilddaten. Keine Hardcodierung.

Ausgabe

• Die Ausgabe ist ein Bild, das den resultierenden Spielbereich nach dem Platzieren der Kachel zeigt.
• Das Bild muss mit Ihrem eigenen Programm kompatibel sein, dh es kann als Spielbereichseingang verwendet werden.
• Wenn es nicht möglich ist, eine Kachel zu platzieren, wird ein Fehler zurückgegeben.

Das können Sie annehmen

• Fliesen haben immer eine Größe von 55 x 55 Pixel
• In Kacheln werden immer nur die Farben angezeigt, die derzeit in den Beispielkacheln verwendet werden.

Anmerkungen

• Ihre Antwort muss nach mindestens 2 Durchgängen eine Beispielausgabe enthalten (mehr wird empfohlen).
• Dies ist eine teilweise und ungenaue Wiedergabe des ursprünglichen Brettspiels. Sie müssen keine der hier nicht genannten Regeln oder Taktiken anwenden.

Ergebnis

• Ihre Punktzahl ist die Byteanzahl Ihrer Übermittlung.
• Bilddaten sind in Ihrer Partitur nicht enthalten.
• Die niedrigste Punktzahl gewinnt.

Möglicherweise möchten Sie ein Skript schreiben, das Ihre Vorlage verwendet, um ein vollständiges Spiel zu spielen, das aus folgenden Elementen bestehen kann:

• Platzieren einer Kachel, die pseudozufällig aus dem vollständigen Satz von 85 ausgewählt wurde.
• Bringen Sie das Plättchen zum Set zurück, wenn es nicht platziert werden kann.
• Wiederholen, bis alle Kacheln platziert wurden - oder bis zwei Kacheln in einer Reihe nicht mehr platziert werden können.

Es wird nicht in Ihre Byteanzahl einbezogen oder Ihre Punktzahl verbessert, aber ich werde wahrscheinlich eine Prämie für diese Art von Antwort anbieten.

Perl 5 mit PerlMagick: 875 789 763

Ich habe die Zeile beginnend mit nicht gezählt, mit sub wder Positionen auf dem Abstand zum Zentrum sortiert werden, um kompakte Lösungen zu bevorzugen (die jetzt ordnungsgemäß funktionieren). In dieser Version wird das Schließen wie gewünscht vermieden, aber ich finde das Gegenteil interessanter und spielerischer. Um dies zu erreichen, ändern Sie die Zeile $s=$t if!grep...in $s=$t if grep....

use Image::Magick;
sub p{/x/;@o=$r->GetPixel(y=>$'+pop,x,$`+pop);"@o"}
sub o{$w=&p;"0 0 0"eq$w?3:&p eq$w}
sub f{$r->FloodfillPaint(y=>$J+$',x,$I+$&,channel,All,fill,@_)}
($i=Image::Magick->new)->Read(@ARGV);$r=$b=$i->[0];
$h=$b->Get(rows)+112;$:=$b->Get(width)+112;
$b->Extent(geometry,"$:x$h-56-56",background,none);
@v=grep p()eq"0 0 0",map{map-54+55*$_.x.($'*55-54),//..$:/55}1..$h/55;
sub w{$_=pop;/x/;abs($:-2*$`)+abs($h-2*$')}@v=sort{w($b)<=>w($a)}@v;
map{map{/x/;$I=$`;$J=$';$r=$b->Clone();
($t=$r)->Composite(image,$i->[1],x,$I,y=>$J);
if((o(27,0,27,-1)&o(0,27,-1,27)&o(27,54,27,55)&o(54,27,55,27))==1){
$s=$t if!grep{/../;$r=$t->Clone();f(none);f(red);
!grep{p()eq"1 0 0"}@v}
map{/..$/;($_,$&.$`)}map{($_.-1,$_.55)}10,27,45;
$o=$r=$t;}$i->[1]->Rotate(degrees,90)}($_)x4}@v;
$s||=$o or exit 1;$s->Trim();$s->Write("car.png")

Verbrauch: perl car.pl board.png tile.png. Ergebnis gespeichert in car.png. Der Beendigungsstatus ist 1, wenn die Kachel nicht platziert werden konnte.

Skript zum Ausführen eines vollständigen Spiels. Es wird davon ausgegangen, dass sich der obige Code in der Datei befindetcar.pl und die Kacheln im tilesVerzeichnis mit dem Namen " 01.pngto" gespeichert sind 25.png.

use List::Util shuffle;$x='00';
@t=shuffle map{($x++)x$_}split'',a4582941333353325523152111;
`cp tiles/11.png car.png`;
$i++,`perl car.pl car.png tiles/$_.png`,print"placed $i\n"for@t

Das läuft jetzt ziemlich langsam. 8-12 Minuten auf meiner Maschine. Beim Schließen bevorzugt: Beim Schließen vermieden (beachten Sie, dass nichts geschlossen ist).

Common Lisp, 2650 2221 1992 1186 1111 Bytes

Update: "Leichtes" Golfen jetzt erledigt, weitere Gewinne erfordern größere Änderungen.

Update 2: Da die Konkurrenz immer härter wird, werden in der neuen Version keine Positionen im aktuellen Spielfeldrechteck mehr bevorzugt (das wären 57 Byte mehr). Diese Option sowie eine einfache Geschwindigkeitsoptimierung sind in der herunterladbaren Version mit dem Simulator standardmäßig aktiviert, in der folgenden offiziellen Antwort jedoch nicht.

Update 3: Kleinere Änderungen an der Benutzeroberfläche, um die Anzahl der Hauptbytes zu erhöhen.

Ich habe auch eine einfache Web-Benutzeroberfläche erstellt. Das Gesamtpaket (eine einzelne LISP-Datei und die Kachelbilder) kann sein heruntergeladen werden . Um zu versuchen, installieren hunchentoot, zpngund png-readmit quiclisp, Last in carcassonne.lisp, und eine Verbindung zu localhost:8080. Der Code wurde unter CCL / Windows und SBCL / Linux getestet. Die oben genannten Bibliotheken werden nur für den UI / Simulator-Teil benötigt; Die Lösung selbst ist ANSI Common Lisp.

(defun c(f p &aux b a s z(c 55))
  (macrolet((d(v l &body b)`(dotimes(,v,l),@b))
            (b(b c)`(d i c(d j c(setf,b,c))))
            (r(&rest p)`(aref,@p))
            (n(u v i j)`(and(setf l(*(f,u,v)l))
                            (find(r f(+,u,i)(+,v,j))`(0,(r f,u,v))))))
    (labels((p(p w)(d y(ceiling w 2)(d x(- w y y)(rotatef(r p y #6=(+ x y))(r p #6##7=(- w y))(r p #7##8=(- w x y))(r p #8#y)))))
            (a(y x)(or(if(= 0(r f y x))1 #4=(and(= 1(incf(r s y x)))(=(r f y x)z)(push`(,y,x)a)0))0))
            (f(y x)(setf z(r f y x))(if #4#(loop for((y x))= a while(pop a)maximize(+(a(1- y)x)(a y(1- x))(a(1+ y)x)(a y(1+ x))))1)))
      (d i 8(when(d x #1=(array-dimension f 0)(or(= 0(r f(- #1#52 i)x))(return t)))(setf f(adjust-array f`(#2=,(+ #1#c)#2#))))(p f(1- #1#)))
      (d i 4(d u #9=(/ #1#c)(d v #9#
        (let((y(* u c))(x(* v c))(l 9e9))
          (when(= 0(r f y x))
            (b #10=(r f(+ y i)(+ x j))(r p i j))
            (setf s(make-array`(,#1#,#1#))a())
            (ignore-errors(if(> #11=(*(loop for d from 1 to 53
                                            sum(+(n y #3=(+ x d)-1 0)(n #5=(+ y d)(+ 54 x)0 1)(n(+ 54 y)#3#1 0)(n #5#x 0 -1)))
                                      (1+ l))
                                (or(car b)0))
                             (setf b`(,#11#,i,y,x))))
            (b #10#0)))))
         (p p 54))
      (when b(d j(cadr b)(p p 54))(b(r f(+(third b)i)(+(nth 3 b)j))(r p i j)))
      `(,f,b))))

Alle Zeilenvorschübe und Zeilenabstände sind nur für kosmetische Zwecke gedacht, um die Lesbarkeit zu gewährleisten, und werden nicht in die Gesamtsumme eingerechnet.

Sie sollten die Funktion cmit zwei Argumenten aufrufen : dem aktuellen Spielfeld und dem zu platzierenden Plättchen. Beide sollten 2D-Arrays sein. die Kachel 55x55 und das Feld ein Vielfaches davon. Zusätzlich muss das Feldarray einstellbar sein. Die Funktion gibt eine Liste mit zwei Elementen mit dem neuen Feld als erstem Argument zurück. Das zweite Element ist, NILwenn die Kachel nicht platziert werden kann, oder eine Liste, die die Koordinaten oben links und die Drehung der neuesten Kachel in diesem Array sowie die Punktzahl für diese Kachel enthält. Diese Informationen können zu Visualisierungszwecken verwendet werden.

Beachten Sie, dass Sie in weiteren Aufrufen das neue Feld verwenden müssen, das von zurückgegeben wird, cauch wenn das zweite Listenelement ist NIL(das ursprüngliche Array wurde möglicherweise adjust-arraybearbeitet und damit ungültig gemacht).

Der Code ist jetzt etwas langsam, die Optimierung der Bytezahl führt zu redundanten Berechnungen. Das folgende Beispiel wurde in ungefähr drei Minuten auf meinem System ausgeführt.

Beispiellauf für alle 85 Kacheln:

Screenshot der Weboberfläche:

DarkBASIC Pro: 2078 1932 1744 Bytes

UPDATE: Nur mehr Golfaufwand

UPDATE: Entspricht jetzt vollständig der Spezifikation, einschließlich der Bevorzugung nicht abschließender Auswahlmöglichkeiten.

Ich habe mich für DarkBASIC entschieden, weil es zwar ziemlich ausführlich ist, aber einen äußerst unkomplizierten und einfachen Befehlssatz für die Bearbeitung von Bildern bietet.

Ich habe eine EXE-Datei für Personen hochgeladen, die nicht über den DarkBASIC-Compiler verfügen ( Windows ) .

#constant m memblock
#constant f function
#constant k endfunction
#constant z exitfunction
#constant i image
#constant e endif
#constant t then
#constant o or
#constant s paste image
#constant n next
#constant r for
set i colorkey 0,20,0:load i "map.png",1:f$="next.png"
if file exist(f$)=0 t f$=str$(rnd(24)+1)+".png"
load i f$,2:make m from i 1,1:make m from i 2,2
global ts,h,j,u,v,td
ts=i width(2):h=i width(1):j=i height(1):u=h/ts:v=j/ts:td=ts*2
create bitmap 2,h+td+1,j+td+1:r b=1 to 4:r xx=0 to u+1:r yy=0 to v+1:x=xx*ts-1:y=yy*ts-1
cls 5120:s 1,ts,ts,1:if (a(x+1,y) o a(x,y+1) o a(x-ts,y) o a(x,y-ts)) and a(x,y)=0
x1=ts*xx:y1=ts*yy:make i from m 2,2:s 2,x1,y1,1
cl=0:r fd=0 to 1:r x2=1 to ts-2:r yt=0 to 1:y2=yt*ts-yt:y3=yt*ts+yt-1
aa=x2:ab=x2:ba=y2:bb=y3:t2=y1:r t3=0 to 1:p=point(x1+aa,y1+ba):q=point(x1+ab,y1+bb)
if p<>q and rgbg(q)<>20 and t2+b>0 t goto fa
if fd and p<>0xFF0000
if l(x1+aa,y1+ba,p)=0 t cl=1
e
aa=y2:ba=x2:bb=x2:ab=y3:t2=x1:n t3:n yt:n x2:n fd:dn=1:c=xx-1:g=yy-1:make i from m 3,2:if cl=0 t goto dm
e
fa:
n y:n x
d=ts/2:r x=0 to d:r y=0 to d-1:vx=ts-1-x:vy=ts-1-y:t1=rd(x,y):t2=rd(vy,x):wr(vy,x,t1):t1=rd(vx,vy):wr(vx,vy,t2):t2=rd(y,vx):wr(y,vx,t1):wr(x,y,t2):n x:n y:n b
dm:
if dn=0 t report error "Not placed"
p=c<0:q=g<0:t1=h+ts*(p o c>=u):t2=j+ts*(q o g>=v):cls 5120:p=ts*p:q=ts*q:s 1,p,q,1:s 3,c*ts+p,g*ts+q,1:get i 1,0,0,t1,t2,1:save i "map.png",1
end
f l(x,y,w)
if x<0 o y<0 o x>=h+td o y>=j+td t z 1
p=point(x,y)
if rgbg(p)=20 t z 1
if p<>w t z 0
dot x,y,0xFF0000:rt=l(x+1,y,p) o l(x-1,y,p) o l(x,y+1,p) o l(x,y-1,p)
k rt
f rd(x,y)
w=m dword(2,0):b=m dword(2,12+(y*w+x)*4)
k b
f wr(x,y,d)
w=m dword(2,0):write m dword 2,12+(y*w+x)*4,d
k
f a(x,y)
if x<0 o y<0 o x>=h o y>=j t z 0
b=m byte(1,15+(y*h+x)*4)
k b