Finding strings in a matrix

Looking for feedback especially regarding design/structure/naming but also anything else that can be improved upon.

Task: Given a (hardcoded) matrix, find out if a given string can be found without visiting a cell twice. Movement is restricted to horizontal/vertical and only adjacent cells can be visited. Print "True" if the input string can be found "False" otherwise.

Matrix:

ABCE
SFCS


Example:

Input: CSE

Result: True. (Start from the C in the 2nd row, go right, go up)

Source code:

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <tuple>
#include <set>

using std::get;
using std::make_tuple;

const std::vector<std::vector<char>> matrix =
{
{'A', 'B', 'C', 'E'},
{'S', 'F', 'C', 'S'},
{'A', 'D', 'E', 'E'},
};

const std::vector<std::tuple<int, int>> directions =
{
make_tuple(-1, 0),
make_tuple(0, 1),
make_tuple(1, 0),
make_tuple(0, -1),
};

std::set<std::tuple<int, int>> used;
std::string chars;

bool find_next_match(size_t index, std::tuple<int, int> cur_pos)
{
if (index == chars.size() - 1) return true;

++index;

used.insert(cur_pos);

for (const auto &dir : directions)
{
auto new_pos = make_tuple(get<0>(cur_pos) + get<0>(dir), get<1>(cur_pos) + get<1>(dir));

if (get<0>(new_pos) < 0 || get<0>(new_pos) > 2) continue;
if (get<1>(new_pos) < 0 || get<1>(new_pos) > 3) continue;

if (used.count(new_pos)) continue;

if (matrix[get<0>(new_pos)][get<1>(new_pos)] != chars[index]) continue;

if (find_next_match(index, new_pos)) return true;
}

used.erase(cur_pos);

return false;
}

int main (int argc, char **argv)
{
std::ifstream infile(argv[1], std::ios::in | std::ifstream::binary);

std::string line;
while (getline(infile, line))
{
chars.clear();
chars = line;

bool found = false;
for (int m = 0; m < 3; ++m)
{
for (int n = 0; n < 4; ++n)
{
if (matrix[m][n] == chars[0])
{
used.clear();
if (find_next_match(0, make_tuple(m, n)))
{
found = true;
break;
}
}
if (found) break;
}
}

if (found) std::cout << "True\n";
else std::cout << "False\n";
}
}


Edit 1:

I changed the find_next_match function to operate on the string directly instead of passing an addiontal argument to keep the amount of arguments under 3 (as per recommendation in Robert C. Martins Clean Code)

Revision 2 based on advice by @vnp

Edit 2:

Revision 3 based on advice by @miscco

• Avoid magic numbers.

It is not immediately clear what 2 and 3 in find_next_match stand for (same for 3 and 4 in main). Even though the matrix is hardcoded, I recommend to infer its dimensions, rather then hardcode them also.

• Avoid globals.

Passing std::string& line as an additional parameter to find_next_match is cleaner then reliance on the global, and obviates the (pretty strange)

    chars.clear();
chars = line;

• tuple vs custom class.

Using a tuple makes the code too verbose to my taste. I'd invest into a struct position with an operator+ overloaded to perform what

    make_tuple(get<0>(cur_pos) + get<0>(dir), get<1>(cur_pos) + get<1>(dir));


does.

• Nitpicks.

• You should test if infile is opened correctly.
• Final print may use a ternary

    std::cout << (found? "True": "False") << '\n';

• I don't want to start a holy war, but I'd return 0; from main.

• Kudos for not using namespace std;
• Thanks for the answer. I will update my question as soon as I can. Two quick questions: - Is there a specific reason you recommend a struct over a class? - In another post I was told to leave return 0; out because it's implicit and the compiler does indeed not complain about it (with settings: -Wall -Wextra -pedantic -O2). I was not aware that this is a holy war issue. – yuri May 23 '17 at 21:36
• @Yuri (1) struct over class - no particular reason. (2) omitting return 0 is perfectly legal; no compiler shall ever complain. Both are just the matter of personal preference of an old schooler. – vnp May 24 '17 at 4:56
• I hope I implemented most of your advice. Keep in mind that I have never done operator overloading before so that part might be pretty bad. – yuri May 24 '17 at 8:58

Let's have a look at your updated code:

Constructors

Point(int a, int b) :
x(a),
y(b)
{};

Point(const Point &p) :
x(std::move(p.x)),
y(std::move(p.y))
{};


The first one is fine, although I would generally mark the inputs a and b as const. However, given that they are basic integers it doesn't matter too much.

However, what is troubling is you mangling of a copy constructor with move semantics. You can only have one. When you pass p as a const reference you cannot move its values, as that would change them, So you have to write one copy constructor and one move constructor. For the copy constructor you can delegate to the explicit one:

Point(const Point &p) : Point(p.x, p.y) {};


For more complex classes, look into the copy and swap idiom which makes life much more easier .

Member access

Avoid the usage of this-> in your code. The only moment you have to use it is when you have name collisions. You should never have name collisions, so you should never need this->.

Operators

bool operator<(const Point& rhs) const
{
if (x != rhs.x)
{
return x < rhs.x;
}
else
{
return y < rhs.y;
}
}


It is more of a personal preference, but I generally prefer ternary operators in such situations:

bool operator<(const Point& rhs) const
{
return (x == rhs.x) ? y < rhs.y
: x < rhs.x;
}


Globals

Global constants are sometimes a necessary evil. But most certainly not here. Create a class and put matrix and friends as members in it.

Avoid one-liner

You have a lot of multi-line statements in a single line

    if (new_pos.x < 0 || new_pos.x > matrix.size() - 1) continue;
if (new_pos.y < 0 || new_pos.y > matrix[0].size() - 1) continue;


This is really bad practice that will haunt you later on. It takes so much more time to read code, when you cannot be sure whether something is a long conditional or already the body of the if/for/while.

Avoid copying everything

In your find_next_match(std::string input, Point cur_pos) function you are copying the string every time you call it. What is even worse, is that you copy it and then force a complete reshuffle of the memory via input.erase(0,1). This is completely unneeded. Just pass the string as a const reference and a size_t as the current position you are in the string.

Even better, when you refactor that into a class, you can make the string a member and omit it from the argument list.

Another way

Personally I find the solution rather boring. It is the same as a million other problems out there. For the sake of originality, I would propose to use a graph representation of the matrix to traverse it.

So every element of the matrix is a node with up to four edges, which connect it with its neighbors. Then you can simply traverse the the graph in a depth-first search to find the string.

Regarding EDIT2

I would definitely make the directions member a static member, so that you do not have to pass it to the constructor. It is never changing, so there is no need for it to be initialized by the constructor.

The index check should better be a greater-or-equal; this is clearer. Also you should return false, as the word was not found.

    if (index >= input.size())
{
return false;
}

• Putting aside the graph based approach for later I updated the current solution with your advice in mind. – yuri May 24 '17 at 12:18
• Alternative idiomatic approach to operator<, reducing the complexity, is to return std::tie(x,y) < std::tie(rhs.x, rhs.y);. – Toby Speight May 24 '17 at 15:04
• Also you should return false, as the word was not found. I'm unsure what you mean by this as that is literally the end condition. – yuri May 24 '17 at 22:55