gridmancer.js

// Solution to CodeCombat's Gridmancer level
// http://sett.com/codecombat/beat-this-level-get-a-programming-job

// Fill the empty space with the minimum number of rectangles.
// (Rectangles should not overlap each other or walls.)
// The grid size is 1 meter, but the smallest wall/floor tile is 4 meters.
// If you can do better than one rectangle for every tile, let us know!
// We'll help you find a programming job (if you want one).
// Check the blue guide button at the top for more info.
// Press Contact below to report success if you want a job!
// Just include your multiplayer link in the contact email.
// Make sure to sign up on the home page to save your code.

var grid = this.getNavGrid().grid;
var tileSize = 4;

var completedGrid = []; // Coordinate grid used to log completed coordinates

var INCOMPLETE = 0; // Value used in completed grid to indicate a position yet to be fitted with a rectangle
var COMPLETE = 1; // Value used in completed grid to indicate a position that has been fitted with a rectangle

/**
 * Initializes the completed grid (two-dimensional array) to the size
 * of the level grid and marks each position as incomplete.
 */
(function initCompletedList() {
   for(var y = 0; y + tileSize < grid.length; y += tileSize) {
        completedGrid[y] = [];
        for(var x = 0; x + tileSize < grid[0].length; x += tileSize) {
            completedGrid[y][x] = INCOMPLETE;
        }
   }
})();

/**
 * Adds positions to the completed grid starting from (x,y)
 * at intervals of the set tile size. The number of positions added
 * in any direction is tileCountX and tileCountY, respectively.
 * @param x Origin x position.
 * @param y Origin y position.
 * @param tileCountX Distance to count in x direction.
 * @param tileCountY Distance to count in y direction.
 */
function markCompleted(x, y, tileCountX, tileCountY) {
    var currentX = x;
    var currentY = y;
    for(var j = 0; j < tileCountY; j++) {
        for(var i = 0; i < tileCountX; i++) {
            completedGrid[currentY][currentX] = COMPLETE;
            currentX += tileSize;
            }
            currentY += tileSize;
            currentX = x;
    }
}

/**
 * Checks if the given (x,y) is already complete, i.e., covered by a rectangle.
 * Returns true if complete, otherwise false.
 * @param x The x coordinate to check.
 * @param y The y coordinate to check.
 * @return True if (x,y) is complete, otherwise false.
 */
function isComplete(x, y) {
	if(completedGrid[y][x] === COMPLETE)
		return true;
		
	return false;
}

/**
 * Checks if the given (x,y) is an unblocked space
 * and is not complete.
 * Returns true if available, otherwise false.
 * @param x The x coordinate to check.
 * @param y The y coordinate to check.
 * @return True if (x,y) is available, otherwise false.
 */
function isAvailable(x, y) {
    var occupied = grid[y][x].length > 0;
    return !occupied && !isComplete(x, y);
}

/**
 * Gets the number of tiles that fit between the origin (x,y)
 * and the first collision.
 * @param x Origin x position.
 * @param y Origin y position.
 * @return Number of tiles that fit between the origin (x,y)
 */
function countTilesWide(x, y, tileSize) {
    var tileCount = 0;
    
    while(isAvailable(x, y)) {
        ++tileCount;
        x += tileSize;
    }
 
    return tileCount;
}

/**
 * Calculates the center point of a dimension given
 * a dimension measurement and a position offset.
 * @param dimensionMeasure Measurement of the x or y dimension.
 * @param offset x or y positional offset.
 * @return Center point of a dimension from offset.
 */
function rectCenter(dimensionMeasure, offset) {
    return offset + (dimensionMeasure / 2);
}

/**
 * Calculates the dimension measurement given a number of tiles
 * and a tile size.
 * @param tileCount Number of tiles.
 * @param tileSize Size of a tile.
 * @return Measurement equal to tileCount * tileSize.
 */
function rectDimension(tileCount, tileSize) {
    return tileCount * tileSize;
}

/**
 * Starting at position (x,y), calculates the largest
 * rectangle that fits within the surrounding walls using the
 * given tile size for measurement.
 * @param x Origin x position.
 * @param y Origin y position.
 * @param tileSize Size of a single tile.
 * @return Rectangle object:
 * 	tileCountX: Number of tiles of size tileSize in the x direction from origin
 *	tileCountY: Number of tiles of size tileSize in the y direction from origin
 *	width: Width of the rectangle equal to tileCountX * tileSize
 *	height: Height of the rectangle equal to tileCountY * tileSize 
 *	centerX: Center x position of the rectangle.
 *	centerY: Center y position of the rectangle.
 */
function fitRectangle(x, y, tileSize) {
	var tileCountWide = countTilesWide(x, y, tileSize); // First row used as reference width
	var tileCountHigh = 1; // We start with one row
    
	var currentY = y + tileSize; // Initialize current y pos to next row up
	var currentTileCountWidth = countTilesWide(x, currentY, tileSize); // Get width for next row up
	
	// Successful rows are available and the same width as reference row
	while(isAvailable(x, currentY) && tileCountWide === currentTileCountWidth) {
        	++tileCountHigh;
        	currentY += tileSize; // Next row up
        	currentTileCountWidth = countTilesWide(x, currentY, tileSize);
	}
	
	var rectWidth = rectDimension(tileCountWide, tileSize);
	var rectHeight = rectDimension(tileCountHigh, tileSize);
	
	return {
		tileCountX: tileCountWide,
		tileCountY: tileCountHigh,
		width: rectWidth,
		height: rectHeight,
		centerX: rectCenter(rectWidth, x),
		centerY: rectCenter(rectHeight, y)
	};
}

/**
 * Places the rectangles on the game field.
 * @param spellBook CodeCombat system object that provides spells, i.e., responds to addRect() method.
 */
function placeRectangles(spellBook) {
    for(var y = 0; y + tileSize < grid.length; y += tileSize) {
        for(var x = 0; x + tileSize < grid[0].length; x += tileSize) {
    		if(isAvailable(x, y)) {
    		    var rect = fitRectangle(x, y, tileSize);
        		spellBook.addRect(rect.centerX, rect.centerY, rect.width, rect.height);
                markCompleted(x, y, rect.tileCountX, rect.tileCountY);
                x += rect.width; // Skip to end of placed rectangle
           }
        }
    }
}

placeRectangles(this);