// Fill the empty space with the minimum number of rectangles.
// 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 guide for more info, and press Contact below to report success.

var realGrid = this.getNavGrid().grid;
var tileSize = 4;
var grid = [];
var x, y,
    tileWidth = Math.floor(realGrid[0].length/tileSize),
    tileHeight = Math.floor(realGrid.length/tileSize);
for (y = -1; y <= tileHeight; y++) {
    grid[y] = [];
    for (x = -1; x <= tileWidth; x++) {
        if (y < 0 || x < 0 || y == tileHeight || x == tileWidth || realGrid[(y+0.5)*tileSize][(x+0.5)*tileSize].length > 0) {
            grid[y][x] = {type: -1, ind: -1};
        } else {
            grid[y][x] = {type: 0, ind: -1};
        }
    }
}

function isEmpty(cell) {
    return cell.type === 0;
}

var addRect = this.addRect;
var spawnedRectangles = this.spawnedRectangles;
function myAddRect(x, y, w, h) {
    var i, j;
    var ind = spawnedRectangles.length;
    addRect((x+w/2)*tileSize, (y+h/2)*tileSize, w*tileSize, h*tileSize);
    if (h == 1 && w == 1) {
        grid[y][x].type = 5;
        grid[y][x].rect = spawnedRectangles[ind];
    } else if (h == 1 && w > 1) {
        grid[y][x].type = 4;
        grid[y][x+w-1].type = 6;
        for (i = x+1; i < x+w-1; i++) grid[y][i].type = 5;
        for (i = x; i < x+w; i++) grid[y][i].rect = spawnedRectangles[ind];
    } else if (h > 1 && w == 1) {
        grid[y][x].type = 2;
        grid[y+h-1][x].type = 8;
        for (i = y+1; i < y+h-1; i++) grid[i][x].type = 5;
        for (i = x; i < y+h; i++) grid[i][x].rect = spawnedRectangles[ind];
    } else if (h > 1 && w > 1) {
        grid[y][x].type = 1;
        grid[y][x+w-1].type = 3;
        grid[y+h-1][x].type = 7;
        grid[y+h-1][x+w-1].type = 9;
        for (i = x+1; i < x+w-1; i++) {
            grid[y][i].type = 2;
            grid[y+h-1][i].type = 8;
        }
        for (i = y+1; i < y+h-1; i++) {
            grid[i][x].type = 4;
            grid[i][x+w-1].type = 6;
        }
        for (i = y+1; i < y+h-1; i++) {
            for (j = x+1; j < x+w-1; j++) {
                grid[i][j].type = 5;
            }
        }
        for (i = y; i < y+h; i++) {
            for (j = x; j < x+w; j++) {
                grid[i][j].rect = spawnedRectangles[ind];
            }
        }
    }
}

function toRect(rect) {
    var r = {'width':rect.width/tileSize,
             'height':rect.height/tileSize};
    r.pos = {'x':rect.pos.x/tileSize-r.width/2,
             'y':rect.pos.y/tileSize-r.height/2};
    return r;
}

var removeRectAt = this.removeRectAt;
var say = this.say;
function myRemoveRect(rect) {
    var i, j;
    // say(rect.pos.x+','+rect.pos.y);
    for (i = rect.pos.y; i < rect.pos.y+rect.height; i++) {
        for (j = rect.pos.x; j < rect.pos.x+rect.width; j++) {
            grid[i][j].type = 0;
            grid[i][j].rect = undefined;
        }
    }
    removeRectAt((rect.pos.x+rect.width/2)*tileSize, (rect.pos.y+rect.height/2)*tileSize);
}

var w, h;
for (y = 0; y < tileHeight; y++) {
    for (x = 0; x < tileWidth; x++) {
        if (grid[y][x].type === 0) {
            h = 1;
            w = 1;
            while (isEmpty(grid[y][x+w])) w++;
            while (grid[y+h].slice(x,x+w).every(isEmpty)) h++;
            myAddRect(x, y, w, h);
            x += w-1;
            this.wait();
        }
    }
}

var i, j, k, rect, rect2;
var broken1 = false, broken2 = false, brokenX = true;
// this.say(spawnedRectangles.length);
while (brokenX) {
    brokenX = false;
    spawnedRectangles = this.spawnedRectangles;
    for (i = 1; i < spawnedRectangles.length; i++) {
        if (!brokenX) {
            rect = toRect(spawnedRectangles[i]);
            broken1 = false;
            for (j = 0; j < i; j++) {
                if (!broken1) {
                    rect2 = toRect(spawnedRectangles[j]);
                    if (rect.pos.y == rect2.pos.y &&
                        rect.height == rect2.height) {
                        broken1 = true;
                    }
                }
            }
            if (rect.pos.y == rect2.pos.y &&
                rect.height == rect2.height) {
                // this.say((i+1)+':testing');
                // this.say((i+1)+':'+rect.pos.x+','+rect.pos.y+','+rect.height);
                // this.say((i)+':'+rect2.pos.x+','+rect2.pos.y+','+rect2.height);
                var pass = true;
                var rectsToTarget = [];
                broken1 = false;
                for (j = rect2.pos.x+rect2.width; j < rect.pos.x; j++) {
                    if (!broken1) {
                        if (rect.height == 1) {
                            // this.say('cell:'+grid[rect.pos.y][j].type);
                            if ([1,2,3,7,8,9].indexOf(grid[rect.pos.y][j].type) > -1) {
                                // this.say(j+','+rect.pos.y);
                                rectsToTarget.push(toRect(grid[rect.pos.y][j].rect));
                            } else {
                                pass = false;
                                broken1 = true;
                            }
                        } else {
                            if (grid[rect.pos.y][j].type === 1) {
                                var p = true;
                                broken2 = false;
                                for (k = rect.pos.y+1; k < rect.pos.y+rect.height; k++) {
                                    if (!broken2) {
                                        if (grid[k][j] !== 4) {
                                            p = false;
                                            broken2 = true;
                                        }
                                    }
                                }
                                if (p) {
                                    rectsToTarget.push(toRect(grid[rect.pos.y][j].rect));
                                    while (grid[rect.pos.y][j] !== 3) j++;
                                } else {
                                    pass = false;
                                    broken1 = true;
                                }
                            } else if (grid[rect.pos.y][j].type === 4) {
                                if (grid[rect.pos.y+rect.height-1][j] !== 7) {
                                    pass = false;
                                    broken1 = true;
                                } else {
                                    var p = true;
                                    broken2 = false;
                                    for (k = rect.pos.y; k < rect.pos.y+rect.height-1; k++) {
                                        if (!broken2) {
                                            if (grid[k][j] !== 4) {
                                                p = false;
                                                broken2 = true;
                                            }
                                        }
                                    }
                                    if (p) {
                                        rectsToTarget.push(toRect(grid[rect.pos.y][j].rect));
                                        while (grid[rect.pos.y][j] !== 6) j++;
                                    } else {
                                        pass = false;
                                        broken1 = true;
                                    }
                                }
                            } else {
                                pass = false;
                                broken1 = true;
                            }
                        }
                    }
                }
                // this.say((i+1)+':'+pass);
                if (pass) {
                    brokenX = true;
                    var rectsToMake = [];
                    for (j = 0; j < rectsToTarget.length; j++) {
                        if (rectsToTarget[j].pos.y === rect.pos.y) {
                            rectsToMake.push([rectsToTarget[j].pos.x,
                                             rectsToTarget[j].pos.y + rect.height,
                                             rectsToTarget[j].width,
                                             rectsToTarget[j].height - rect.height]);
                            myRemoveRect(rectsToTarget[j]);
                        } else if (rectsToTarget[j].pos.y < rect.pos.y) {
                            rectsToMake.push([rectsToTarget[j].pos.x,
                                              rectsToTarget[j].pos.y,
                                              rectsToTarget[j].width,
                                              rectsToTarget[j].height - rect.height]);
                            myRemoveRect(rectsToTarget[j]);
                        } else {
                            // this.say('erk'); // REMEMBER CONVERT FROM THEIRS TO MINE!
                        }
                    }
                    rectsToMake.push([rect2.pos.x,
                                      rect.pos.y,
                                      rect.pos.x + rect.width - rect2.pos.x,
                                      rect.height]);
                    myRemoveRect(rect);
                    myRemoveRect(rect2);
                    for (j = 0; j < rectsToMake.length; j++) {
                        myAddRect(rectsToMake[j][0],
                                  rectsToMake[j][1],
                                  rectsToMake[j][2],
                                  rectsToMake[j][3]);
                    }
                }
            }
        }
    }
}