6
\$\begingroup\$

This inspired by this C# question

The basics is to calculate the total number of paths that a rook can take without revisiting a square to move to a diagonally opposite position.

I tried to throw every possible tool in my rather limited toolset at this and got a pretty decent improvement.

To calculate all the possible moves for grids < 7x7 takes less than a second and a 7x7 grid takes about 45 seconds.

I have tried to calculate the moves for an 8x8 grid but after 12 hours my office started to smell like burning plastic and I gave up.

Is there any way to make this more efficient?

#include <atomic>
#include <chrono>
#include <iostream>
#include <thread>
#include <vector>

typedef unsigned long long uint64;
typedef unsigned int uint32;

std::atomic<uint64> pathsFound = 0;

class Board
{
public:
    Board(uint32 rows, uint32 cols)
        :
        rows{ rows },
        cols{ cols }
    {
        for (uint32 y = 0; y < rows; y++)
        {
            for (uint32 x = 0; x < cols; x++)
            {
                squares.push_back(calcMoves(x, y));
            }
        }
    }

    uint32 calcIndex(uint32 x, uint32 y)
    {
        return x + y * cols;
    }

    uint64 calcBit(uint32 index)
    {
        uint64 one = 1;
        return one << index;
    }

    std::vector<uint32> calcMoves(uint32 x, uint32 y)
    {
        std::vector<uint32> moves;
        if (x > 0)
            moves.push_back(calcIndex(x - 1, y));
        if (x < cols - 1)
            moves.push_back(calcIndex(x + 1, y));
        if (y > 0)
            moves.push_back(calcIndex(x, y - 1));
        if (y < rows - 1)
            moves.push_back(calcIndex(x, y + 1));
        return moves;
    }

    void GetPaths(uint64 path, uint32 currentIndex, uint32 targetIndex, uint32 level)
    {
        if (currentIndex == targetIndex)
        {
            pathsFound++;
            return;
        }

        path |= calcBit(currentIndex);    

        if (level < 4)
        {
            #pragma omp parallel for 
            for (int i = 0; i < squares[currentIndex].size(); i++)
            {
                uint32 move = squares[currentIndex][i];
                if ((uint64)(path & calcBit(move)) == (uint64)0)
                {
                    GetPaths(path, move, targetIndex, level + 1);
                }
            }
        }
        else
        {
            for (uint32 move : squares[currentIndex])
            {
                if ((uint64)(path & calcBit(move)) == (uint64)0)
                {
                    GetPaths(path, move, targetIndex, level + 1);
                }
            }
        }
    }
    uint32 rows;
    uint32 cols;
    std::vector<std::vector<uint32>> squares;
};

void timer(std::stop_token stoken)
{
    using namespace std::chrono;
    auto begin = steady_clock::now();
    while (!stoken.stop_requested())
    {
        std::this_thread::sleep_for(seconds(1));
        auto end = steady_clock::now();
        std::cout << "found = " << pathsFound << ", ellapsed = " << duration_cast<seconds>(end - begin).count() << " sec.\n";
    }
}

int main()
{
    constexpr uint32 size = 7;
    Board board(size, size);

    std::jthread tt(timer);

    uint32 currentIndex = board.calcIndex(0, 0);
    uint32 targetIndex = board.calcIndex(size - 1, size - 1);
    board.GetPaths(0, currentIndex, targetIndex, 0);

    tt.request_stop();
    tt.join();

    std::cout << "Paths = " << pathsFound;
}
\$\endgroup\$
6
  • \$\begingroup\$ Using std::vector<std::vector<T>> for 2D grid is often repeated beginner-like decision. Prefer std::array<T, rows * cols> (then you should use rows, cols as template parameter of Board), or if you want to get rows/cols dynamically, use std::unique_ptr<T[]> \$\endgroup\$
    – frozenca
    Nov 6, 2021 at 14:10
  • \$\begingroup\$ @frozenca, it's is a vector that contains possible moves for each square. I agree that std::array might have been better but it will make zero difference to the performance. \$\endgroup\$
    – jdt
    Nov 6, 2021 at 14:12
  • \$\begingroup\$ Oh, my bad. Isn't using uint32 for move an overkill? How about uint8 instead? \$\endgroup\$
    – frozenca
    Nov 6, 2021 at 14:16
  • 2
    \$\begingroup\$ Reference: oeis.org/A007764 \$\endgroup\$
    – Carsten S
    Nov 7, 2021 at 16:44
  • 2
    \$\begingroup\$ @CarstenS, thanks, very interesting. I especially liked the youtube video :-) \$\endgroup\$
    – jdt
    Nov 7, 2021 at 17:35

2 Answers 2

7
\$\begingroup\$

Use standard integer types

Don't use typedef to create your own fixed-size integer types. The standard library provides types like std::uint32_t and std::uint64_t for you. Your typedefs might not be correct on all platforms. C only guarantees that an int is at least 16 bits for example, and a long long might actually be larger than 64 bits.

If you want to save a bit of typing, then you can bring the standard types into the global namespace so you can avoid having to write std::, like so:

#include <cstdint>

using std::uint32_t;
using std::uint64_t;

But don't do this inside header files.

Make the board's dimensions template parameters

Perhaps the compiler will see that you use a constant for the size of the board and will optimize your code accordingly, but to avoid any doubt, you can use template paramaters to set the size of a Board:

template<std::size_t rows, std::size_t cols>
class Board {
public:
    Board() {
        for (std::size_t y = 0; y < rows; y++) {
            ...

Optimize finding valid rook moves

You are pre-computing a vector of vector for all the valid rook moves. Traversing squares means double pointer indirection. It is probably much faster to try all four directions inside GetPaths(), and check for each direction whether it is valid there. So something like:

#pragma omp parallel for 
for (int dir = 0; dir < 4; ++dir) {
    if (auto move = GetValidMove(currentIndex, dir)) {
        if (!(path & calcBit(*move)) {
            GetPaths(path, *move, targetIndex, level + 1);
        }
    }
}

Where GetValidMove() looks like this:

std::optional<std::uint32_t> GetValidMove(std::uint32_t index, int dir) {
    switch (dir) {
    case 0:
         if (index % cols)        // will be efficient on an 8x8 board
             return index - 1;
         else
             return std::nullopt; // {} works as well
    case 1:
         ...
    }
}

Rook or king moves?

You are only checking for moves to adjacent tiles. In chess, a rook can move as much as it wants in a horizontal or vertical direction. If it moves from one side to the other, you don't count the tiles inbetween as visited.

Prune dead ends early

If you always start at the top left of the board, and after a few moves you hit another wall like so:

 --------
|#       |
|##      |
| ####   |
|    ###X|
|        |
 --------

Then you know that you just partitioned the board into two halves, and one half is a dead zone. In the case of hitting the right wall, going up is never going to get you to the bottom right again. But your algorithm will explore every possible path within the dead zone. Adding a check for this might make each move less efficient, but pruning huge parts of the solution space this way might more than make up for it.

Make functions static and/or const where possible

Functions like calcIndex() and calcBit() neither use nor modify member variables, so they should be made static and const:

static std::uint32 calcIndex(std::uint32 x, std::uint32 y) const {
    ...
}

GetPaths() doesn't modify any member variables, so it can be made const. But that also brings me to:

Avoid making a class unnecessarily

In Java and C#, everything has to be in a class. However, in C++ there is no such requirement. In your code, you are only interested in calling GetPaths(). Consider writing it as a free function:

template<std::size_t rows, std::size_t cols>
static GetPaths(std::uint32_t currentIndex = 0, std::uint32_t targetIndex = rows * cols - 1, std::uint64_t path = 0, std::uint32_t level = 0) {
    ...
    GetPaths(move, targetIndex, path, level + 1);
    ...
}

int main() {
    std::jthread tt(timer);
    GetPaths<7, 7>();
    std::cout << "Paths = " << pathsFound << '\n';
}

Make GetPaths() return the number of paths

I understand why you made pathsFound a global atomic variable, as it's the easiest way to have a separate thread show the progress. However, it has some drawbacks:

  • It uses global state, so you cannot run GetPaths() for multiple boards a the same time.
  • Atomics themselves are not free and might make the code less efficient.
  • Functions should return their results via the return parameter.

I would make it so it returns the number of paths, but you can still use a global atomic for debugging:

template<...>
static std::uint64_t GetPaths(...) {
    if (currentIndex == targetIndex)
    {
        pathsFound++; // for debugging purposes
        return 1;
    }

    ...
    std::uint64_t num_paths{};
    ...
    num_paths += GetPaths(...);
    ...
    return num_paths;
}
\$\endgroup\$
3
  • \$\begingroup\$ The King versus Rook part bothered me about the original C# question as well. \$\endgroup\$
    – pacmaninbw
    Nov 6, 2021 at 14:56
  • \$\begingroup\$ Thanks for your review. I'm going to experiment with early pruning and all the other suggestions. I'm not really sure what you mean with double pointer indirection. I would have thought that pre-calculating the moves would be faster than messing with division and modulus operations. \$\endgroup\$
    – jdt
    Nov 6, 2021 at 21:44
  • \$\begingroup\$ A std::vector<T> is basically a size and a pointer to an array of Ts. A std::vector<std::vector<T>> is therefore a size and a pointer to an array of sizes and pointers to arrays of Ts. Everything the CPU does costs some cycles. Following pointers has its cost. Division and modulus is expensive in general as well, but it can be very cheap if the size of your board is a power of two, as a compiler will, for example, be able to convert % 8 into & 7. \$\endgroup\$
    – G. Sliepen
    Nov 6, 2021 at 22:27
1
\$\begingroup\$

Timer logic drift

I know this will not help you speed it up, but your timer logic has some potential for drift. It could be that you see output for seconds 1, 2, 3, and 5, but not for 4, if your cpu is under heavy load.

To prevent drift, instead of

void timer(std::stop_token stoken)
{
    using namespace std::chrono;
    auto begin = steady_clock::now();
    while (!stoken.stop_requested())
    {
        std::this_thread::sleep_for(seconds(1));
        auto end = steady_clock::now();
        std::cout << "found = " << pathsFound << ", ellapsed = " << duration_cast<seconds>(end - begin).count() << " sec.\n";
    }
}

use something like

void timer(std::stop_token stoken)
{
    using namespace std::chrono;
    auto begin = steady_clock::now();
    size_t secondsSinceStart = 0;
    while (!stoken.stop_requested())
    {
        std::this_thread::sleep_until(begin + seconds(++secondsSinceStart));
        std::cout << "found = " << pathsFound << ", ellapsed = " << secondsSinceStart << " sec.\n";
    }
}

This will ensure that you get output for every second, reducing potential further trouble if you'd want to parse your output.

(It's not a big improvement, definitely not to performance, but a good habit to get into writing timed things this way.)

\$\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.