Technical Exam - Valid Chess Moves

This technical exam question involves taking a chess board as a nested array consisting of <colour><piece> pairs such as "wp" for white pawn or "bk" for black knight, and calculating the total number of valid moves for either side.

Given a valid chess board as a 2D array, calculate the number of valid moves for either side.

Pieces are represented by 2 character strings where the first character is w or b for white or back, and the second character represents which piece is in that position:

no chartacter for Pawn
b for Bishop
n for Knight
r for Rook
q for Queen
k for King

The size of the board and the number of each piece on the board may not follow chess rules. For example, a valid input may be:

$board = [
  ['a' => 'w', 'b' => 'w'],
  ['a' => '', 'b' => ''],
  ['a' => 'b', 'b' => 'b']
];

And the correct output would be:
4
Since both players currently have 2 moves available.

You must use at least 1 class to represent the pieces and 1 class to represent the board, but you can use as many as you like.

Aside from Ghost's inability to list code blocks inside of quotes, this is a fairly simple question that is going to devolve into a lengthy answer.

The Board and the Game State

My immediate reaction is to question what purpose the Board class is going to have, other than being a requirement and clean code. Perhaps that's my own experience with Ludum Dare and terrible 2D arrays to represent maps and playable areas coming through though.

Since it's a requirement though, let's use it to handle the "game state" and get board initialization taken care of.

In its most basic form, the board needs to:

• be created to an arbitrary size
• keep track of some state (the pieces on the board)
• allow placing a piece on the board
• allow retrieving the piece on the board at a position

Since we don't have the pieces defined yet we can use their string values still. A really simple implementation of the board logic would look like:

class Board
{
	private array $state = [];

	public function __construct(int $rows, int $columns)
	{
		$this->state = array_fill(0, $rows, array_fill(0, $columns, null));
	}

	public function __toString(): string
{
		return json_encode($this->state);
	}

	public function getPiece(string $column, int $row): ?string
	{
		return $this->state[$row -1][$this->alphaToNum($column)] ?? null;
	}

	public function placePiece(string $column, int $row, string $piece): void
	{
		$this->state[$row -1][$this->alphaToNum($column)] = $piece;
	}

	private function alphaToNum(string $char): int
	{
		return ord(strtolower($char)) - 97;
	}
}

To start testing this we can throw together a really simple "game" and view the output, like so:

<?php

use Tharbakim\ChessPlayableMovesSolver\Board;

require('../vendor/autoload.php');

$board = new Board(3, 2);
$board->placePiece('a', 1, 'b');
$board->placePiece('b', 1, 'b');
$board->placePiece('a', 3, 'w');
$board->placePiece('b', 3, 'w');

echo $board;

Which upon running gives up an output of [["b","b"],[null,null],["w","w"]].

We can do slightly better though. What if we abandon the basic json_encoder and attempt to ascii art out way to a better game board As an intermediate step, we can draw out the strings for each piece with 2 loops and add some nice spacing between them:

public function __toString(): string
{
	$board = '';
	foreach ($this->state as $row) {
		foreach ($row as $cell) {
			$board .= str_pad($cell ?? '--', 3);
		}
		$board = rtrim($board);
		$board .= PHP_EOL . PHP_EOL;
	}
	return $board;
}

Which looks a little more board-like:

b b

-- --

w w

But I think we can do slightly better by giving our ascii chart some axis labels. It's certainly not a pretty solution with the mangling of strings, but we have all the information we need to assign labels if we assume we never need to deal with more than 26 columns:

public function __toString(): string
{
	$board = '';
	foreach ($this->state as $index => $row) {
		$rowLabel = sizeof($this->state) - $index;
		$board .= "$rowLabel| ";
		foreach ($row as $cell) {
			$board .= str_pad($cell ?? '--', 3);
		}
		$board = rtrim($board);
		$board .= PHP_EOL . PHP_EOL;
	}
	$columnCount = sizeof($this->state[0]);
	$board = substr($board, 0, -1);
	$board .= '__ ' . str_repeat('__ ', $columnCount) . PHP_EOL;
	$board .= ' | ' . implode('  ', range('a', chr(96 + $columnCount))) . PHP_EOL;
	return $board;
}

Which, finally looks like:

3| b  b 

2| -- --

1| w  w 
__ __ __ 
 | a  b

Side quest completed. We have a basic game board keeping track of our state, and a handy ascii output to help us with debugging along the way.

Putting the Pieces on the Board

Given we have the board it's reasonable to want to put some "real" pieces on it instead of just string representations like we have now. Given that this isn't anarchy chess we know there's 6 different types of pieces that all share some traits we can get started with some simple inheritance and create some empty classes to represent our different pieces.

First, a generic Piece class to house our common traits among all the pieces:

abstract class Piece
{
	public const COLOR_WHITE = 'w';
	public const COLOR_BLACK = 'b';

	protected const PIECE_TYPE = 'INVALID';

	private string $type;

	public function __construct(
		private string $color,
	) {
		if (!in_array($color, [self::COLOR_WHITE, self::COLOR_BLACK])) {
			throw new \InvalidArgumentException('Invalid color');
		}
		$this->type = static::PIECE_TYPE;
	}

	public function __toString(): string
	{
		return $this->color . $this->type;
	}
}

followed by 6 simple classes that all look like this Knight.php example:

<?php

class Knight extends Piece
{
	protected const PIECE_TYPE = 'n';

	public function __construct(string $color)
	{
		parent::__construct($color);
	}
}

Which we can test with a simple 2 lines:

$pawn = new Knight(Piece::COLOR_WHITE);
echo $pawn;

And see an output of wn as expected.

However, I already know I'm not going to want to be sorting through the logic of which piece to generate while we're parsing the input. Instead, this is the right use case for a factory to decide for us.

Is this a Pawn Shop?

Given the question from the top we know that the input for a new piece is always going to be a 1 or 2 character string - the first colour determining the colour of the piece and the second determining the type of piece it represents.

At this point I don't think we actually care about the colour of the pieces when answering the original question but I'm going to carry it forward regardless. Maybe we'll find a use for it after all at the end (did someone say coloured text outputs?).

Instead what we really care about are the 6 permutations we can get when creating a new piece. A small caveat, if we want to map the pieces into an array we'll either need to have an empty array as a key or convert it to another character (such as a space) with padding again. Since empty arrays as keys is gross, we're going to pad.

Still, there remains nothing terribly interesting or complex here and it's all pretty general boilerplate stuff. An almost typical factory to turn 2 character codes into pieces:

class PieceFactory
{
	private const PIECE_MAP = [
		'k' => King::class,
		'q' => Queen::class,
		'r' => Rook::class,
		'b' => Bishop::class,
		'n' => Knight::class,
		' ' => Pawn::class,
	];
	public static function create(string $piece)
	{
		[$color, $piece] = str_split(str_pad($piece, 2, ' '));
		if (!array_key_exists($piece, self::PIECE_MAP)) {
			throw new InvalidArgumentException('Invalid piece type');
		}
		$class = self::PIECE_MAP[$piece];
		return new $class($color);
	}
}

Which is the final piece we need to be able to revisit our initial test output. We should now be able to swap in our game pieces and factory instead of using raw string values on our board. Which means after some adjustments to our board our demo now looks like:

$board = new Board(3, 2);
$board->placePiece('a', 1, PieceFactory::create('w'));
$board->placePiece('b', 1, PieceFactory::create('w'));
$board->placePiece('a', 3, PieceFactory::create('b'));
$board->placePiece('b', 3, PieceFactory::create('b'));
echo $board;

However we're quickly outgrowing our test case here, and it's not in the same format the question provided.

Parsing the Problem

Looking back at the original question, it included the following:

$board = [
  ['a' => 'b', 'b' => 'b'],
  ['a' => '', 'b' => ''],
  ['a' => 'w', 'b' => 'w']
];

as an example of input.

Given this, we're going to go ahead and make the assumption that we're always dealing with a rectangular board (please don't make me think about other shapes). Therefore we can determine the rows and columns involved easily:

$input = [
	['a' => 'b', 'b' => 'b'],
	['a' => '', 'b' => ''],
	['a' => 'w', 'b' => 'w']
  ];

$board = new Board(sizeof($input), sizeof($input[0]));

And with a pair of nested loops we can parse through the input instead of "manually" placing pieces as we were doing before:

$input = [
	['a' => 'w', 'b' => 'w'],
	['a' => '', 'b' => ''],
	['a' => 'b', 'b' => 'b']
  ];

$board = new Board(sizeof($input), sizeof($input[0]));
for ($row = 0; $row < sizeof($input); $row++) {
	foreach ($input[$row] as $column => $piece) {
		if ($piece) {
			$board->placePiece($column, $row + 1, PieceFactory::create($piece));
		}
	}
}

echo $board;

which gives us the same output as before. Now we're free to change the input around for whatever chess boards we want to play with, such as the traditional setup:

$traditionalInput = [
	['a' => 'br', 'b' => 'bn', 'c' => 'bb', 'd' => 'bq', 'e' => 'bk', 'f' => 'bb', 'g' => 'bn', 'h' => 'br'],
	['a' => 'b', 'b' => 'b', 'c' => 'b', 'd' => 'b', 'e' => 'b', 'f' => 'b', 'g' => 'b', 'h' => 'b'],
	['a' => '', 'b' => '', 'c' => '', 'd' => '', 'e' => '', 'f' => '', 'g' => '', 'h' => ''],
	['a' => '', 'b' => '', 'c' => '', 'd' => '', 'e' => '', 'f' => '', 'g' => '', 'h' => ''],
	['a' => '', 'b' => '', 'c' => '', 'd' => '', 'e' => '', 'f' => '', 'g' => '', 'h' => ''],
	['a' => '', 'b' => '', 'c' => '', 'd' => '', 'e' => '', 'f' => '', 'g' => '', 'h' => ''],
	['a' => 'w', 'b' => 'w', 'c' => 'w', 'd' => 'w', 'e' => 'w', 'f' => 'w', 'g' => 'w', 'h' => 'w'],
	['a' => 'wr', 'b' => 'wn', 'c' => 'wb', 'd' => 'wq', 'e' => 'wk', 'f' => 'wb', 'g' => 'wn', 'h' => 'wr'],
];

Which gives the familiar looking:

8| wr wn wb wq wk wb wn wr

7| w  w  w  w  w  w  w  w

6| -- -- -- -- -- -- -- --

5| -- -- -- -- -- -- -- --

4| -- -- -- -- -- -- -- --

3| -- -- -- -- -- -- -- --

2| b  b  b  b  b  b  b  b

1| br bn bb bq bk bb bn br
_  _  _  _  _  _  _  _  _  
 | a  b  c  d  e  f  g  h

Movement

Finally making it to the"meat" of the problem, there are a couple different approaches here with increasing implementation complexity to consider.

Firstly, the most naive approach would be to loop through each piece on the board and define some rules on the classes that define what a valid movement is - check each of the possibilities for an existing piece and count the result. However:

• That doesn't immediately account for the inability of some pieces to "jump" over others
• There's some additional logic required for pawn movement (possibly, we might also assumption this logic out of the way later to support different game board sizes/setups)
• Multiple pieces have similar movement patterns in a single direction, which we can keep DRY

With this in mind let's ignore the knight for a second. The remaining characters:

• Only move in a straight line (in 1-8 directions)
• Can move either 1 or an "unlimited" number of space within the confines of the board

Therefore we can probably represent the movement as a series of "vector-like" arrays, one for each direction (so we can bail out as soon as a space is occupied and prevent "jumping").

Since we're dealing with some specific limitations in our data representation, let's us a separate class to represent it.

class MovementMatrix implements Countable
{
	public const MOVEMENT_LEFT_KEY = 'x-';
	public const MOVEMENT_RIGHT_KEY = 'x+';
	public const MOVEMENT_UP_KEY = 'y+';
	public const MOVEMENT_DOWN_KEY = 'y-';
	public const MOVEMENT_UP_LEFT_KEY = 'x-y-';
	public const MOVEMENT_UP_RIGHT_KEY = 'x+y+';
	public const MOVEMENT_DOWN_LEFT_KEY = 'x-y+';
	public const MOVEMENT_DOWN_RIGHT_KEY = 'x+y-';

	private $matrices  = [];

	public function __construct()
	{
		$this->initializeMatrices();
	}

	public function __toString(): string
	{
		$output = '';
		foreach ($this->matrices as $key => $matrix) {
			$output .= $key . PHP_EOL;
			foreach ($matrix as $row) {
				$output .= implode(' ', $row) . PHP_EOL;
			}
		}
		return $output;
	}

	public function count(): int
	{
		return array_sum(array_map('count', $this->matrices));
	}

	private function initializeMatrices(): void
	{
		$this->matrices = [
			static::MOVEMENT_RIGHT_KEY => [],
			static::MOVEMENT_LEFT_KEY => [],
			static::MOVEMENT_UP_KEY => [],
			static::MOVEMENT_DOWN_KEY => [],
			static::MOVEMENT_UP_RIGHT_KEY => [],
			static::MOVEMENT_UP_LEFT_KEY => [],
			static::MOVEMENT_DOWN_RIGHT_KEY => [],
			static::MOVEMENT_DOWN_LEFT_KEY => [],
		];
	}

	public function setMatrix(string $key, array $matrix): void
	{
		$this->matrices[$key] = $matrix;
	}

	public function getMatrix(string $key): array
	{
		return $this->matrices[$key];
	}
}

Since the movement patterns belong to the pieces, let's revisit them and implement some movement logic. Take the Bishop for example:

protected function applyMovement(MovementMatrix $matrices, Board $board, int $column, int $row): MovementMatrix
{
	$directions = [
		MovementMatrix::MOVEMENT_DOWN_LEFT_KEY,
		MovementMatrix::MOVEMENT_DOWN_RIGHT_KEY,
		MovementMatrix::MOVEMENT_UP_LEFT_KEY,
		MovementMatrix::MOVEMENT_UP_RIGHT_KEY,
	];
    
	foreach ($directions as $direction) {
		$instructions = str_split($direction);
		$validMovements = [];
		if ($instructions[1] === '+') {
			$xMovement = 1;
		} else {
			$xMovement = -1;
		}
        
		if ($instructions[3] === '+') {
			$yMovement = 1;
		} else {
			$yMovement = -1;
		}
        
		while ($board->checkPositionIsEmpty($column + $xMovement, $row + $yMovement)) {
			$validMovements = [$column + $xMovement, $row + $yMovement];
			$column += $xMovement;
			$row += $yMovement;
		}
		$matrices->setMatrix($direction, $validMovements);
	}
	return $matrices;
}

Each piece only needs to register up to 8 of its own movement patterns inside of the MovementMatrix object, and then we'll be able to wrap things up inside of our game board with some generic counting logic.

Counting Movement

Since our MovementMatrix implements the Countable interface the actual counting logic is quite simple. All we need to do is iterate over the board and call count() on the MovementMatrix of each valid piece, summing up the number as we go.

As an added bonus we can also filter on individual piece types in case we need to debug some scenarios later, and default to counting for all pieces:

public function getPlayableMoves(string $pieceFilter = Piece::class): int
{
	$playableMoves = 0;
	foreach ($this->state as $row => $columns) {
		foreach ($columns as $column => $piece) {
			if (is_a($piece, $pieceFilter)) {
				$playableMoves += count($piece->getMovementMatrix($this, $column, $row));
			}
		}
	}
	return $playableMoves;
}

The Results

And finally, we're ready to see some numbers. Lets start with the classic TraditionalInput class we defined earlier:

$input = TraditionalInput::getInput();

$board = new Board(sizeof($input), sizeof($input[0]));

for ($row = 0; $row < sizeof($input); $row++) {
	foreach ($input[$row] as $column => $piece) {
		if ($piece) {
			$board->placePiece($column, $row + 1, PieceFactory::create($piece));
		}
	}
}

echo 'Valid playable moves: ' . $board->getPlayableMoves() . PHP_EOL;

For an output of:

Valid playable moves: 24

Which checks out (8 pawns can each move, and both of the 2 knights can make 2 possible moves for a total of 12, doubled since there's 2 sides).

But a pawn can move 2 places at the start of the game!

This is very true, however given that we're allowing any game state to be calculated here there is no way to know whether the pawn is actually in its initial position or not. Sure we could calculate if it is 2 spaces from the edge of the board for its respective side and that would be a very valid way of doing this calculation, however with a variable board size there's no guarantee that anything other than the TraditionalInput state follows that rule. Consider the initial example state again:

$board = [
  ['a' => 'b', 'b' => 'b'],
  ['a' => '', 'b' => ''],
  ['a' => 'w', 'b' => 'w']
];

Therefore I'm opting to not support the double space move for a pawn from its initial position, and that's something I'm okay with.

In these types of problems you should always be willing to make concessions on what is possible where it makes sense, and wherever you're ready to back up your decision to anybody who challenges it.

Speaking of the original question:

Valid playable moves: 4

Which if that was our only goal, we should have just counted by hand.