4
\$\begingroup\$

I'm trying to come up with a solution to a coding challenge on Kattis, where there is a 2D grid filled with x's and o's, and the goal is to figure out whether or not a given starting coordinate can reach a given end coordinate by traveling up, down, left, or right. Only the o's are navigable, and the width and height of the grid can each be up to 1000 characters.

Here is an example grid:

xoxxx
ooxxo
oxxxo
ooooo
oxxxx
ooooo

I'll define this as

std::vector<std::string> space;

For this space, e.g., space[0][1] can reach space[5][4].

Note: This isn't quite the problem. I've generalized it a bit because there are some nuances that are a bit irrelevant to efficiency. Here's the actual problem.

I've taken a recursive approach to this problem, and my program passes the first 22 out of the 25 total test cases, before exceeding the 1-second time limit. The algorithm that I thought of was to keep checking whether the next valid coordinate could reach the end. The base case occurs when the starting coordinate is the ending coordinate, and it signifies that the problem's starting point can reach the ending point. If there is no valid next location then the current path cannot reach the ending point. If all the paths reach a dead end then that signifies that the problem's starting point cannot travel to the ending point.

Here are the brains of the program (specifically canTravel):

struct Point {
    int x, y;
    friend bool operator==(const Point &p1, const Point &p2);
};

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

std::vector<Point> memo; // take note of the visited locations to avoid revisiting them

bool memoContains(const Point &p1) {
    return std::find_if(memo.begin(), memo.end(), [&](const Point &p) { return p == p1; }) != memo.end();
}

bool canTravel(const std::vector<std::string> &space, const Point &start, const Point &end) {
    if (start == end) // base case: the start == the destination
        return true; 

    memo.push_back(start); // add current location to the list of visited locations

    /*
    format:

    const auto &next_location = avoid out of bounds error &&
        next location is an 'o' &&
        avoid revisiting a location &&
        recursively check whether the next location can reach the destination

    */

    const auto &right = start.x < space[start.y].length() - 1 && 
        space[start.y][start.x + 1] == 'o' && 
        !memoContains({ start.x + 1, start.y }) && 
        canTravel(space, { start.x + 1, start.y }, end);

    const auto &left = start.x > 0 && 
        space[start.y][start.x - 1] == 'o' && 
        !memoContains({ start.x - 1, start.y }) && 
        canTravel(space, { start.x - 1, start.y }, end);

    const auto &down = start.y < space.size() - 1 && 
        space[start.y + 1][start.x] == 'o' && 
        !memoContains({ start.x, start.y + 1 }) && 
        canTravel(space, { start.x, start.y + 1 }, end);

    const auto &up = p1.y > 0 && 
        space[start.y - 1][start.x] == 'o' && 
        !memoContains({ start.x, start.y - 1 }) && 
        canTravel(space, { start.x, start.y - 1 }, end);

    return right || left || down || up; // at least one path needs to reach the destination
}

Why is this slow/inefficient? How can it be improved? Can a recursive approach be used here or is an iterative one preferable?

\$\endgroup\$
1
\$\begingroup\$

What is killing your performance is memoContains. It turns your algorithm from O(n) into O(n^2).

The better solution is to create a second array of the same size as your input, where you mark each cell visited. Then you can do the check in O(1).

Next, you need to implement a short circuit for your logic. If right is true, there is no point in computing the other directions.

Why do you define right and the other three bools as references?

There are some more tricks you can apply, for example to avoid checking for out-of-bounds indexing by simply making the array one cell larger on all sides, and filling those positions with x.

Finally, regarding recursion. It's a nice way of describing the algorithm. You might get better performance if you use a stack instead. But the only way to know for sure is to try it out and time it. :)

Oh, and one more thing:

std::vector<std::string> space;

Is highly inefficient. Your data is all over the memory because the data for each array is allocated independently. You should probably make this a single vector (or string if you must) that you index as row * width + column. Note that now you can index neighboring cells using simple pointer arithmetic (add 1 to the pointer to access the cell on the right, for example).

\$\endgroup\$
  • \$\begingroup\$ Oh whoops I actually added that short circuiting but accidentally pasted my previous version of this function. I'll give everything else a shot, though. \$\endgroup\$ – Archie Gertsman Jan 27 '18 at 3:43
  • \$\begingroup\$ @ArchieGertsman: I have edited one more time, I keep finding more things to comment on. :) \$\endgroup\$ – Cris Luengo Jan 27 '18 at 3:47
  • 1
    \$\begingroup\$ When using the second array to hold cells that have already been visited, you can set the initial values so that all the 'x' cells are marked visited. Then you won't need to check space for 'o'. \$\endgroup\$ – 1201ProgramAlarm Jan 27 '18 at 4:27
  • \$\begingroup\$ And since you are copying the input into a larger array anyway, you can use 0 and 1 instead of 'o' and 'x', and use any of the other bits in the byte to mark a cell as visited. Using less memory makes it more efficient, the requited bit operations are trivial. \$\endgroup\$ – Cris Luengo Jan 27 '18 at 4:37
  • \$\begingroup\$ @CrisLuengo I've implemented your first and last suggestions, and it's still going over the time limit. Could you please take a look at the updated code? pastebin.com/NHY9dx0g \$\endgroup\$ – Archie Gertsman Jan 30 '18 at 16:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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