current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 2 down vote favorite

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;
    }

EDITED CODE

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

    using namespace std;

                                        //Loop[4] //Loop[5]
    int * Possibles(int Widht, int Height, int Poz, int Poz1, int Leng, int * Possible)
    {
        if(Poz1 < Widht - Leng + 1) // To right
        {
            Possible[0] = 1;
        }

        if(Poz1 >= Leng - 1) // To left
        {
            Possible[1] = 1;
        }

        if(Poz <= Height - Leng) // From top to bottom
        {
            Possible[2] = 1;
        }

        if(Poz >= Leng) // From bottom to top
        {
            Possible[3] = 1;
        }

        return Possible;
    }

    int * Zero(int * Possible)
    {
            Possible[0] = 0;
            Possible[1] = 0;
            Possible[2] = 0;
            Possible[3] = 0;

            return Possible;
    }

    string Next(string ** Matrix, int Height, int Widht)
    {
        return Matrix[Height][Widht];
    }

    bool Find(string Word, int Poz, int Poz1, int Look, string Have, string ** Matrix)
    {

        if(Have == Word)
        {
            return true;
        }

        if(Word.substr(Look,1) == Next(Matrix, Poz, Poz1))
        {
            Have += Word.substr(Look,1);

            return Find(Word, Poz, Poz1 + 1, Look + 1, Have, Matrix);
        }

        return false;
    }

    int main()
    {
        int Height = 0, Widht = 0, Numb = 0;

        int Loop[] = {0, 0, 0, 0, 0, 0, 0};

        int * Possible = new int[4];

        string Search;

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

        Data >> Widht >> Height;

        string ** Matrix = new string*[Height];

        for(int i = 0; i < Widht; ++i)
        {
            Matrix[i] = new string[Widht];
        }

        while(Loop[0] < Height)
        {
            Loop[1] = 0;

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

                Loop[1]++;
            }

            Loop[0]++;
        }

        Data >> Numb;

        string Words[Numb];

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

            Loop[2]++;
        }

        Data.close();

        while(Loop[3] < Numb)
        {
            Search = Words[Loop[3]].substr(0, 1);
            Loop[4] = 0;

            while(Loop[4] < Height)
            {
                Loop[5] = 0;

                while(Loop[5] < Widht)
                {
                    if(Matrix[Loop[4]][Loop[5]] == Search)
                    {
                        Zero(Possible);
                        Possibles(Widht, Height, Loop[4], Loop[5], Words[Loop[3]].size(), Possible);

                        if(Possible[0] == 1)
                        {
                            if(Find(Words[Loop[3]], Loop[4], Loop[5] + 1, 1, Search, Matrix))
                            {
                                cout << "Stupid word found !!!!!!!!! " << Words[Loop[3]] << endl;
                            }
                        }
                        cout << Possible[0] << " " << Possible[1] << " " << Possible[2] << " " << Possible[3] << " " << Next(Matrix, Loop[4], Loop[5]) << endl;
                    }

                    Loop[5]++;
                }

                Loop[4]++;
            }

            Loop[3]++;
        }

        for(int i1 = 0; i1 < Widht; ++i1)
        {
            delete [] Matrix[i1];
        }

        delete [] Matrix;
        delete [] Possible;

        return 0;
    }

And 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.

I've improved the code by your suggestions. Can you suggest anything about its speed?

share|improve this question
 
took me like 5 seconds to find all the words.... –  Malachi Dec 27 '13 at 21:14
 
Yeah this is old code, now i have improved one which can work up with matrix of 40000 * 40000 or 1,6 billion letters –  iCoRe Jan 1 at 14:56
add comment

3 Answers

up vote 2 down vote

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.

share|improve this answer
 
+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. –  Jamal♦ Nov 4 '13 at 8:44
 
Thanks it's useful, but I still think that while loops are more comfortable to use. –  iCoRe Nov 4 '13 at 18:07
add comment
up vote 2 down vote

  • 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.

share|improve this answer
 
Thanks for tips :) –  iCoRe Nov 2 '13 at 6:55
 
@iCoRe: You're welcome. I hope it was helpful enough, even though I didn't address anything pertaining to speed. You're welcome to make some changes and post that code below the original. –  Jamal♦ Nov 2 '13 at 8:00
 
K, I'm making changes now. And about speed, do you have any suggestions? –  iCoRe Nov 2 '13 at 10:42
 
@iCoRe: I'll take another look at it, though I'm not the best with algorithms. Someone else may come along and offer suggestions. –  Jamal♦ Nov 2 '13 at 17:11
 
K, thanks. But thats the problem, nobody else have offered a thing :D –  iCoRe Nov 2 '13 at 19:34
show 6 more comments
up vote 1 down vote

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.)

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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