As part of an job interview process, I was tasked to write a solver for a simplified Tetris game using JavaScript. The game board size is 4x4 and there are 4 different pieces given in a .txt file. It is not allowed to rotate the pieces, so they should be placed exactly as they are specified in the file. Following normal Tetris rules, a row is cleared when there are no empty squares on a row. The goal is to have as few pieces on the board as possible after having placed all of them.
On a high level, what my code does is as follows:
- Parse the input file and create
TetrisPieceobjects - Create a new
Gameobject that holds the tetris pieces and has a board size of 4x4 - Shuffle the tetris pieces and compute their possible locations one at a time. Randomly choose one of the locations, place the piece on the board, and move on to the next piece. This is done by the
RandomSolverclass - Calculate the score of the solution and compare it to the best score so far. Reset game. Go back to step 3 until score is 0 (the optimal solution) or iterations = 10000
index.js
const fs = require('fs');
const parseFile = require('./reader');
const Game = require('./game');
const Coordinate = require('./coordinate');
const RandomSolver = require('./RandomSolver');
const inputFile = '../data/tetris_file.txt';
console.log('Parsing input file...');
const tetrisPieces = parseFile(inputFile);
console.log('Done.');
const boardSize = 4;
console.log(`Creating new game with size ${boardSize}`);
const game = new Game(boardSize, tetrisPieces);
const randomSolver = new RandomSolver(game);
randomSolver.run();
reader.js
const fs = require('fs');
const TetrisPiece = require('./tetrisPiece');
const Coordinate = require('./coordinate');
/**
* Parses a file containing tetris piece information. The function reads the
* entire file into memory. For larger files, the file should be consumed line
* by line.
* @param {String} file The file path
* @return {TetrisPiece[]} The tetris pieces in the file
*/
function parseFile(file) {
let data;
try {
data = fs.readFileSync(file, 'utf-8').split('\r\r\n');
}
catch (err) {
throw err;
}
let tetrisPieces = [];
data.forEach(line => {
const tetrisPiece = parseLine(line);
tetrisPieces.push(tetrisPiece);
});
return tetrisPieces;
}
/**
* Parses a line of the input file containing tetric piece information.
* @param {String} line A line in the input file
* @return {TetrisPiece} A tetris piece constructed from input line
*/
function parseLine(line) {
const idCoordinates = line.split(':');
if (idCoordinates.length !== 2) {
throw 'Line contains invalid data';
}
const id = idCoordinates[0];
const rawCoordinates = idCoordinates[1].split(';');
let coordinates = [];
rawCoordinates.forEach(coordinate => {
const xy = coordinate.split(',');
coordinates.push(new Coordinate(xy[0], xy[1]));
});
return new TetrisPiece(id, coordinates);
}
module.exports = parseFile;
game.js
const Coordinate = require('./coordinate');
/**
* Tetris game representation
*/
class Game {
constructor(boardSize, tetrisPieces) {
this.initTetrisBoard(boardSize);
this.tetrisPieces = tetrisPieces;
}
/**
* Initializes game board with given size (square)
* @param {Number} size The length of a side of the square
*/
initTetrisBoard(size) {
this.gameBoard = new Array(size).fill(null).map(item => (new Array(size).fill(null)));
}
/**
* Resets the game state to empty board
*/
reset() {
this.initTetrisBoard(this.getBoardSize());
}
/**
* Places given tetris piece on game board at given position
* @param {TetrisPiece} tetrisPiece The tetris piece to place
* @param {Coordinate} position The game board Coordinate to place the piece at.
* The tetris piece's coordinates are translated with this Coordinate
* @param {Boolean} [visualize=false] Visualize the game board after inserting piece
* @return {Boolean} Whether or not the tetris piece could be placed at given position
*/
placeTetrisPiece(tetrisPiece, position, visualize = false) {
if (!this.isPositionValidForTetrisPiece(tetrisPiece, position)) {
return false;
}
tetrisPiece.coordinates.forEach(localCoord => {
const boardCoord = localCoord.translate(position.x, position.y);
this.gameBoard[boardCoord.y][boardCoord.x] = tetrisPiece.id;
});
if (visualize) {
this.printGameBoard();
}
this.update(visualize);
return true;
}
/**
* Clears all complete rows
* @param {Boolean} [visualize=false] Visualize game board after clearing rows
*/
update(visualize = false) {
let didClearAnyRows = false;
for (let rowIndex = 0; rowIndex < this.gameBoard.length; rowIndex++) {
const row = this.gameBoard[rowIndex];
if (this.isRowComplete(row)) {
this.clearRow(rowIndex);
--rowIndex;
didClearAnyRows = true;
}
}
if (visualize && didClearAnyRows) {
this.printGameBoard();
}
}
/**
* Checks if given tetris piece can be placed at given position
* @param {TetrisPiece} tetrisPiece The tetris piece
* @param {Coordinate} position The tetris piece position
* @return {Boolean}
*/
isPositionValidForTetrisPiece(tetrisPiece, position) {
const boardCoords = tetrisPiece.coordinates.map(
localCoord => localCoord.translate(position.x, position.y));
if (boardCoords.some(boardCoord => this.isOutOfBounds(boardCoord) ||
this.gameBoard[boardCoord.y][boardCoord.x] !== null)) {
return false;
}
return true;
}
/**
* Checks if the tetris piece intersects with any other pieces on the board.
* Ignores coordinates outside the the board bounds
* @param {TetrisPiece} tetrisPiece The tetris piece
* @param {Coordinate} position The tetris piece position
* @return {Boolean} True if piece intersects, false otherwise
*/
checkForCollision(tetrisPiece, position) {
let collision = false;
tetrisPiece.coordinates.forEach(localCoord => {
const boardCoord = localCoord.translate(position.x, position.y);
if (!this.isOutOfBounds(boardCoord)) {
if (this.gameBoard[boardCoord.y][boardCoord.x] !== null) {
collision = true;
}
}
});
return collision;
}
/**
* Checks if given coordinate is outside board bounds
* @param {Coordinate} coord The coordinate
* @return {Boolean} True if outside bounds, false otherwise
*/
isOutOfBounds(coord) {
return coord.x < 0 || coord.y < 0 || coord.x >= this.getBoardSize() || coord.y >= this.getBoardSize();
}
/**
* Checks if tetris piece has any coordinates in spawning area (north of game board).
* @param {TetrisPiece} tetrisPiece The tetris piece
* @param {Coordinate} position The tetris piece position
* @return {Boolean} True if piece has at least one coordinate in spawning area
* but all other coordinates are within bounds, false otherwise
*/
isPartlyInSpawningAreaButInsideBounds(tetrisPiece, position) {
const boardCoords = tetrisPiece.coordinates.map(localCoord => localCoord.translate(position.x, position.y));
if (boardCoords.some(boardCoord => boardCoord.x < 0 || boardCoord.x >= this.getBoardSize() || boardCoord.y < 0)) {
return false;
}
if (boardCoords.some(boardCoord => boardCoord.y >= this.getBoardSize())) {
return true;
}
return false;
}
/**
* Calculates the spawn position for given tetris piece. The spawn position is
* calculated so that it is left-aligned and has at least one coordinate within
* game board bounds.
* @param {TetrisPiece} tetrisPiece The tetris piece
* @return {Coordinate} The spawn position
*/
getSpawnPositionForTetrisPiece(tetrisPiece) {
return new Coordinate(0,
this.getBoardSize() - 1 - Math.min(...tetrisPiece.coordinates.map(coord => coord.y)));
}
/**
* Returns the length of a side on the square game board
* @return {Number} The length of a side on the game board
*/
getBoardSize() {
return this.gameBoard.length;
}
/**
* Checks if the given row is filled by a tetris piece
* @param {Array} row The row to check
* @return {Boolean} True if complete, false otherwise
*/
isRowComplete(row) {
return row.every(val => val !== null);
}
/**
* Clears the given row, shifting all rows on top of it one step down. Inserts
* an empty row on top.
* @param {Number} rowIndex The row index
*/
clearRow(rowIndex) {
const emptyRow = this.createEmptyRow();
this.gameBoard.splice(rowIndex, 1);
this.gameBoard.push(emptyRow);
}
/**
* Creates an empty board row
* @return {Array} Array filled with null, same size as game board
*/
createEmptyRow() {
return new Array(this.getBoardSize()).fill(null);
}
/**
* Returns the number of tetris piece fragments on the board
* @return {Number} The number of fragments
*/
getTotalCost() {
let cost = 0;
this.gameBoard.forEach(row => row.forEach(val => {
if (val !== null) {
cost++;
}
}));
return cost;
}
/**
* Visualizes the current game board state
*/
printGameBoard() {
console.log(' ----');
for (let y = this.gameBoard.length - 1; y >= 0; y--) {
let line = "|";
for (let x = 0; x < this.gameBoard[y].length; x++) {
const val = this.gameBoard[y][x];
line += val === null ? " " : val;
}
line += "|";
console.log(line);
}
console.log(' ----');
}
}
module.exports = Game;
randomSolver.js
/**
* An NPC that tries to find the optimal solution using random decisions
*/
class RandomSolver {
/**
* Initializes solver with a game that is already initialized
* @param {Game} game The intialized game
*/
constructor(game) {
this.game = game;
}
/**
* Attempts to find the best solution and shows the best solution it found
*/
run() {
let bestSolution;
console.log('Finding optimal solution using random decision...');
for (let i = 0; i < 10000; i++) {
const solution = this.randomSolution();
if (solution) {
if (!bestSolution || bestSolution.cost > solution.cost) {
bestSolution = solution;
if (solution.cost === 0) {
break;
}
}
}
this.game.reset();
}
console.log('Optimal solution (in given order):');
console.log(bestSolution);
this.printSolution(bestSolution);
}
/**
* Returns a solution by at each step calculating the possible tetris piece
* positions and choosing one of them randomly
* @return {Object} Undefined if game over, otherwise dict containing each
* tetris piece's ID as key and its position as value. Also contains the total cost
* of the solution with key 'cost'
*/
randomSolution() {
const shuffledPieces = shuffleArray(this.game.tetrisPieces);
let solution = {};
for (let i = 0; i < this.game.tetrisPieces.length; i++) {
const piece = shuffledPieces[i];
const possibleLocationsForPiece = this.getPossiblePositionsForPiece(piece);
// Game over
if (!possibleLocationsForPiece || possibleLocationsForPiece.length === 0) {
return;
}
const randomLocation = possibleLocationsForPiece[Math.floor(Math.random() * possibleLocationsForPiece.length)];
this.game.placeTetrisPiece(piece, randomLocation);
solution[piece.id] = randomLocation;
}
solution['cost'] = this.game.getTotalCost();
return solution;
}
/**
* Visualizes a complete solution
* @param {Object} solution See {@link RandomSolver#randomSolution} for description
*/
async printSolution(solution) {
this.game.reset();
for (const [key, value] of Object.entries(solution)) {
if (key !== 'cost') {
const piece = this.game.tetrisPieces.find(tetrisPiece => tetrisPiece.id === key);
this.game.placeTetrisPiece(piece, value, true);
}
await sleep(1000);
}
this.game.reset();
}
/**
* Returns the valid positions for given tetris piece with current game state
* @param {TetrisPiece} tetrisPiece The tetris piece
* @return {Coordinate[]} The valid positions, empty if none
*/
getPossiblePositionsForPiece(tetrisPiece) {
const spawnPosition = this.game.getSpawnPositionForTetrisPiece(tetrisPiece);
let possibleLocations = [];
possibleLocations = this.explorePossiblePositions(tetrisPiece, spawnPosition, spawnPosition);
return possibleLocations
}
/**
* Recursively calculates all possible positions for given tetris piece at given location
* with current game state
* @param {TetrisPiece} tetrisPiece The tetris piece
* @param {[type]} currentPosition The piece's current (theoretical) position
* @param {[type]} lastPosition The piece's previous position, used to avoid backtracking
* @return {Coordinate[]} The possible positions
*/
explorePossiblePositions(tetrisPiece, currentPosition, lastPosition) {
const southCoordinate = currentPosition.translate(0, -1);
const westCoordinate = currentPosition.translate(-1, 0);
const eastCoordinate = currentPosition.translate(1, 0);
let possibleLocations = [];
if (this.canMoveTo(tetrisPiece, southCoordinate)) {
const exploredPositions = this.explorePossiblePositions(tetrisPiece, southCoordinate, currentPosition);
possibleLocations = addUniqueCoordinates(possibleLocations, exploredPositions);
}
else {
if (this.game.isPositionValidForTetrisPiece(tetrisPiece, currentPosition)) {
possibleLocations = addUniqueCoordinates(possibleLocations, [currentPosition]);
}
}
[westCoordinate, eastCoordinate].forEach(coordinate => {
if (!lastPosition.equals(coordinate)) {
if (this.canMoveTo(tetrisPiece, coordinate)) {
const exploredPositions = this.explorePossiblePositions(tetrisPiece, coordinate, currentPosition);
possibleLocations = addUniqueCoordinates(possibleLocations, exploredPositions);
}
}
});
return possibleLocations;
}
/**
* Calculates if tetris piece can move to given position
* @param {TetrisPiece} tetrisPiece The tetris piece
* @param {Coordinate} position The position
* @return {Boolean} True if possible, false otherwise
*/
canMoveTo(tetrisPiece, position) {
if (this.game.isPositionValidForTetrisPiece(tetrisPiece, position)) {
return true;
}
if (this.game.isPartlyInSpawningAreaButInsideBounds(tetrisPiece, position)) {
if (!this.game.checkForCollision(tetrisPiece, position)) {
return true;
}
}
return false;
}
}
/**
* Adds given coordinates to given array if they do not exist in the array already
* @param {Coordinate[]} arr The array of existing coordinates
* @param {Coordinate[]} coords The coordinates to add if not already present
* @return {Coordinate[]} The new array
*/
function addUniqueCoordinates(arr, coords) {
coords.forEach(coord => {
if (!checkIfCoordinateExistsInArray(arr, coord)) {
arr = [...arr, coord];
}
})
return arr;
}
/**
* Checks if given coordinate exists in array
* @param {Coordinate[]} arr The array of coordinates
* @param {Coordinate} coordToCheck The coordinate to check for
* @return {Boolean} True if exists, false otherwise
*/
function checkIfCoordinateExistsInArray(arr, coordToCheck) {
let exists = false;
arr.forEach(coord => {
if (coord.equals(coordToCheck)) {
exists = true;
}
})
return exists;
}
/** Utility method to shuffle an array */
const shuffleArray = arr => arr
.map(a => [Math.random(), a])
.sort((a, b) => a[0] - b[0])
.map(a => a[1]);
/**
* Utility method to halt execution
* @param {Number} ms Milliseconds to sleepå
*/
function sleep(ms) {
return new Promise(resolve => setTimeout(resolve, ms));
}
module.exports = RandomSolver;
coordinate.js
/**
* A 2D coordinate representation
*/
class Coordinate {
constructor(x, y) {
this.x = parseInt(x);
this.y = parseInt(y);
}
/**
* Translate this coordinate with given x and y offsets
* @param {Number} x Offset along x-axis
* @param {Number} y Offset along y-axis
* @return {Coordinate} The translated Coordinate
*/
translate(x, y) {
return new Coordinate(this.x + parseInt(x), this.y + parseInt(y));
}
/**
* Compare this Coordinate to another Coordinate by value
* @param {Coordinate} coord The Coordinate to compare with
* @return {Boolean}
*/
equals(coord) {
return this.x === coord.x && this.y === coord.y;
}
}
module.exports = Coordinate;
tetris_file.txt
A:0,0;1,0;1,1;2,1
B:0,0;0,1;0,2;1,2
C:0,0;1,0;2,0;1,1
D:0,0;1,0;1,1;1,-1
Unfortunately I did not pass the assignment, so I asked for feedback on my implementation. According to them, the biggest problem with my code was that the solution was too complex for the task and that the code was hard to read. They also said that my prints were not working and that I overused the letstatement.
I am not arguing against the feedback that I got, but what bothers me is even with this feedback, I do not know how I should improve my code. Therefore I am asking for a code review, specifically with readability and architecture in mind.
I am aware that my solution is quite unorthodox for JavaScript; it can probably be seen that I come from a Java background. As such, I would also appreciate any comments on how to make the solution more "JS-like". I should also mention that the algorithm was not important in the task, so it doesn't need to be reviewed.
