Create a gist now

Instantly share code, notes, and snippets.

My solution to codecombat.com 's GridMancer challenge. See http://codecombat.com/play/level/gridmancer
/**
* RECTIFY ...BY FOXLY
* ---------------------------------------------------------------------------
* Given an array of cells, where 1 represents a filled cell and 0
* represents an empty cell, finds the minimum set of rectangles needed
* to cover the filled cells. Result is returned as an array of rectangle
* objects where (x1,y1) is the upper-left coordinate of the rectangle
* and (x2,y2) is the lower-right coordinate of the rectangle.
*
* @see [based on] http://www.cs.uic.edu/~dasgupta/resume/publ/papers/bookchap3.pdf
* @see [possibly faster] http://bit.ly/1lrrqqu (stackoverflow.com)
*
* @author https://github.com/foxly
* @license MIT + GPL2
*
* MIN ACEPTABLE: 40
* OPTIMAL: 29
* THIS CODE DELIVERS: 29
*
* ============================================================================
*/
var _greedy = true; // If set false, optimizes the algorithm for speed. If set true
// optimizes the algorithm for minimum number of rectangles
// ============================================================================
var _polys = []; // Array of polygon objects
var _empty_rows = []; // Strike-table of known empty rows
var _canvas = [ // Pre-compiled array of the game map for testing
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0],
[0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0],
[0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0],
[0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0],
[0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0],
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0],
[1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0],
[1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0],
[0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0],
[0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0],
[1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0],
[1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
[1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
];
// ============================================================================
/**
* Traverses the game grid and loads it into a 2 dimensional array. Used when working in
* the codecombat.com environment, when the codecombat.com environment is working ... ;)
*
* @return {array} _canvas | Bitmapped array of game surface, where 1 represents a
* filled cell and 0 represents an empty cell
*/
function scrapeGrid(){
var grid = this.getNavGrid().grid;
// Cache array dimensions to improve loop speed. This technique is used throughout the code to improve speed.
// @see http://stackoverflow.com/questions/6973942/is-optimizing-javascript-for-loops-really-necessary
var grid_y_max = grid.length;
var grid_x_max = grid[0].length;
var tile_size = 4;
for(var y = 0; y + tile_size < grid_y_max; y += tile_size) {
for(var x = 0; x + tile_size < grid_x_max; x += tile_size) {
_canvas[y][x] = grid[y][x].length > 0 ? 1 : 0;
}
}
}
/**
* Overwrites a given segment of a row in the _canvas array with 0's. All params
* are zero-based.
*
* @param {int} row | y-offset of row
* @param {int} from | starting x-offset
* @param {int} to | ending x-offset
*/
function zeroSpan(row, from, to){
for(var i = from; i <= to; i++){
_canvas[row][i] = 0;
}
}
/**
* Scans the _canvas array for polygons and adds them to the _poly array if found
*/
function findPoly(){
var upper_set = false;
var first_row = true;
var x1 = false;
var y1 = false;
var x2 = false;
var y2 = false;
for(var y_offset = 0; y_offset < height; y_offset++){
// If a row is in the strike-table, we can skip it because its empty
if(_empty_rows[y_offset] === true){
continue;
}
// Extend the horizontal beam across the canvas until we either hit
// a discontinuity, or the end of the canvas
if(first_row){
var row_is_empty = true;
for(var x_offset = 0; x_offset < width; x_offset++){
if(_canvas[y_offset][x_offset]){ // Within the loop, also test for empty rows
row_is_empty = false;
}
if(!upper_set && _canvas[y_offset][x_offset]){
y1 = y_offset;
y2 = y1;
x1 = x_offset;
x2 = x1;
upper_set = true;
first_row = false;
}
else if(upper_set){
if(!_canvas[y_offset][x_offset]){
x2 = x_offset - 1;
break; // Inner X loop
}
else if(x_offset === (width - 1)){
x2 = x_offset;
}
}
}
// When empty rows are found, add them to the strike-table so we can
// skip them. This substantially improves performance.
if(row_is_empty){
_empty_rows[y_offset] = true;
_remaining_rows--;
}
// If we found a compatible span, remove its cells from the canvas array
if(x1 !== false){
zeroSpan(y_offset, x1, x2);
}
}
else {
// Bounds-check the segment before iterating through it to save cycles
var x1_bounded = ( ((x1 === 0) && (_canvas[y_offset][x1] === 1) ) || (_canvas[y_offset][x1 - 1] === 0));
var x2_bounded = ( ((x2 === (width - 1)) && (_canvas[y_offset][x2] === 1)) || (_canvas[y_offset][x2 + 1] === 0));
// If we're running in _greedy mode instead of 'fast' mode, force the
// scanning loop to extend its vertical beam downwards until it
// hits a limit
if(_greedy && _canvas[y_offset][x1] && _canvas[y_offset][x2]){
// Perform a ghetto XOR operation
var tick = 0;
if(_canvas[y_offset][x1 - 1] !== 0){
tick++;
}
if(_canvas[y_offset][x2 + 1] !== 0){
tick++;
}
// If the horizontal beam doesn't completely span the current rectangle,
// we can go ahead and extend the vertical beam
if(tick === 1){
x1_bounded = true;
x2_bounded = true;
}
}
// If the segment is bounded, or we're operating in greedy mode per above, scan the
// horizontal beam until we hit a discontinuity or reach the end
if(x1_bounded && x2_bounded ){
var is_continuous = true;
for(var segment_offset = x1; segment_offset <= x2; segment_offset++){
if(!_canvas[y_offset][segment_offset]){
is_continuous = false;
break; // Inner X loop
}
}
if(is_continuous){
y2 = y_offset;
zeroSpan(y_offset, x1, x2);
}
else {
_polys.push({x1:x1, y1:y1, x2:x2, y2:y2});
break; // Outer Y-Loop
}
}
else {
_polys.push({x1:x1, y1:y1, x2:x2, y2:y2});
break; // Outer Y-Loop
}
}
if( (x1 !== false) && (y_offset === (width - 1)) ){
zeroSpan(y_offset, x1, x2);
_polys.push({x1:x1, y1:y1, x2:x2, y2:y2});
}
}
}
var width = _canvas[0].length;
var height = _canvas.length;
var _remaining_rows = height;
var _iter_count = 0;
var failsafe = 0;
while( (_remaining_rows > 0) && (failsafe < 500) ){
_iter_count++;
failsafe++;
findPoly();
}
// TODO (ONCE CODECOMBAT FIXES THEIR DEV ENVIRONMENT)
//
// 1) Read-in canvas using scrapeGrid()
// 2) Transcribe the data to our coordinate system
// 3) Create a loop to write-out _polys[] to their grid system
// =================================================================================================
console.log(_canvas);
console.log(_polys);
jQuery(document).ready(function(){
var poly_count = _polys.length;
for(var poly_offset = 0; poly_offset < poly_count; poly_offset++){
var color = '#'+(0x1000000+(Math.random())*0xffffff).toString(16).substr(1,6);
var height = _polys[poly_offset].y2 - _polys[poly_offset].y1 + 1;
var width = _polys[poly_offset].x2 - _polys[poly_offset].x1 + 1;
var scale = 20;
var html ='';
html += '<div class="poly" style="background-color:' + color + '; position:absolute; border:solid 1px #111;';
html += 'height:' + ((height * scale) -2)+ 'px; ';
html += 'width:' + ((width * scale) - 2) + 'px; ';
html += 'top:' + (_polys[poly_offset].y1 * scale) + 'px; ';
html += 'left:' + (_polys[poly_offset].x1 * scale) + 'px; ';
html += '"></div></div>';
jQuery('.workspace').append(html);
}
var count = 'POLYS: ' + poly_count + ' | ITERATIONS: ' + _iter_count;
jQuery('.count').append(count);
});
// USE THE FOLLOWING HTML CODE
// ===============================================================================
//<html style="background-color:#444;" xmlns="http://www.w3.org/1999/xhtml">
//
//<head profile="http://gmpg.org/xfn/11">
//
// <script type="text/javascript" src="http://localhost/jquery.js"></script>
// <script type="text/javascript" src="http://localhost/rectify.js"></script>
//
//</head>
//
//<body style="">
// <div class="workspace" style="height:400px; width:400px; background-color:yellow; position:absolute; top:0px; left:0px"></div>
// <div class="count" style="background:white; position:absolute; top:420px; left:0px"></div>
//</body>
//
//</html>
@fasterixxx

I think in line 252 should be variable 'height' instead of 'width'? ?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment