3
\$\begingroup\$

I am trying to optimize a function called place_block. It is meant to give the best row, col coordinate in the matrix to place a given block of row and column size.

My current implementation is unreadable and bad practice. I'm looking for a better way to put it.

// Generates the best possible solution to place a given block of size

vector<int> place_block(char grid[8][8], int block_size_r, int block_size_col) {
    vector<int> rowcol;
//  Based on a block size of block_size_r x block_size_col generate a convient position to place it in the grid without
// Overflow
int row = 0;
int col = 0;
int row_max = 8 - block_size_r;
int col_max = 8 - block_size_col;
// Randomly Iterate through the grid till a perfect row by col is achieved where the block can be placed in the grid
// without overflowing


    // Check if the block can be placed in the grid without overflowing and if the block is not overlapping another block in the grid
    // Ensure that each block is accounted for. Ex. for a 2x2 block, ensure that all 4 spaces are empty, based off block_size_r and block_size_col
for (int i = 0; i < 8; i++) {
    for (int j = 0; j < 8; j++) {
        if (isEmpty(grid, i, j)) {
            if (block_size_r == 1 && block_size_col == 1) {
                rowcol.push_back(i);
                rowcol.push_back(j);
                return rowcol;
            } else if (block_size_r == 1 && block_size_col == 2) {
                if (isEmpty(grid, i, j + 1)) {
                    rowcol.push_back(i);
                    rowcol.push_back(j);
                    return rowcol;
                }
            } else if (block_size_r == 1 && block_size_col == 3) {
                if (isEmpty(grid, i, j + 1) && isEmpty(grid, i, j + 2)) {
                    rowcol.push_back(i);
                    rowcol.push_back(j);
                    return rowcol;
                }
            } else if (block_size_r == 1 && block_size_col == 4) {
                if (isEmpty(grid, i, j + 1) && isEmpty(grid, i, j + 2) && isEmpty(grid, i, j + 3)) {
                    rowcol.push_back(i);
                    rowcol.push_back(j);
                    return rowcol;
                }
            } else if (block_size_r == 1 && block_size_col == 5) {
                if (isEmpty(grid, i, j + 1) && isEmpty(grid, i, j + 2) && isEmpty(grid, i, j + 3) &&
                    isEmpty(grid, i, j + 4)) {
                    rowcol.push_back(i);
                    rowcol.push_back(j);
                    return rowcol;
                }
            } else if (block_size_r == 2 && block_size_col == 1) {
                if (isEmpty(grid, i + 1, j)) {
                    rowcol.push_back(i);
                    rowcol.push_back(j);
                    return rowcol;
                }
            } else if (block_size_r == 2 && block_size_col == 2) {
                if (isEmpty(grid, i + 1, j) && isEmpty(grid, i, j + 1) && isEmpty(grid, i + 1, j + 1)) {
                    rowcol.push_back(i);
                    rowcol.push_back(j);
                    return rowcol;
                }
            } else if (block_size_r == 2 && block_size_col == 3) {
                if (isEmpty(grid, i + 1, j) && isEmpty(grid, i, j + 1) && isEmpty(grid, i + 1, j + 1) &&
                    isEmpty(grid, i, j + 2) && isEmpty(grid, i + 1, j + 2)) {
                    rowcol.push_back(i);
                    rowcol.push_back(j);
                    return rowcol;
                }
            } else if (block_size_r == 2 && block_size_col == 4) {
                if (isEmpty(grid, i + 1, j) && isEmpty(grid, i, j + 1) && isEmpty(grid, i + 1, j + 1) &&
                    isEmpty(grid, i, j + 2) && isEmpty(grid, i + 1, j + 2) && isEmpty(grid, i, j + 3) &&
                    isEmpty(grid, i + 1, j + 3)) {
                    rowcol.push_back(i);
                    rowcol.push_back(j);
                    return rowcol;
                }
            } else if (block_size_r == 3 && block_size_col == 1) {
                if (isEmpty(grid, i + 1, j) && isEmpty(grid, i + 2, j)) {
                    rowcol.push_back(i);
                    rowcol.push_back(j);
                    return rowcol;
                }
            } else if (block_size_r == 3 && block_size_col == 2) {
                if (isEmpty(grid, i + 1, j) && isEmpty(grid, i + 2, j) && isEmpty(grid, i, j + 1) &&
                    isEmpty(grid, i + 1, j + 1) && isEmpty(grid, i + 2, j + 1)) {
                    rowcol.push_back(i);
                    rowcol.push_back(j);
                    return rowcol;
                }
            } else if (block_size_r == 3 && block_size_col == 3) {
                if (isEmpty(grid, i + 1, j) && isEmpty(grid, i + 2, j) && isEmpty(grid, i, j + 1) &&
                    isEmpty(grid, i + 1, j + 1) && isEmpty(grid, i + 2, j + 1) && isEmpty(grid, i, j) &&
                    isEmpty(grid, i, j + 2) && isEmpty(grid, i + 1, j + 2) && isEmpty(grid, i + 2, j + 2)) {
                    rowcol.push_back(i);
                    rowcol.push_back(j);
                    return rowcol;
                }

            } else if (block_size_r == 4 && block_size_col == 1) {
                if (isEmpty(grid, i + 1, j) && isEmpty(grid, i + 2, j) && isEmpty(grid, i + 3, j)) {
                    rowcol.push_back(i);
                    rowcol.push_back(j);
                    return rowcol;
                }
            } else if (block_size_r == 4 && block_size_col == 2) {
                if (isEmpty(grid, i + 1, j) && isEmpty(grid, i + 2, j) && isEmpty(grid, i + 3, j) &&
                    isEmpty(grid, i, j + 1) && isEmpty(grid, i + 1, j + 1) && isEmpty(grid, i + 2, j + 1) &&
                    isEmpty(grid, i + 3, j + 1)) {
                    rowcol.push_back(i);
                    rowcol.push_back(j);
                    return rowcol;
                }
            } else if (block_size_r == 5 && block_size_col == 1) {
                if (isEmpty(grid, i + 1, j) && isEmpty(grid, i + 2, j) && isEmpty(grid, i + 3, j) &&
                    isEmpty(grid, i + 4, j)) {
                    rowcol.push_back(i);
                    rowcol.push_back(j);
                    return rowcol;
                }
            } else if (block_size_r == 5 && block_size_col == 2) {
                if (isEmpty(grid, i + 1, j) && isEmpty(grid, i + 2, j) && isEmpty(grid, i + 3, j) &&
                    isEmpty(grid, i + 4, j) && isEmpty(grid, i, j + 1) && isEmpty(grid, i + 1, j + 1) &&
                    isEmpty(grid, i + 2, j + 1) && isEmpty(grid, i + 3, j + 1) && isEmpty(grid, i + 4, j + 1)) {
                    rowcol.push_back(i);
                    rowcol.push_back(j);
                    return rowcol;
                }
            } else if (block_size_r == 6 && block_size_col == 1) {
                if (isEmpty(grid, i + 1, j) && isEmpty(grid, i + 2, j) && isEmpty(grid, i + 3, j) &&
                    isEmpty(grid, i + 4, j) && isEmpty(grid, i + 5, j)) {
                    rowcol.push_back(i);
                    rowcol.push_back(j);
                    return rowcol;
                }
            } else if (block_size_r == 6 && block_size_col == 2) {
                if (isEmpty(grid, i + 1, j) && isEmpty(grid, i + 2, j) && isEmpty(grid, i + 3, j) &&
                    isEmpty(grid, i + 4, j) && isEmpty(grid, i + 5, j) && isEmpty(grid, i, j + 1) &&
                    isEmpty(grid, i + 1, j + 1) && isEmpty(grid, i + 2, j + 1) && isEmpty(grid, i + 3, j + 1) &&
                    isEmpty(grid, i + 4, j + 1) && isEmpty(grid, i + 5, j + 1)) {
                    rowcol.push_back(i);
                    rowcol.push_back(j);
                    return rowcol;
                }
            } else if (block_size_r == 7 && block_size_col == 1) {
                if (isEmpty(grid, i + 1, j) && isEmpty(grid, i + 2, j) && isEmpty(grid, i + 3, j) &&
                    isEmpty(grid, i + 4, j) && isEmpty(grid, i + 5, j) && isEmpty(grid, i + 6, j)) {
                    rowcol.push_back(i);
                    rowcol.push_back(j);
                    return rowcol;
                }
            } else if (block_size_r == 7 && block_size_col == 2) {
                if (isEmpty(grid, i + 1, j) && isEmpty(grid, i + 2, j) && isEmpty(grid, i + 3, j) &&
                    isEmpty(grid, i + 4, j) && isEmpty(grid, i + 5, j) && isEmpty(grid, i + 6, j) &&
                    isEmpty(grid, i, j + 1) && isEmpty(grid, i + 1, j + 1) && isEmpty(grid, i + 2, j + 1) &&
                    isEmpty(grid, i + 3, j + 1) && isEmpty(grid, i + 4, j + 1) && isEmpty(grid, i + 5, j + 1) &&
                    isEmpty(grid, i + 6, j + 1)) {
                    rowcol.push_back(i);
                    rowcol.push_back(j);
                    return rowcol;
                }
            } else if (block_size_r == 8 && block_size_col == 1) {
                if (isEmpty(grid, i + 1, j) && isEmpty(grid, i + 2, j) && isEmpty(grid, i + 3, j) &&
                    isEmpty(grid, i + 4, j) && isEmpty(grid, i + 5, j) && isEmpty(grid, i + 6, j) &&
                    isEmpty(grid, i + 7, j)) {
                    rowcol.push_back(i);
                    rowcol.push_back(j);
                    return rowcol;
                }
            } else if (block_size_r == 8 && block_size_col == 2) {
                if (isEmpty(grid, i + 1, j) && isEmpty(grid, i + 2, j) && isEmpty(grid, i + 3, j) &&
                    isEmpty(grid, i + 4, j) && isEmpty(grid, i + 5, j) && isEmpty(grid, i + 6, j) &&
                    isEmpty(grid, i + 7, j) && isEmpty(grid, i, j + 1) && isEmpty(grid, i + 1, j + 1) &&
                    isEmpty(grid, i + 2, j + 1) && isEmpty(grid, i + 3, j + 1) && isEmpty(grid, i + 4, j + 1) &&
                    isEmpty(grid, i + 5, j + 1) && isEmpty(grid, i + 6, j + 1) && isEmpty(grid, i + 7, j + 1)) {
                    rowcol.push_back(i);
                    rowcol.push_back(j);
                    return rowcol;

                }
            }  // check 2x5
            else if (block_size_r == 2 && block_size_col == 5) {
             if (isEmpty(grid, i, j + 1) && isEmpty(grid, i, j + 2) && isEmpty(grid, i, j + 3) &&
                    isEmpty(grid, i, j + 4) && isEmpty(grid, i + 1, j) && isEmpty(grid, i + 1, j + 1) &&
                    isEmpty(grid, i + 1, j + 2) && isEmpty(grid, i + 1, j + 3) && isEmpty(grid, i + 1, j + 4)) {
                    rowcol.push_back(i);
                    rowcol.push_back(j);
                    return rowcol;
                }
            } else if (block_size_r == 3 && block_size_col == 5) {
                if (isEmpty(grid, i, j + 1) && isEmpty(grid, i, j + 2) && isEmpty(grid, i, j + 3) &&
                    isEmpty(grid, i, j + 4) && isEmpty(grid, i + 1, j + 1) && isEmpty(grid, i + 1, j + 2) &&
                    isEmpty(grid, i + 1, j + 3) && isEmpty(grid, i + 1, j + 4) && isEmpty(grid, i + 2, j + 1) &&
                    isEmpty(grid, i + 2, j + 2) && isEmpty(grid, i + 2, j + 3) && isEmpty(grid, i + 2, j + 4)) {
                    rowcol.push_back(i);
                    rowcol.push_back(j);
                    return rowcol;
                }
            } else if (block_size_r == 4 && block_size_col == 5) {
                if (isEmpty(grid, i, j + 1) && isEmpty(grid, i, j + 2) && isEmpty(grid, i, j + 3) &&
                    isEmpty(grid, i, j + 4) && isEmpty(grid, i + 1, j + 1) && isEmpty(grid, i + 1, j + 2) &&
                    isEmpty(grid, i + 1, j + 3) && isEmpty(grid, i + 1, j + 4) && isEmpty(grid, i + 2, j + 1) &&
                    isEmpty(grid, i + 2, j + 2) && isEmpty(grid, i + 2, j + 3) && isEmpty(grid, i + 2, j + 4) &&
                    isEmpty(grid, i + 3, j + 1) && isEmpty(grid, i + 3, j + 2) && isEmpty(grid, i + 3, j + 3) &&
                    isEmpty(grid, i + 3, j + 4)) {
                    rowcol.push_back(i);
                    rowcol.push_back(j);
                    return rowcol;
                }

            } // 3x4
            else if (block_size_r == 3 && block_size_col == 4) {
                if (isEmpty(grid, i, j + 1) && isEmpty(grid, i, j + 2) && isEmpty(grid, i, j + 3) &&
                    isEmpty(grid, i + 1, j + 1) && isEmpty(grid, i + 1, j + 2) && isEmpty(grid, i + 1, j + 3) &&
                    isEmpty(grid, i + 2, j + 1) && isEmpty(grid, i + 2, j + 2) && isEmpty(grid, i + 2, j + 3)) {
                    rowcol.push_back(i);
                    rowcol.push_back(j);
                    return rowcol;
                }
            } else if (block_size_r == 4 && block_size_col == 4) {
                if (isEmpty(grid, i, j + 1) && isEmpty(grid, i, j + 2) && isEmpty(grid, i, j + 3) &&
                    isEmpty(grid, i + 1, j + 1) && isEmpty(grid, i + 1, j + 2) && isEmpty(grid, i + 1, j + 3) &&
                    isEmpty(grid, i + 2, j + 1) && isEmpty(grid, i + 2, j + 2) && isEmpty(grid, i + 2, j + 3) &&
                    isEmpty(grid, i + 3, j + 1) && isEmpty(grid, i + 3, j + 2) && isEmpty(grid, i + 3, j + 3)) {
                    rowcol.push_back(i);
                    rowcol.push_back(j);
                    return rowcol;
                }
            } else if (block_size_r == 5 && block_size_col == 4) {
                if (isEmpty(grid, i, j + 1) && isEmpty(grid, i, j + 2) && isEmpty(grid, i, j + 3) &&
                    isEmpty(grid, i + 1, j + 1) && isEmpty(grid, i + 1, j + 2) && isEmpty(grid, i + 1, j + 3) &&
                    isEmpty(grid, i + 2, j + 1) && isEmpty(grid, i + 2, j + 2) && isEmpty(grid, i + 2, j + 3) &&
                    isEmpty(grid, i + 3, j + 1) && isEmpty(grid, i + 3, j + 2) && isEmpty(grid, i + 3, j + 3) &&
                    isEmpty(grid, i + 4, j + 1) && isEmpty(grid, i + 4, j + 2) && isEmpty(grid, i + 4, j + 3)) {
                    rowcol.push_back(i);
                    rowcol.push_back(j);
                    return rowcol;
                }
            }

        }
    }
}



    rowcol.push_back(row);
    rowcol.push_back(col);
    std::cout << "row: " << row << " col: " << col << std::endl;
    return rowcol;
}

I'm looking for the best way to optimize what I've implemented. Thanks in the future!

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Welcome to Code Review! The current question title, which states your concerns about the code, is too general to be useful here. Please edit to the site standard, which is for the title to simply state the task accomplished by the code. Please see How to get the best value out of Code Review: Asking Questions for guidance on writing good question titles. \$\endgroup\$ Nov 14, 2022 at 7:48
  • \$\begingroup\$ I think you'll need to show us your isEmtpy() function. And is vector an alias for std::vector? \$\endgroup\$ Nov 15, 2022 at 9:42
  • \$\begingroup\$ (There is no isEmtpy.) \$\endgroup\$
    – greybeard
    Nov 15, 2022 at 11:19

1 Answer 1

3
\$\begingroup\$

You can drastically improve your code, if you also use loops for testing whether block positions are free.

So, first iterate through the outer grid (Of course only until grid size - height and same for columns). Then for each position row and col where you currently are, check from this position, if the block would fit. Again with a loop.

I extended the example and allow for an rectangular grid of any size. But of course, at the beginning of the function, I added a sanity check that everything fits together.

Please see below one potential improvement proposal:

#include <iostream>
#include <vector>
#include <algorithm>

struct Coordinate {
    size_t row{};
    size_t col{};
};

std::vector<Coordinate> findPositions(std::vector<std::vector<int>>& grid, size_t width, size_t height) {

    // Resulting potential positions
    std::vector<Coordinate> result{};

    // sanity check. Check min and max extension of grid and block
    if (
        // Prevent the grid has no rows
        not grid.empty() and
        // Check, the all columns have the same width
        std::all_of(grid.begin(), grid.end(), [&](const std::vector<int>& row) { return row.size() == grid.front().size(); })
        // Block to fit has at least one row and column and is not bigger than the grid
        and (width > 1) and (height > 1) and (width < grid.front().size()) and (height < grid.size())) {
    }


    // Check for all row and columns of the grid
    // But only to a position, where the block could fit
    for (size_t row = 0; row <= (grid.size() - height); ++row) 
        for (size_t col = 0; col <= (grid.front().size() - width); ++col) {

            bool potentialFit = true;
            // Now check, if all cells of the block starting at this row / col positions are empty
            for (size_t blockRow = row; potentialFit and (blockRow < (row + height)); ++blockRow)
                for (size_t blockCol = col; potentialFit and (blockCol < (col + width)); ++blockCol)
                    // If this cell is occupied
                    if (grid[blockRow][blockCol] != 0)
                        // Indicate that we have no soulition and stop loops
                        potentialFit = false;
            // We found a fit. store the postion
            if (potentialFit)
                result.push_back({ row, col });
        }
    return result;
}

int main() {
    std::vector<std::vector<int>> grid{
        { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        { 0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0},
        { 0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0},
        { 1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0},
        { 0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0},
        { 0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0},
    };
    // Look where a 3x4 block will fit in above grid
    for (const Coordinate& c : findPositions(grid, 3, 4))
        std::cout << "Row: " << c.row << "\tCol: " << c.col << '\n';
}

if you want to accept square grids only, you may change in the sanity check:

std::all_of(grid.begin(), grid.end(), [&](const std::vector<int>& row) { return row.size() == grid.size(); })

Of course you can also allow blocks with same width and height only; simply add a new condition.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.