Beach Trails solver

beach-trails.ts

// Beach Trails solver
// http://github.com/adufilie

enum Dir {N, E, S, W, length}
type Pos = {x:number, y:number, dir:Dir};
type TileCollection = {[tile:string]: number};
const Delta = {X: [0, 1, 0, -1], Y: [-1, 0, 1, 0]};
const OUTER_TILE = '    ';

function rotate(tile:string, direction:Dir)
{
	return direction ? tile.slice(direction).concat(tile.slice(0, direction)) : tile;
}
function numRotations(tile:string):number
{
	if (tile.slice(0, 2) === tile.slice(2))
		return tile[0] === tile[1] ? 1 : 2;
	return 4;
}
function getTileSideChar(tile:string|null, side:Dir)
{
	return (tile || OUTER_TILE)[side];
}

class TileGame
{
	constructor({width, height, tiles}:{width: number, height: number, tiles: TileCollection})
	{
		this.width = width;
		this.height = height;
		this.grid = Array(height).fill(1).map(() => Array(width).fill(null));
		this.tiles = tiles;
	}

	maxDepth = 0;
	width:number;
	height:number;
	grid:(string|null)[][];
	tiles:TileCollection;

	gridToString()
	{
		let separatorLine = `+${Array(this.width).fill('---').join('+')}+`;
		let lines = [separatorLine];
		for (let row of this.grid)
		{
			lines.push(
				`|${row.map(tile => ` ${getTileSideChar(tile, Dir.N)} `).join('|')}|`,
				`|${row.map(tile => `${getTileSideChar(tile, Dir.W)}${tile ? ' ' : '?'}${getTileSideChar(tile, Dir.E)}`).join('|')}|`,
				`|${row.map(tile => ` ${getTileSideChar(tile, Dir.S)} `).join('|')}|`,
				separatorLine,
			);
		}
		return lines.join('\n');
	}

	getAdjacentTile(pos:Pos)
	{
		let x = pos.x + Delta.X[pos.dir];
		let y = pos.y + Delta.Y[pos.dir];
		if (y >= 0 && y < this.height && x >= 0 && x < this.width)
			return this.grid[y][x];
		return OUTER_TILE;
	}

	putTile(tile:string, {x, y}:Pos):boolean
	{
		let gridN = this.getAdjacentTile({x, y, dir: Dir.N});
		let gridE = this.getAdjacentTile({x, y, dir: Dir.E});
		let gridS = this.getAdjacentTile({x, y, dir: Dir.S});
		let gridW = this.getAdjacentTile({x, y, dir: Dir.W});
		let fits = (
			(!gridN || gridN[Dir.S] == tile[Dir.N]) &&
			(!gridE || gridE[Dir.W] == tile[Dir.E]) &&
			(!gridS || gridS[Dir.N] == tile[Dir.S]) &&
			(!gridW || gridW[Dir.E] == tile[Dir.W])
		);
		if (fits)
			this.grid[y][x] = tile;
		return fits;
	}

	removeTile({x, y}:Pos)
	{
		this.grid[y][x] = null;
	}

	nextPos(pos:Pos):Pos|null
	{
		for (let turn = 0; turn < Dir.length; turn++)
		{
			let dir = (pos.dir + turn) % Dir.length;
			if (!this.getAdjacentTile({...pos, dir}))
			{
				let x = pos.x + Delta.X[dir];
				let y = pos.y + Delta.Y[dir];
				return {x, y, dir};
			}
		}
		return null;
	}

	fillGrid(pos:Pos = {x: 0, y: 0, dir: Dir.E}, depth = 0):boolean
	{
		if (depth >= this.maxDepth)
		{
			this.maxDepth = depth;
			let remaining:TileCollection = {};
			for (let tile in this.tiles)
				if (this.tiles[tile] > 0)
					remaining[tile] = this.tiles[tile];
			console.log('new configuration with', this.maxDepth, 'tiles; remaining:', remaining);
			console.log(this.gridToString());
		}

		//console.log(pos, 'try');
		for (let tile in this.tiles)
		{
			if (!this.tiles[tile])
				continue;

			// consume tile
			this.tiles[tile]--;
			let numRot = numRotations(tile);
			for (let rot = 0; rot < numRot; rot++)
			{
				if (this.putTile(rotate(tile, rot), pos))
				{
					// tile fits, try next
					//console.log(pos, 'tile fits', tile);
					let nextPos = this.nextPos(pos);
					if (!nextPos || this.fillGrid(nextPos, depth + 1))
						return true; // success
					// backtrack
					//console.log(pos, 'backtrack', tile);
					this.removeTile(pos);
				}
			}
			// reject tile
			//console.log(pos, 'reject tile', tile);
			this.tiles[tile]++;
		}
		// no tiles fit
		//console.log(pos, 'no tiles fit');
		return false;
	}
}

let game = new TileGame({
	width: 6,
	height: 6,
	tiles: {
		'TTTT': 2,
		'CCCC': 2,
		'TTCC': 3,
		'TCTC': 3,
		'TTT ': 3,
		'CCC ': 3,
		'T T ': 5,
		'C C ': 5,
		'TT  ': 3,
		'CC  ': 3,
		'T   ': 2,
		'C   ': 2
	}
});
if (game.fillGrid())
	console.log(game.gridToString());
else
	console.log('fail');

// sample solution
/*
35 tiles; remaining: {TCTC: 1}
+---+---+---+---+---+---+
|   |   |   |   |   |   |
|  T|T T|T T|T  |   |   |
| T |   |   | T | C | C |
+---+---+---+---+---+---+
| T |   |   | T | C | C |
|   |  C|C C|C C|C C|C  |
| T | C |   | T | C | C |
+---+---+---+---+---+---+
| T | C |   | T | C | C |
|  T|T T|T T|T T|T C|C  |
| T | C |   | T | T | C |
+---+---+---+---+---+---+
| T | C |   | T | T | C |
|   |   | ? |T T|T  |   |
| T | C |   | T | T | C |
+---+---+---+---+---+---+
| T | C | C | T | T | C |
|  T|T C|C C|C T|T  |   |
| T | T | C | C |   | C |
+---+---+---+---+---+---+
| T | T | C | C |   | C |
|   |   |  C|C C|C C|C  |
|   |   |   |   |   |   |
+---+---+---+---+---+---+
*/

rules.jpg