Le jeu de plateau

Dans le jeu de société " Carcassonne ", les joueurs placent des tuiles en faisant correspondre leurs bords et gagnent les meilleurs scores en créant de grandes zones de terrain contiguës. Voici (grosso modo) les types et quantités de tuiles incluses dans le jeu:

#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

La tâche

Vous devez placer une tuile en faisant correspondre les bords, tout en essayant de conserver les plus grandes zones de terrain contiguës possibles.

Placement

• Les tuiles ne peuvent être placées que dans l'un des (jusqu'à 4) espaces vides adjacents à toute tuile (ou tuiles) existante dans la zone de jeu.
• Les carreaux peuvent être tournés de 90, 180 ou 270 degrés.

Correspondance des bords

• Les bords d'une tuile placée doivent correspondre aux bords en contact des (jusqu'à 4) tuiles voisines, c'est-à-dire que les pixels en contact sont de la même couleur.

Terrain contigu

• La «fermeture d'une zone de terrain» fait référence au placement d'une tuile de telle sorte qu'aucune zone de couleur contiguë ne puisse ensuite être poursuivie avec d'autres placements de tuiles.
• Si un placement alternatif est possible, il doit être choisi par rapport à tout placement de tuiles qui fermerait une zone de terrain.
• Si vous devez choisir entre plusieurs emplacements de clôture, choisissez-en un. Si vous devez choisir entre plusieurs emplacements non fermés, choisissez-en un.
• Ignorez # ff00ff (les pixels d'angle) lors du calcul des zones contiguës. Ne tenez pas compte non plus des bâtiments, c'est-à-dire des zones de couleur déjà entièrement enfermées dans une tuile.

Contribution

• L'entrée est deux images:

  1. L'aire de jeux.

     • La zone de jeu initiale est constituée de tuiles #11(une seule tuile).
     • La zone de lecture augmentée créée en sortie doit également être prise en charge en entrée.

  2. La tuile à placer.

     • Tous les exemples de tuiles doivent être pris en charge en entrée.

• Déterminez les bords / terrains contigus correspondants en utilisant uniquement ces données d'image. Pas de codage en dur.

Sortie

• La sortie est une image montrant la zone de jeu résultante après avoir placé la tuile.
• L'image doit être compatible avec votre propre programme, c'est-à-dire qu'elle peut être utilisée comme entrée de zone de lecture.
• S'il est impossible de placer une tuile, retournez une erreur.

Vous pouvez supposer que

• Les tuiles mesurent toujours 55 px par 55 px
• Les tuiles ne comporteront que les couleurs actuellement utilisées dans les tuiles d'exemple.

Remarques

• Votre réponse doit comporter un exemple de sortie après au moins 2 passages (plus est encouragé).
• Il s'agit d'un rendu partiel et inexact du jeu de société d'origine, vous n'avez pas besoin d'appliquer les règles ou tactiques non mentionnées ici.

But

• Votre score est le nombre d'octets de votre soumission.
• Les données d'image ne sont pas incluses dans votre score.
• Le score le plus bas l'emporte.

Vous voudrez peut-être écrire un script qui utilise votre soumission pour jouer à un jeu complet, qui pourrait consister en:

• Placer une tuile choisie de manière pseudo-aléatoire parmi l'ensemble complet de 85.
• Rendre la tuile à l'ensemble si elle ne peut pas être placée.
• Répéter jusqu'à ce que chaque tuile ait été placée - ou jusqu'à ce que deux tuiles d'affilée ne puissent pas être placées.

Il ne sera pas inclus dans votre nombre d'octets, ou améliorera votre score, mais je proposerai probablement une prime à ce type de réponse.

Perl 5 avec PerlMagick: 875 789 763

Je n'ai pas compté la ligne commençant par sub w, qui sert à trier les positions sur la distance au centre pour privilégier les solutions compactes (fonctionne désormais correctement). Dans cette version, la fermeture est évitée comme demandé mais je trouve le contraire plus intéressant et plus fidèle au jeu. Pour y parvenir, changez la ligne $s=$t if!grep...en $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")

Utilisation: perl car.pl board.png tile.png. Résultat stocké dans car.png. Le statut de sortie est 1 si la tuile n'a pas pu être placée.

Script pour exécuter un jeu complet. Il suppose que le code ci - dessus est dans le fichier car.plet les carreaux sont stockés dans le tilesrépertoire nommé 01.pngà 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

Cela fonctionne assez lentement maintenant. 8-12 minutes sur ma machine. Avec fermeture préférée: Avec fermeture évitée (notez que rien n'est fermé).

Lisp commun, 2650 2221 1992 1186 1111 octets

Mise à jour: golf "facile" maintenant terminé, les gains supplémentaires nécessiteront des changements plus importants.

Mise à jour 2: Avec la concurrence de plus en plus féroce, la nouvelle version ne favorise plus les positions à l'intérieur du rectangle du terrain de jeu actuel (qui serait de 57 octets supplémentaires). Cette option, ainsi qu'une simple optimisation de la vitesse, sont activées par défaut dans la version téléchargeable avec le simulateur, mais pas dans la réponse officielle ci-dessous.

Mise à jour 3: modifications mineures de l'interface pour les gains de comptage d'octets majeurs.

J'ai également créé une interface utilisateur Web simple. Le package complet (un seul fichier LISP et les images des tuiles) peut être téléchargé ici . Pour l' essayer, installer hunchentoot, zpnget png-readavec quiclisp, chargez carcassonne.lispet connectez - vous localhost:8080. Le code a été testé sur CCL / Windows et SBCL / Linux. Les bibliothèques mentionnées ci-dessus ne sont nécessaires que pour la partie UI / simulateur; la solution elle-même est un simple Lisp commun ANSI.

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

Tous les sauts de ligne et les espacements de début de ligne sont uniquement destinés aux cosmétiques, pour garantir la lisibilité, et ne sont pas pris en compte dans la somme totale.

Vous devez appeler la fonction cavec deux arguments: le champ de jeu actuel et la tuile à placer. Les deux doivent être des tableaux 2D; la tuile 55x55 et le champ un multiple de cela. De plus, la matrice de champs doit être réglable. La fonction renvoie une liste à deux éléments avec le nouveau champ comme premier argument. Le deuxième élément est NILsi la tuile ne peut pas être placée, ou sinon une liste contenant les coordonnées en haut à gauche et la rotation de la dernière tuile sur ce tableau et le score pour cette tuile. Ces informations peuvent être utilisées à des fins de visualisation.

Notez que dans les appels ultérieurs, vous devez utiliser le nouveau champ renvoyé par cmême si le deuxième élément de la liste l'est NIL(le tableau d'origine peut avoir été adjust-arraymodifié et donc invalidé).

Le code est maintenant un peu lent, l'optimisation du nombre d'octets entraînant des calculs redondants. L'exemple ci-dessous s'est terminé en environ trois minutes sur mon système.

Exemple d'exécution pour les 85 tuiles:

Capture d'écran de l'interface utilisateur Web:

DarkBASIC Pro: 2078 1932 1744 octets

MISE À JOUR: juste plus d'efforts de golf

MISE À JOUR: Répond maintenant pleinement aux spécifications, y compris en préférant les choix non fermés.

J'ai choisi DarkBASIC parce que bien qu'il soit assez verbeux, il fournit un jeu de commandes extrêmement direct et simple pour manipuler les images.

J'ai téléchargé un EXE pour les personnes qui n'ont pas le compilateur DarkBASIC ( 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