O jogo de tabuleiro

No jogo de tabuleiro " Carcassonne ", os jogadores colocam peças combinando suas bordas e obtêm as pontuações mais altas criando grandes áreas contíguas do terreno. A seguir, são (aproximadamente) os tipos e quantidades de peças incluídas no jogo:

#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

A tarefa

Você deve colocar um ladrilho combinando com as arestas, enquanto tenta manter as maiores áreas contíguas possíveis do terreno.

Canal

• As peças podem ser colocadas apenas em um dos (até 4) espaços em branco adjacentes a qualquer peça (ou peça) existente na área de recreação.
• Os ladrilhos podem ser girados 90, 180 ou 270 graus.

Correspondência de arestas

• As arestas de um ladrilho colocado devem corresponder às arestas tocantes dos (até 4) ladrilhos vizinhos, ou seja, os pixels tocantes são da mesma cor.

Terreno contíguo

• "Fechar uma área do terreno" refere-se à colocação de um ladrilho de forma que qualquer área contígua de cor não possa ser continuada com mais posicionamentos de ladrilho.
• Se um posicionamento alternativo for possível, ele deverá ser escolhido sobre qualquer posicionamento de ladrilho que feche uma área do terreno.
• Se você precisar escolher entre vários canais de fechamento, escolha um. Se você precisar escolher entre vários canais sem fechamento, escolha qualquer.
• Desconsidere # ff00ff (os pixels de canto) ao calcular áreas contíguas. Também desconsidere edifícios, ou seja, áreas de cores já totalmente fechadas dentro de um ladrilho.

Entrada

• A entrada possui duas imagens:

  1. A área de recreação.

     • A área de reprodução inicial consiste em bloco #11(um bloco único).
     • A área de reprodução aumentada criada como saída também deve ser suportada como entrada.

  2. O ladrilho a ser colocado.

     • Todos os blocos de exemplo devem ser suportados como entrada.

• Determine arestas correspondentes / terreno contíguo usando apenas esses dados de imagem. Sem codificação.

Saída

• Saída é uma imagem que mostra a área de reprodução resultante após a colocação do ladrilho.
• A imagem deve ser compatível com o seu próprio programa, ou seja, pode ser usada como entrada na área de reprodução.
• Se for impossível colocar um bloco, retorne um erro.

Você pode assumir que

• As peças são sempre 55 px por 55 px
• Os ladrilhos apenas apresentam as cores usadas atualmente nos ladrilhos de exemplo.

Notas

• Sua resposta deve apresentar exemplo de saída após pelo menos 2 passagens (mais é incentivado).
• Esta é uma renderização parcial e imprecisa do jogo de tabuleiro original. Você não precisa aplicar nenhuma das regras ou táticas não mencionadas aqui.

Ponto

• Sua pontuação é a contagem de bytes do seu envio.
• Os dados da imagem não estão incluídos na sua pontuação.
• Menor pontuação ganha.

Você pode escrever um script que use sua submissão para jogar um jogo completo, que pode consistir em:

• Colocando um bloco escolhido pseudo-aleatoriamente do conjunto completo de 85.
• Retornando o bloco ao conjunto, se não puder ser colocado.
• Repetindo até que cada peça tenha sido colocada - ou até que duas peças seguidas não possam ser colocadas.

Ele não será incluído na sua contagem de bytes ou melhorará sua pontuação, mas provavelmente vou oferecer uma recompensa para esse tipo de resposta.

Perl 5 com PerlMagick: 875 789 763

Não contei a linha inicial sub w, que é usada para classificar as posições à distância do centro para preferir soluções compactas (agora funcionando corretamente). Nesta versão, o fechamento é evitado como solicitado, mas acho o oposto mais interessante e fiel ao jogo. Para conseguir isso, mude a linha $s=$t if!grep...para $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 armazenado em car.png. O status de saída é 1 se o bloco não puder ser colocado.

Script para executar um jogo completo. Ele assume que o código acima está no arquivo car.ple os blocos são armazenados no tilesdiretório denominado01.png para 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

Isso corre bem devagar agora. 8-12 minutos na minha máquina. Com fechamento preferido: Com fechamento evitado (observe que nada está fechado).

Common Lisp, 2650 2221 1992 1186 1111 bytes

Atualização: O golfe "fácil" agora está pronto, mais ganhos exigirão mudanças maiores.

Atualização 2: Com a competição cada vez mais acirrada, a nova versão não favorece mais as posições dentro do atual retângulo do campo de jogo (isso seria 57 bytes extra). Essa opção, além de uma simples otimização de velocidade, é ativada por padrão na versão para download com o simulador, mas não na resposta oficial abaixo.

Atualização 3: Pequenas alterações na interface para maiores ganhos na contagem de bytes.

Também criei uma interface da Web simples. O pacote completo (um único arquivo LISP e as imagens em bloco) pode ser baixado aqui . Para experimentá-lo, instale e hunchentoot, com o quiclisp, carregue e conecte-se a . O código foi testado no CCL / Windows e SBCL / Linux. As bibliotecas mencionadas acima são necessárias apenas para a parte da interface do usuário / simulador; a solução em si é simples ANSI Common Lisp.zpngpng-readcarcassonne.lisplocalhost:8080

(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 os feeds de linha e espaçamento inicial são apenas para cosméticos, para garantir a legibilidade e não são contabilizados na soma total.

Você deve chamar a função ccom dois argumentos: o campo de jogo atual e o bloco a ser colocado. Ambos devem ser matrizes 2D; o bloco 55x55 e o campo um múltiplo disso. Além disso, a matriz de campos deve ser ajustável. A função retorna uma lista de dois elementos com o novo campo como seu primeiro argumento. O segundo elemento éNIL se o bloco não puder ser colocado ou uma lista contendo as coordenadas no canto superior esquerdo e a rotação do bloco mais recente nessa matriz e a pontuação desse bloco. Esta informação pode ser usada para fins de visualização.

Observe que em outras chamadas, você deve usar o novo campo retornado, cmesmo que o segundo elemento da lista seja NIL(a matriz original pode ter sidoadjust-array ed e, portanto, invalidada).

O código agora está um pouco lento, otimizando a contagem de bytes, resultando em cálculos redundantes. O exemplo abaixo foi concluído em cerca de três minutos no meu sistema.

Exemplo de execução para todos os 85 blocos:

Captura de tela da interface do usuário da Web:

DarkBASIC Pro: 2078 1932 1744 bytes

ATUALIZAÇÃO: Apenas mais esforço no golfe

ATUALIZAÇÃO: agora atende plenamente às especificações, incluindo a escolha de opções sem fechamento.

Eu escolhi o DarkBASIC porque, embora seja bastante detalhado, fornece um conjunto de comandos extremamente direto e simples para manipular imagens.

Fiz upload de um EXE para pessoas que não possuem o 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