Speed Coding 2016 – Q4

6 July 2016, by

Here’s the 4th and final question from our last speed coding competition. This is a long and tricky one, so make sure you’ve put some time aside if you’re planning to try and solve it.

Question 4

Carcassonne is a board game where you assemble square tiles into a region of French countryside, building roads, fields, cities and monasteries. We are playing with the basic set, i.e. no river. There are 24 different types of tile in the game. Copies of the tiles can be found on JCloisterZone’s github here.

Each edge of each tile can be field, city or road. Tiles must be placed adjacent to existing tiles so that all adjoining edges are of the same type, i.e. city to city, road to road and field to field. They may be rotated any way to fit, but not flipped. We have a finite number of each tile in the quantities shown:

 Tile Name Number of tiles C 5 CC.2 2 CFC.2 3 CFc+ 2 CFc.1 1 CRRR 3 CRr 3 Cc+ 2 Cc.1 3 CcRr+ 2 CcRr 3 Ccc+ 1 Ccc 3 CccR+ 2 CccR 1 Cccc+ 1 L 4 LR 2 RCr 4 RFr 8 RRR 4 RRRR 1 Rr 9 RrC 3

Your challenge is to build a legal 7×7 board, with the usual starting tile “RCr” as the centre square unrotated. To make it a bit harder we’re going to introduce some extra restrictions too.

• You may not place two instances of the same tile type adjacent to each other, even diagonally.
• You may not place two monasteries (tiles “L” or “LR”) adjacent to each other, even diagonally.
• You may not place two city tiles with coats of arms (tiles with a “+” in the name) adjacent to each other, even diagonally.

You should

• read in the basic tile data (name, quantity, edges) into a suitable data structure
• assemble a 7×7 board
• place “RCr” in the centre square
• fill up the remaining squares so that all internal edges of our board have matching tile edge types i.e. road joins with road, city with city, and obeying the additional adjacency rules above
• use each tile only up to the quantity shown, e.g. you may only use four of tile “RCr” including the central square

The timed problem

Assemble the board as a 840×840 image using the tile images provided, rotating as necessary.

Hint: Note that whilst there are four possible rotations of tile “LR” you can use, with the road pointing north south east or west, rotating tile “L” makes no difference to the set of edges it presents. Similarly there are only two orientations of tile “CFc+” worth testing.

Bonus challenge

There are 72 tiles in the Carcassonne set: construct a 9×8 board that uses all of the tiles. (There are now two equally-middle squares: you may place the starting tile in either of them.)

Categories: Social, Softwire, Technical