Instantly share code, notes, and snippets.

foxly/gist:8168624 Last active Aug 2, 2016

What would you like to do?
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 += '
'; jQuery('.workspace').append(html); } var count = 'POLYS: ' + poly_count + ' | ITERATIONS: ' + _iter_count; jQuery('.count').append(count); }); // USE THE FOLLOWING HTML CODE // =============================================================================== // // // // // // // // // // //
//
// // //

fasterixxx commented Jul 23, 2014

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