# Place a Carcassonne tile

The board game

In the board game "Carcassonne" players place tiles by matching their edges and earn the highest scores through creating large contiguous areas of terrain. The following are (roughly) the types and quantities of tiles included in the game:

#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

You must place a tile by matching edges, while trying to maintain the largest possible contiguous areas of terrain.

Placement

• Tiles can only be placed in one of the (up to 4) blank spaces adjacent to any existing tile (or tiles) in the play area.
• Tiles can be rotated 90, 180 or 270 degrees.

Edge-matching

• Edges of a placed tile must match the touching edges of the (up to 4) neighbouring tiles, i.e. touching pixels are the same colour.

Contiguous terrain

• "Closing an area of terrain" refers to placing a tile such that any contiguous area of colour could not then be continued with further tile placements.
• If an alternative placement is possible, it must be chosen over any tile placement that would close an area of terrain.
• If you have to choose between a number of closing placements, choose any. If you have to choose between a number of non-closing placements, choose any.
• Disregard #ff00ff (the corner pixels) when calculating contiguous areas. Also disregard buildings, i.e. areas of colour already fully enclosed within a tile.

Input

• Input is two images:

1. The play area.

• The initial play area consists of tile #11 (a single tile).
• The augmented play area created as output must also be supported as input.
2. The tile to be placed.

• All of the example tiles must be supported as input.
• Determine matching edges/contiguous terrain using this image data alone. No hardcoding.

Output

• Output is an image showing the resultant play area after placing the tile.
• The image must be compatible with your own program, i.e. it can be used as play area input.
• If it's impossible to place a tile, return an error.

You can assume that

• Tiles are always 55 px by 55 px
• Tiles will only ever feature the colours currently used in the example tiles.

Notes

• Your answer must feature example output after at least 2 passes (more is encouraged).
• This is a partial and inaccurate rendering of the original board game, you don't need to apply any of the rules or tactics not mentioned here.

Score

• Image data isn't included in your score.
• Lowest score wins.

Playing a full game

You may wish to write a script that uses your submissison to play a full game, which might consist of:

• Placing a tile chosen pseudorandomly from the full set of 85.
• Returning the tile to the set if it can't be placed.
• Repeating until every tile has been placed - or until two tiles in a row can't be placed.

It won't be included in your byte count, or improve your score, but I'll likely offer a bounty to this kind of answer.

• what is the differenct between 12, 15, and 17? Nov 7, 2014 at 16:22
• thanks for catching that, 17 was a duplicate. however 15 does differ as it can potentially close an area of terrain. (btw, areas of colour aren't contiguous if only the corners of pixels touch)
– jsh
Nov 7, 2014 at 16:33
• So one 15 and two 2s could make 2 separate black sections of size 2. While one 12 and two 2s could make a black sections that is 3 big instead. Ok. Nov 7, 2014 at 16:37
• 1. if you could use the ms paint fill bucket tool to change the colour of an area it is a contiguous area. in your example there would be 7 contiguous areas. 2. that sounds reasonable. as long as you use two images as specified you can do this however you want. 3. you can depict blank space in any way you like. transparency is a good option. you could also use any colour not featured in the example tiles.
– jsh
Nov 8, 2014 at 2:34
• @hosch250 the play area is infinite (extends as necessary). With just the first tile on the play, the first tile is the whole play area. Nov 10, 2014 at 1:19

# Common Lisp, 2650222119921186 1111 bytes

Update: "Easy" golfing now done, further gains will require bigger changes.

Update 2: With the competition getting fiercer, the new version no longer favors positions inside the current playing field rectangle (that would be 57 bytes extra). This option, as well as a simple speed optimization, is by enabled by default in the downloadable version with the simulator, but not in the official answer below.

Update 3: Minor interface changes for major byte count gains.

I created a simple Web UI as well. The full package (a single LISP file and the tile images) can be downloaded here. To try it, install hunchentoot, zpng and png-read with quiclisp, load in carcassonne.lisp, and connect to localhost:8080. The code has been tested on CCL/Windows and SBCL/Linux. The above mentioned libraries are only needed for the UI/simulator part; the solution itself is plain 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))))


All line feeds and line-starting spacing are for cosmetics only, to ensure legibility, and not counted into the total sum.

You should call the function c with two arguments: The current play field, and the tile to place. Both should be 2D arrays; the tile 55x55 and the field a multiple of that. Additionally, the field array must be adjustable. The function returns a two-element list with the new field as its first argument. The second element is NIL if the tile cannot be placed, or otherwise a list containing the top-left coordinates and rotation of the latest tile on that array and the score for that tile. This information can be used for visualization purposes.

Note that in further calls, you must use the new field returned by c even if the second list element is NIL (the original array may have been adjust-arrayed and thus invalidated).

The code is now a bit on the slow side, byte count optimization resulting in redundant calculations. The example below completed in about three minutes on my system.

Example run for all 85 tiles:

Web UI screenshot:

• Preferring the placement to be within the current rectangle is a good idea. I was noticing that it tends to be snakey if you take the easy route.
– BMac
Nov 10, 2014 at 5:50
• not the winning score, but you get the bounty for a few nice innovations.
– jsh
Nov 17, 2014 at 14:51

# DarkBASIC Pro: 20781932 1744 bytes

UPDATE: Just more golfing effort

UPDATE: Now fully meets the spec, including preferring non-closing choices.

I chose DarkBASIC because while it's rather verbose, it provides an extremely straightforward and simple command set for manipulating images.

I uploaded an EXE for people who don't have the DarkBASIC compiler (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  # Perl 5 with PerlMagick: 875 789 763 I did not count the line starting with sub w, which is used to sort positions on the distance to the center to prefer compact solutions (now working properly). In this version closing is avoided like requested but I find the opposite more interesting and true to the game. To achieve that change the line $s=$t if!grep... to $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")


Usage: perl car.pl board.png tile.png. Result stored in car.png. Exit status is 1 if the tile could not be placed.

Script to run a complete game. It assumes the code above is in the file car.pl and the tiles are stored in tiles directory named 01.png to 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


This runs quite slowly now. 8-12 minutes on my machine. With closing preferred: With closing avoided (note nothing is closed).

• The area close test seems to not work properly. The city-with-road-corner tile at (0,1) was the last one placed. Nov 11, 2014 at 5:06
• @jlahd You are right. For tests I reversed the condition as it is much easier not to close a region (also it is a better strategy in the actual game to close them). But now I am not sure if this reverse condition even works properly. I will fix that today. Nov 11, 2014 at 7:05
• @jlahd Fixed, thanks for noticing. The opposite condition was OK after all BTW. Nov 11, 2014 at 9:17