El juego de mesa

En el juego de mesa " Carcassonne ", los jugadores colocan fichas haciendo coincidir sus bordes y obtienen los puntajes más altos al crear grandes áreas contiguas de terreno. Los siguientes son (aproximadamente) los tipos y cantidades de fichas incluidas en el juego:

#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 tarea

Debe colocar un mosaico haciendo coincidir los bordes, mientras trata de mantener las áreas contiguas de terreno más grandes posibles.

Colocación

• Las fichas solo se pueden colocar en uno de los espacios en blanco (hasta 4) adyacentes a cualquier ficha existente (o fichas) en el área de juego.
• Las baldosas se pueden girar 90, 180 o 270 grados.

Coincidencia de bordes

• Los bordes de un mosaico colocado deben coincidir con los bordes en contacto de los (hasta 4) mosaicos vecinos, es decir, los píxeles en contacto son del mismo color.

Terreno contiguo

• "Cerrar un área de terreno" se refiere a colocar un mosaico de manera que cualquier área contigua de color no pueda continuar con más ubicaciones de mosaico.
• Si es posible una ubicación alternativa, se debe elegir sobre cualquier ubicación de mosaico que cierre un área de terreno.
• Si tiene que elegir entre varias ubicaciones de cierre, elija cualquiera. Si tiene que elegir entre varias ubicaciones que no cierran, elija cualquiera.
• No tenga en cuenta # ff00ff (los píxeles de la esquina) al calcular áreas contiguas. Ignore los edificios, es decir, las áreas de color que ya están completamente encerradas dentro de un mosaico.

Entrada

• La entrada es dos imágenes:

  1. El área de juego.

     • El área de juego inicial consta de mosaico #11(un mosaico único).
     • El área de reproducción aumentada creada como salida también debe ser compatible como entrada.

  2. El azulejo a colocar.

     • Todos los mosaicos de ejemplo deben ser compatibles como entrada.

• Determine los bordes coincidentes / terreno contiguo utilizando solo estos datos de imagen. Sin codificación.

Salida

• La salida es una imagen que muestra el área de juego resultante después de colocar el mosaico.
• La imagen debe ser compatible con su propio programa, es decir, puede usarse como entrada de área de reproducción.
• Si es imposible colocar un mosaico, devuelve un error.

Puedes asumir que

• Los mosaicos son siempre de 55 px por 55 px
• Los mosaicos solo presentarán los colores utilizados actualmente en los mosaicos de ejemplo.

Notas

• Su respuesta debe presentar una salida de ejemplo después de al menos 2 pases (se recomienda más).
• Esta es una representación parcial e inexacta del juego de mesa original, no necesita aplicar ninguna de las reglas o tácticas que no se mencionan aquí.

Puntuación

• Su puntuación es el recuento de bytes de su envío.
• Los datos de imagen no están incluidos en su puntaje.
• La puntuación más baja gana.

Es posible que desee escribir un guión que use su sumisión para jugar un juego completo, que podría consistir en:

• Colocando un mosaico elegido pseudoaleatoriamente del conjunto completo de 85.
• Devolver el mosaico al conjunto si no se puede colocar.
• Repetir hasta que se hayan colocado todas las fichas, o hasta que no se puedan colocar dos fichas seguidas.

No se incluirá en el recuento de bytes ni mejorará su puntaje, pero es probable que ofrezca una recompensa por este tipo de respuesta.

Perl 5 con PerlMagick: 875 789 763

No conté la línea que comienza sub w, que se usa para ordenar las posiciones en la distancia al centro para preferir soluciones compactas (ahora funcionan correctamente). En esta versión, el cierre se evita como se solicitó, pero encuentro lo contrario más interesante y fiel al juego. Para lograr eso, cambie la línea $s=$t if!grep...a $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")

Uso: perl car.pl board.png tile.png. Resultado almacenado en car.png. El estado de salida es 1 si no se pudo colocar el mosaico.

Script para ejecutar un juego completo. Se asume que el código anterior se encuentra en el archivo car.ply las baldosas se almacenan en tilesel directorio llamado 01.pnga 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

Esto corre bastante lento ahora. 8-12 minutos en mi máquina. Con cierre preferido: con cierre evitado (tenga en cuenta que nada está cerrado).

Common Lisp, 2650 2221 1992 1186 1111 bytes

Actualización: golf "fácil" ahora hecho, más ganancias requerirán mayores cambios.

Actualización 2: con la competencia cada vez más feroz, la nueva versión ya no favorece las posiciones dentro del rectángulo actual del campo de juego (eso sería 57 bytes adicionales). Esta opción, así como una optimización de velocidad simple, está habilitada de forma predeterminada en la versión descargable con el simulador, pero no en la respuesta oficial a continuación.

Actualización 3: Cambios menores en la interfaz para mayores ganancias de conteo de bytes.

También creé una interfaz de usuario web simple. El paquete completo (un único archivo LISP y las imágenes de mosaico) se puede descargar aquí . Para probarlo, instale hunchentoot, zpngy png-readcon quiclisp, cargue carcassonne.lispy conéctese localhost:8080. El código ha sido probado en CCL / Windows y SBCL / Linux. Las bibliotecas mencionadas anteriormente solo son necesarias para la parte de UI / simulador; la solución en sí es ANSI Common Lisp simple.

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

Todos los avances de línea y el espaciado de inicio de línea son solo para cosméticos, para garantizar la legibilidad, y no se cuentan en la suma total.

Debe llamar a la función ccon dos argumentos: el campo de juego actual y el mosaico para colocar. Ambos deben ser matrices 2D; el mosaico 55x55 y el campo un múltiplo de eso. Además, la matriz de campo debe ser ajustable. La función devuelve una lista de dos elementos con el nuevo campo como primer argumento. El segundo elemento es NILsi el mosaico no se puede colocar, o de lo contrario, una lista que contiene las coordenadas superior izquierda y la rotación del último mosaico en esa matriz y la puntuación para ese mosaico. Esta información puede usarse para fines de visualización.

Tenga en cuenta que en otras llamadas, debe usar el nuevo campo devuelto cincluso si el segundo elemento de la lista es NIL(la matriz original puede haber sido adjust-arrayeditada y, por lo tanto, invalidada).

El código ahora es un poco lento, la optimización de conteo de bytes resulta en cálculos redundantes. El siguiente ejemplo se completó en aproximadamente tres minutos en mi sistema.

Ejemplo de ejecución para las 85 fichas:

Captura de pantalla de la interfaz de usuario web:

DarkBASIC Pro: 2078 1932 1744 bytes

ACTUALIZACIÓN: solo más esfuerzo de golf

ACTUALIZACIÓN: ahora cumple totalmente con las especificaciones, incluida la preferencia de opciones sin cierre.

Elegí DarkBASIC porque, aunque es bastante detallado, proporciona un conjunto de comandos extremadamente sencillo y sencillo para manipular imágenes.

Subí un EXE para personas que no tienen el compilador 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