5
\$\begingroup\$

I've been working on this word search algorithm and had some issues about its speed. It kinda looks like it takes a little too much time.

If anyone could offer suggestions on making this better and improving my skills, that would be great.

    #include <iostream>
    #include <string>
    #include <fstream>

    using namespace std;

    bool Check(string Letter, string Matrix)
    {
        return (Letter == Matrix) ? true : false;

    }

    int main()
    {
        int Height = 0, Widht = 0, Numb = 0, Longer = 0, Look = 0, Look1 = 0, Look2 = 0, Look3 = 0, Poz = 0, Poz1 = 0;

        int Loop = 0, Loop1 = 0, Loop2 = 0, Loop3 = 0, Loop4 = 0, Loop5 = 0, Loop6 = 0;

        bool Found, Found1, Found2, Found3;

        ifstream Data("Files/Info.txt");

        Data >> Widht >> Height;

        string Matrix[Height][Widht];

        while(Loop < Height)
        {
            Loop1 = 0;

            while(Loop1 < Widht)
            {
                Data >> Matrix[Loop][Loop1];

                Loop1++;
            }

            Loop++;
        }

        Data >> Numb;

        string Words[Numb];

        while(Loop2 < Numb)
        {
            Data >> Words[Loop2];

            Loop2++;
        }

        Data.close();

        while(Loop3 < Numb)
        {
            Longer = Words[Loop3].size();
            Loop4 = 0;
            Loop6 = 0;

            cout << Words[Loop3] << endl;

            while(Loop4 < Height) // Looks horizantaly
            {
                Loop5 = 0;
                Look = 0;
                Look1 = 0;

                while(Loop5 < Widht - Longer + 1)
                {
                    Found = Check(Words[Loop3].substr(Look, 1), Matrix[Loop4][Loop5]);

                    if(Found)
                    {
                        Loop6 = 1;
                        Look = Loop5;
                        Poz = Loop4;
                        Poz1 = Loop5;

                        while(Loop6 < Longer)
                        {
                            Look++;

                            Found1 = Check(Words[Loop3].substr(Loop6, 1), Matrix[Loop4][Look]);

                            if(Found1)
                            {
                                Loop6++;
                            }
                            else
                            {
                                Loop5 += Loop6;
                                Loop6 = Longer + 1;
                            }
                        }
                    }

                    if(Loop6 == Longer)
                    {
                        cout << "Word " << Words[Loop3] << " was found at: " << Poz << " collumn " << Poz1 + 1 << " symbol. Horizontaly from right to left" << endl;
                        Loop5 = Widht;
                        Loop4 = Height;
                        Loop3++;
                    }

                    Loop5++;
                }

                Loop4++;
            }

            Loop3++;
        }

        return 0;
    }

The infos file looks like this:

10 10
a s d f g h j k l o
e t a k t r e e a d
t e d a w e f g d a
r e s a g a f a q w
d c s q a z x v n b
q w e t a s f w p s
w a r y i w t o o a
s b b d s s w q o k
w e r a d g d a p a
q w r c b a x l s k
3
tree
poop
test

Of course, I will later add other directions in which words might be written.

\$\endgroup\$
  • \$\begingroup\$ took me like 5 seconds to find all the words.... \$\endgroup\$ – Malachi Dec 27 '13 at 21:14
  • \$\begingroup\$ Yeah this is old code, now i have improved one which can work up with matrix of 40000 * 40000 or 1,6 billion letters \$\endgroup\$ – iCoRe Jan 1 '14 at 14:56
  • \$\begingroup\$ Why don't you use for loops? they much more easy to write and read. I was just lost in your loops for input. \$\endgroup\$ – FazeL Nov 6 '15 at 10:27
  • \$\begingroup\$ What you are trying to do, is very similar to this. there is a nice implementation here I think it is not the same, but you can use it very much. \$\endgroup\$ – FazeL Nov 6 '15 at 12:24
  • \$\begingroup\$ I think one thing to fuel your performance would be change the string matrix[][] to char matrix[][]. \$\endgroup\$ – FazeL Nov 6 '15 at 12:26
4
\$\begingroup\$
  • widht is misspelled; it should be width. :-)

  • Some generalities regarding naming convention:

    Variables and functions should start with a lowercase letter:

    // "camel case"
    int camelCaseVariable;
    void camelCaseFunction() {}
    

    // "snake case"
    int snake_case_variable;
    void snake_case_function() {}
    

    Custom types should start with a capital letter:

    class Class;
    

    Macros should be uppercase:

    #define MACRO 0
    
  • Check()'s body can be simplified as such:

    return Letter == Matrix; // already returns true or false
    

    Its parameters should also be passed by constant reference since they're not being modified:

    bool Check(string const& Letter, string const& Matrix) {}
    
  • You should make sure the input file is open before proceeding. If not, terminate from main() by returning 1 or EXIT_FAILURE.

  • You could vastly improve readability by using more functions. Putting everything in main() is not always a good idea, especially with a lot of nesting. Define the functions to perform one important task, and call them in main() or wherever else as needed. Function call overhead shouldn't hurt you here, making the readability aspect more important.

    In its current state, more comments may help others follow the code. That, in turn, could help flesh out any optimization issues. However, this isn't a substitute for writing readable code.

\$\endgroup\$
3
\$\begingroup\$

Code style

  1. As you are writing C++ there is no need to declare all local variables at the beginning of a block. Declare them where they are needed.

  2. Give your loop counters sensible names. Single letter loop counters are accepted practice but sometimes it makes it easier to read to provide some more descriptive name.

  3. There is no value in using while loops everywhere. In some places for loops would be much cleaner to read, especially since they allow you to declare the loop counter in place. I found it very hard to discern all the loop variables to see if they are being used later on for some reason. So your first while loop in main could be rewritten as:

    for (int y = 0; y < Height; y++)
    {
        for (int x = 0; x < Width; x++)
        {
            Data >> Matrix[y][x];
        }
    }
    

    This clearly limits the scope of the loop counter to the loop so anyone reading the code doesn't have to check if the variables might be used further down. It also states the invariants of the loop all in one place. I choose x and y because using x and y to denote coordinates in a 2d structure is fairly common in the programming world. For other loops different names will make more sense.

    Same goes for the outer while loop which loops over all words. The inner while loops are ok since you are skipping some parts but still the loop counters should be renamed to something more suitable.

  4. Also your other variables could use more descriptive names. For example

    • Numb should be wordCount
    • Longer should be wordLength
  5. As Jamal said: standard naming convention for local variables and methods is camelCase, classes are PascalCase.

  6. Do not use an array to hold a bunch of loop counters. See above for recommendations for loops.

\$\endgroup\$
  • \$\begingroup\$ +1 good stuff. Honestly, I couldn't follow the code well enough to determine that an array is a bad idea here. When I see so many like-variables like that, an array first comes to mind. Normally I wouldn't recommend such a thing. :-) I really wish I knew how this code could be refactored. \$\endgroup\$ – Jamal Nov 4 '13 at 8:44
  • \$\begingroup\$ Thanks it's useful, but I still think that while loops are more comfortable to use. \$\endgroup\$ – iCoRe Nov 4 '13 at 18:07
1
\$\begingroup\$

For arrays whose size can be determined at compile time, such as Loop and Possible, prefer the use of std::array which will be safer for bounds checking and will not degenerate into a pointer when passed to another function. (std::array is only available with C++11)

For arrays whose size cannot be determined at compile time, such as Matrix and the members of Matrix, prefer to use std::vector which will take care of the memory allocations for you, and allow you more flexibility in your code.

You can still use the bracket [] syntax with std::array and std::vector so only minimal changes to the above code should be required for implementation, but it is safer to use std::vector::at so that vector can perform bounds checking for you (it will throw an exception if you attempt to access an element outside of the bounds of the vector instead of simply giving you access to raw memory.)

\$\endgroup\$

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.