3
\$\begingroup\$

I wrote a C++ program to find the solution to a puzzle board (a custom puzzle from my school). The puzzle board is made from squares - tiles. On the different tile middle, side or corner there are points (random amount of points). The mission is to construct blocks from tiles, so that each block contains one and only one point and that point has to be the point symmetry point of the block. The mission is to make blocks so that there are no tiles left that are not in a block.

But my code takes AGES to run with larger inputs (with a board of size 10x10, it runs for hours - literally), and that is definitely because I don't know how to write time and performance efficient C++ code.

I am mainly using a lot of vectors and some custom structs.

If you know any ways I can improve my code, give a redo of it or post some good documentation regarding this situation, please let me see!

#include <iostream>
#include <fstream>
#include <sstream>
#include <array>
#include <vector>
#include <algorithm>



struct Tile {
    int x {0};
    int y {0};

    std::vector<Tile> get_adjacent_fTiles(const std::vector<Tile>& fTiles) const
    {
        std::vector<Tile> adjacentTiles {};
        for(const auto& tile : fTiles) {
            if((x == tile.x && y == tile.y - 1) || (x == tile.x + 1 && y == tile.y) || (x == tile.x && y == tile.y + 1) || (x == tile.x - 1 && y == tile.y)) {
                adjacentTiles.push_back(tile);
            }
        }
        return adjacentTiles;
    }


    void print() const
    {
        std::cout << "\"" << x << "," << y << "\"";
    }
};

bool operator==(const Tile& tile1, const Tile& tile2) {
    return (tile1.x == tile2.x && tile1.y == tile2.y);
}

bool operator!=(const Tile& tile1, const Tile& tile2) {
    return (tile1.x != tile2.x || tile1.y != tile2.y);
}

Tile operator+(const Tile& tile1, const Tile& tile2) {
    return Tile{tile1.x + tile2.x, tile1.y + tile2.y};
}

Tile operator*(int num, const Tile& tile) {
    return Tile{num * tile.x, num * tile.y};
}

Tile operator*(const Tile& tile, int num) {
    return Tile{num * tile.x, num * tile.y};
}

Tile operator*(const Tile& tile1, const Tile& tile2) {
    return Tile{tile1.x * tile1.x, tile2.x * tile2.y};
}

Tile operator/(const Tile& tile, int num) {
    return Tile{tile.x / num, tile.y / num};
}


struct Point {
    int x;
    int y;
    int type;
    
Point(int x, int y) : x(x), y(y)
    {
        if(x % 2 == 0 && y % 2 == 0) type = 0;
        else if(x % 2 != 0 && y % 2 != 0) type = 1;
        else if(x % 2 != 0 && y % 2 == 0) type = 2;
        else type = 3;
    }


    void print() const
    {
        std::cout << "Point" << "(" << x << "," << y << " type: " << type << ")";
    }
};

bool operator==(const Point& point1, const Point& point2) {
    return (point1.x == point2.x && point1.y == point2.y);
}

bool operator!=(const Point& point1, const Point& point2) {
    return (point1.x != point2.x || point1.y != point2.y);
}

bool operator==(const Point& point, const Tile& tile) {
    return (point.x == tile.x && point.y == tile.y);
}

bool operator==(const Tile& tile, const Point& point) {
    return (point.x == tile.x && point.y == tile.y);
}

Tile operator*(const Point& point, const Tile& tile) {
    return Tile{point.x * tile.x, point.y * tile.y};
}

Tile operator*(const Tile& tile, const Point& point) {
    return Tile{point.x * tile.x, point.y * tile.y};
}

Tile operator-(const Point& point, const Tile& tile) {
    return Tile{point.x - tile.x, point.y - tile.y};
}

Tile operator-(const Tile& tile, const Point& point) {
    return Tile{tile.x - point.x, tile.y - point.y};
}


struct Block {
    Point point {0, 0};
    std::vector<Tile> tiles {};

    Block(Point point) : point(point)
    {
        if(point.type == 0) {
            tiles.push_back({point.x/10, point.y/10});
        }
        else if(point.type == 1) {
            tiles.push_back({(point.x+5)/10-1, (point.y+5)/10-1});
            tiles.push_back({(point.x+5)/10-1, (point.y+5)/10});
            tiles.push_back({(point.x+5)/10, (point.y+5)/10-1});
            tiles.push_back({(point.x+5)/10, (point.y+5)/10});
        }
        else if(point.type == 2) {
            tiles.push_back({(point.x+5)/10-1, point.y/10});
            tiles.push_back({(point.x+5)/10, point.y/10});
        }
        else {
            tiles.push_back({point.x/10, (point.y+5)/10-1});
            tiles.push_back({point.x/10, (point.y+5)/10});
        }
    }

    void add_tile(const Tile& tile)
    {
        tiles.push_back(tile);
        //std::cout << "Tile added\n";
    }

    void expand(const Tile& tile)
    {
        add_tile(tile);
        add_tile((point - 5*tile)/5);
        //std::cout << "Block expanded\n";
    }

    void remove_tile()
    {
        tiles.pop_back();
    }

    void remove_eTile_pair()
    {
        tiles.pop_back();
        tiles.pop_back();
    }

    std::vector<Tile> get_adjacent_fTiles(const std::vector<Tile>& fTiles) const
    {
        std::vector<Tile> adjacentFTiles;
        for(const auto& tile : tiles) {
            for(const auto& fTile : tile.get_adjacent_fTiles(fTiles)) {
                if (std::find(adjacentFTiles.begin(), adjacentFTiles.end(), fTile) == adjacentFTiles.end()) {
                    adjacentFTiles.push_back(fTile);
                }
            }
        }
        return adjacentFTiles;
    }

    std::vector<Tile> get_expandable_tiles(const std::vector<Tile>& fTiles) const
    {
        std::vector<Tile>expandableTiles {};
        std::vector<Tile> test = get_adjacent_fTiles(fTiles);
        for(const auto& fTile1 : get_adjacent_fTiles(fTiles)) {
            for(const auto& fTile2 : get_adjacent_fTiles(fTiles)) {
                if((fTile1 != fTile2) && point == 5*(fTile1 + fTile2)) {
                    if (std::find(expandableTiles.begin(), expandableTiles.end(), fTile2) == expandableTiles.end()) { 
                        expandableTiles.push_back(fTile1);
                        break;
                    }   
                }
            }
        }
        return expandableTiles;
    }


    void print() const
    {
        point.print(); std::cout << ": ";
        for(auto& tile : tiles) {
            tile.print(); std::cout << " ";
        }
    }


    bool operator==(const Block& block) const {
        if(point != block.point) return false;
        if(tiles.size() != block.tiles.size()) return false;
        for(auto i = 0; i < tiles.size(); i++) {
            if(tiles[i] != block.tiles[i]) return false;
        }
        return true;
    }

    bool operator!=(const Block& block) const {
        if(point != block.point) return true;
        if(tiles.size() != block.tiles.size()) return true;
        for(auto i = 0; i < tiles.size(); i++) {
            if(tiles[i] != block.tiles[i]) return true;
        }
        return false;
    }
};


struct Board {
    int x {0};
    int y {0};
    std::vector<Block> blocks;

    std::vector<Tile> get_fTiles()
    {
        std::vector<Tile> emptyTiles;
        emptyTiles.reserve(x * y);
        for(int i = 0; i < x; i++) {
            for(int j = 0; j < y; j++) {
                bool found = false;
                for(const auto& block : blocks) {
                    if(found) break;
                    for(const auto& tile : block.tiles) {
                        if(i == tile.x && j == tile.y) {
                            found = true; 
                            break;
                        }
                    }
                }
                if(!found) emptyTiles.push_back({i, j});
            }
        }
        return emptyTiles;
    }

    bool is_expandable()
    {
        for(const auto& block : blocks) {
            if(block.get_adjacent_fTiles(get_fTiles()).size() != 0) return true;
        }
        return false;
    }

    bool is_finished()
    {
        int sum = 0;
        for(const auto& block : blocks) {
            for(const auto& tile : block.tiles) {
                sum++;
            }
        }
        return (sum == x * y);
    }


    void print()
    {
        std::cout << "---Printing board info---\n";
        for(auto& block : blocks) { block.print(); std::cout << '\n'; }
        std::cout << "Empty tiles: ";
        for(auto& fTile : get_fTiles()) { fTile.print(); std::cout << " "; }
        std::cout << "\n---Printing finished---\n";
    }


    bool operator==(const Board& board) const {
    if(blocks.size() != board.blocks.size()) return false;
    for(auto i = 0; i < blocks.size(); i++) {
        if(!(blocks[i] == board.blocks[i])) return false;
    }
        return true;
    }
};





Board getBoardData(const std::string& filePath)
{
    std::ifstream dataFile(filePath);
    Board board;
    if (dataFile.is_open()) {
        std::string line;
        //get board size
        {
            std::getline(dataFile, line);
            std::stringstream ss(line);
            std::string token;
            std::getline(ss, token, ',');
            board.x = std::stoi(token);
            std::getline(ss, token);
            board.y = std::stoi(token);
        }
        //HERE
        while(std::getline(dataFile, line)) {
            std::stringstream ss(line);
            std::string token;
            int x = 0; int y = 0;
            std::getline(ss, token, ',');
            x = std::stoi(token);
            std::getline(ss, token, ',');
            y = std::stoi(token);
            board.blocks.push_back(Block{Point{x, y}});
        }
        dataFile.close();
    }
    return board;
}



void generateBoard(Board board, Board& solvedBoard, bool& boardFound)
{
    if(boardFound) {
        std::cout << "\n\n\nFOUND!!!!!!!!\n\n\n";
        return;
    }
    for(auto& block : board.blocks) {
        for(auto& eTile : block.get_expandable_tiles(board.get_fTiles())) {
            block.expand(eTile);

            if(board.is_finished()) {
                solvedBoard = board;
                boardFound = true;
                return;
            }
            if(!board.is_expandable()) {
                block.remove_eTile_pair();
                return;
            }
            //board.print();
            generateBoard(board, solvedBoard, boardFound);
            block.remove_eTile_pair();
        }
    }
}

Board solveBoard(Board board)
{
    static Board solvedBoard;
    static bool boardFound;

    if(board.is_finished()) {
        return board;
    }
    if(!board.is_expandable()) return {};

    generateBoard(board, solvedBoard, boardFound);

    return solvedBoard;
}

int main()
{
    const std::string filePath = "LitFO70";
    Board board = getBoardData(filePath);
    board.print();
    Board solvedBoard = solveBoard(board);
    std::cout << "FINISHED";
    if(!solvedBoard.is_finished()) std::cout << "\nNo solved boards found!";
    std::cout << "\nSolved board:\n";
    board.print();
    return 0;
}
\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

Enable compiler warnings and fix all of them

Your code compiles, but my compiler warns about comparisons between integers of different kinds. This is because of your use of auto i = 0 in several for-loops. The compiler deduces that 0 is an int, but you want a std::size_t here. The easy fix is to just write std::size_t explicitly:

for (std::size_t i = 0; i < tiles.size(); ++i) {
    …
}

There is one other warning about an unused variable tile in this piece of code:

for(const auto& tile : block.tiles) {
    sum++;
}

This whole loop can just be replaced with:

sum += block.tiles.size();

Code formatting issues

While code style is somewhat of a matter of taste, and the most important thing is just to be consistent, there are some things I think you should avoid. In particular, always put the body of if, for and similar statements on a separate line. This makes it easier to visually spot them. For example, instead of:

if(!found) emptyTiles.push_back({i, j});

Write:

if(!found)
    emptyTiles.push_back({i, j});

You might also consider always putting braces around the body of such statements:

if(!found) {
    emptyTiles.push_back({i, j});
}

This avoids making mistakes when adding another statement to the body if the if; if there were no braces and you forget to add them, it's not going to do what you expect.

Instead of fixing code formatting issues manually, I recommend you use a formatting tool like ClangFormat or Artistic Style.

Naming things

I think the names you chose for functions, types and variables are mostly fine. However, just like with code formatting, make sure you are consistent. I see some functions names having snake_case (is_finished()), others have camelCase (getBoardData()).

Don't abbreviate unnecessarily, but if you do, be consistent. I see both expandable_tiles and eTiles used.

I assumed eTiles meant "expandable tiles", or is it "expanded tiles"? That's already a bit confusing, but what I don't know at all is what the f stands for in fTiles. Or was it because it stands for "empty tiles", but you already used the e for something else, and just went for the next letter in the alphabet? If so, that's pretty terrible!

x and y are common names for coordinates, so it's fine to use them. However, they are not the right names for sizes. I would use width and height for that. This will make much more sense in get_fTiles():

std::vector<Tile> emptyTiles;
emptyTiles.reserve(width * height);

for (int x = 0; x < width; ++x) {
    for (int y = 0; y < height; ++y) {
        …
        if (x == tile.x && y == tile.y) {
            …
        }
        …
    }
}

Make more functions const

You made some functions const already, but the member functions of Board can all be made const as well.

Missing error checking

When reading data from a file, many things can go wrong. Even if the file was opened succesfully, there might be a read error later on. Also, the contents of the file might not be what you expect, so even if reading was succesful, you should not blindly trust what you have read.

The best way to check that you have read all data correctly is to check whether dataFile.eof() is true after reading in all lines. If it isn't, you know you didn't reach the end of the file succesfully.

What if the width or height you read from the first line is zero, or even a negative number? What happens if you read duplicate points? What if parsing a number fails?

If you do encounter an error, make sure you throw an exception, or print an error message to std::cerr, and exit the program with EXIT_FAILURE.

Overload operator<<() intead of creating print() member functions

Instead of calling your own print() functions, wouldn't it be nice if you could just write:

std::cout << "Solved board:\n" << board;

You can do that by overloading operator<<() instead of creating your print() member functions:

struct Board {
    …
    friend std::ostream& operator<<(std::ostream& out, const Board& board) {
        out << "---Printing board info---\n";
        for(auto& block : blocks) { 
            out << block << '\n';
        }
        out << "Empty tiles: ";
        for(auto& fTile : get_fTiles()) {
            out << fTile << " ";
        }
        return out << "\n---Printing finished---\n";
    }
};

Note how it is independent of std::cout: now you can also print a board to a std::fstream or to a std::stringstream.

Don't make local variables static without a reason

In solveBoard(), you made solveBoard and boardFound static. There is no reason to do that, and this makes it non-reentrant and not thread-safe. While that might not matter for this program, I would just remove static.

Performance

But my code takes AGES to run with larger inputs (with a board of size 10x10, it runs for hours - literally), and that is definitely because I don't know how to write time and performance efficient C++ code.

The problem here is not fine-tuning your code to be faster, the problem is in the algorithms you implemented. Consider for example get_fTiles(): you want a list of all the empty tiles. You do this by checking for every possible tile position, if there is a block that contains a tile with that exact position. That's already pretty bad: this takes \$O(W \cdot H \cdot B \cdot T)\$ time, where \$W\$ is width, \$H\$ is height, \$B\$ is the number of blocks and \$T\$ is the number of tiles per block. For a 10 by 10 board, that's probably in the order of 10000 operations. It also has to allocate memory for the vector of empty tiles and put the Tiles in it.

Then you call block.get_adjacent_fTiles(get_fTiles()). This checks for every tile in the block, if one of the tiles in the empty list of tiles is adjacent to that tile, and if it wasn't already in adjacentFTiles, adds it. If the block contained just a few tiles, you were checking against many empty tiles that were not even close to it. If there are many tiles in the block, you might see a lot of duplicate adjacent tiles. This adds a few factors of 10 more to the number of opreations to do on a 10 by 10 board. You also created several more vectors to store tiles in.

But here comes the kicker: in is_expandable(), you then just check if block.get_adjacent_fTiles(get_fTiles()).size() != 0. So after all that tedious work creating vectors of empty and adjacent tiles, you just wanted to know: was there at least 1 adjactend empty tile? So you didn't actually need to store all that tile information!

And then you call is_expandable() inside a double for-loop inside generateBoard(). Every for-loop multiplies the amount of work that needs to be done. This is why your code takes such a huge amount of time to solve just a 10 by 10 board.

So how can you improve this? You have to rethink the way you are doing things, and find algorithms that don't require this many loops, and don't need that many temporary std::vectors to store data in. Consider for example of maintaining an array that stores whether board tiles are empty or not:

struct Board {
    int width{};
    int height{};
    std::vector<Block> blocks;
    std::vector<bool> occupied_tiles;
    …
};

Board getBoardData(const std::string& filePath)
{
    …
    board.occupied_tiles.resize(board.width * board.height);
    …
    board.blocks.push_back(Block{Point{x, y}});
    occupied_tiles[x + y * board.width] = true;
};

Then checking whether a given tile is empty or not is simply reading from occupied_tiles, instead of having go through every tile in every block.

This might not be the only thing that can be improved in your code, but this is generally the kind of thinking you have to do in order to get your algorithm to run faster.

Create proper classes

You created several structs to organize your data, which is great. However, all members are public, and you have several non-member functions that directly modify the member variables of those structs. The problem with that is that is doesn't provide proper encapsulation. Ideally, you create classes (which are just structs where everything is private by default), and only allow the member variabels to be modified via public member functions. These member functions can then ensure the state of an object of that class is always correct. It also forces you to think about what operations are going to be done on objects, and makes it more clear when you perform those operations.

For example, instead of getBoardData() directly accessing the member variables, it would be better to write it like so:

Board getBoardData(const std::string& filePath)
{
    std::ifstream dataFile(filePath);
    std::string line;

    int width;
    int height;

    // Get board size
    {
        …
    }

    Board board(width, height);

    // Read blocks
    while(std::getline(dataFile, line)) {
        …
        board.add_block(Point{x, y});
    }

    if(!dataFile.eof()) {
        throw std::runtime_error("Could not read input file!");
    }

    return board;
}
\$\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.