Path trou the matrix

[duskoKoscica]

Well I have created this one and on my computer it is working. I would like to hear about some alternative solutions.
INTRODUCTION
This time I have one algorithm, but to understand it we need to consider a few terms. First of all, we should be familiar with the pangrams.
For example: “The quick brown fox jumps over lazy dog” is the famous one. The pangram has all letters of a particular alphabet.
Yes, there are perfect pangrams they have all the letters, but they don’t repeat more than once.
In this case we will use: “D. V. Pike flung J. Q. Schwartz my box“.

THE PROBLEM
In the matrix we have placed our perfect pangram each letter is surrounded with the next one. By surrounded I mean that each letter is on distance no further than one position: left, right, up, down or diagonally.
So, our aim is to find the path that starts at the beginning position and forms unbroken line toward the end.
The found path is the programs output.

Matrix:
* V I E *
D P K F L
X O B N U
Z M Y G J
T R W S Q
* A H C *

SOLUTION:
ANALYSIS:
In the solution, we start from the first letter, and then we search for the second one in surrounding of the first one, after we have found second letter we look for the third one and so on till we find all letters from the perfect pangram.
When I say surrounding, I mean that if the current location is (m, n), the next letter could be found at:
(m-1,n), (m+1,n), (m,n+1), (m,n-1), (m-1,n-1), (m+1, n-1), (m+1, n+1) or (m-1, n+1).
Because it is a perfect pangram, we can form continual line that fills the given matrix.

CODE:
We have two files, one is main.cpp and the other is Functions.h file. If you don’t like this approach you could create one file and run the program.

main.cpp

#include <iostream>

#include "Functions.h"

using namespace std;

int
main( void)


 cout<<MESSAGE_1<<endl;
 WritteMatrix(DIM_ROW,DIM_COL,cMatrix);

 cout<<MESSAGE_2<<endl;
 WritteArray(DIM_ROW*DIM_COL-4,cPerfectPangram); 
 cout<<endl;

 //FIND THE LETTER D
 int xStart=0, yStart=0;
 FindStart( xStart, yStart,
            DIM_ROW,DIM_COL,
            cMatrix);

 //FIND THE PATH
 int Koordinat[DIM_ROW*DIM_COL-4][2];
 Koordinat[0][0]=xStart; Koordinat[0][1]=yStart;
 FindThePath(DIM_ROW*DIM_COL-4,
         Koordinat,
         DIM_ROW*DIM_COL-4,
         cPerfectPangram,
             DIM_ROW, DIM_COL, 
         cMatrix,
         xStart, yStart);


    int p; cin>>p;
    return EXIT_SUCCESS;
}

Functions.h

#include <iostream>

#define DIM_ROW 6
#define DIM_COL 5
#define WORDS_TOTAL 26


#define MESSAGE_1 "In the matrix"
#define MESSAGE_2 "Looking for the sentence"

char cMatrix[DIM_ROW][DIM_COL]=
{{'*', 'V', 'I', 'E', '*'},
 {'D', 'P', 'K', 'F', 'L'},
 {'X', 'O', 'B', 'N', 'U'},
 {'Z', 'M', 'Y', 'G', 'J'},
 {'T', 'R', 'W', 'S', 'Q'},
 {'*', 'A', 'H', 'C', '*'}};

char cPerfectPangram[]={'D','V','P','I','K',
                        'E','F','L','U','N',
                    'G','J','Q','S','C',
            'H','W','A','R','T',
            'Z','M','Y','B',
                'O','X'};





void
WritteMatrix( int i, int j, 
          char cMatrix[DIM_ROW][DIM_COL])
{
for(int i=0; i<DIM_ROW; i++)
    {
        for(int j=0; j<DIM_COL; j++)
            std::cout<<cMatrix[i][j];
        std::cout<<std::endl;
    }
}

void
WritteArray( int n, char cNiz[])
{
    for(int i=0; i< n; std::cout<<cNiz[i++]<<" ");
}

void
FindStart(int& iX, int& iY, 
      int i, int j,
      char cMatrix[DIM_ROW][DIM_COL])
{
    for(i=0; i<DIM_ROW; i++)
        for(j=0; j<DIM_COL; j++)
        if( cMatrix[i][j]=='D') 
        {
            iX=i; iY=j; break;
        }
}

bool
OK( int i, int j)
{
    bool bResult=true;
    if((i<0)||(i>=6)) bResult =false;
    if((j<0)||(j>=5)) bResult =false;
    return bResult;
}

void
FindThePath(int iDimenzija ,
        int Koordinat[DIM_ROW*DIM_COL-4][2],
        int iPangram ,
        char cPerfektPangram[DIM_ROW*DIM_COL],
            int iRed,int iKol,
        char cMatrix[DIM_ROW][DIM_COL],
        int xStart,int yStart)
{
    for(int i=1; i< DIM_ROW*DIM_COL-4; i++)
    {
        char cTrazeni=cPerfektPangram[i];

        int x=xStart, y=yStart;
        if( OK(++x,++y)&&(cTrazeni == cMatrix[x][y]))
        {
            Koordinat[i][0]=x; ++xStart;
            Koordinat[i][1]=y; ++yStart;
            continue;
        }

        x=xStart, y=yStart;
        if(OK(--x,--y)&&( cTrazeni == cMatrix[x][y])) 
        {
            Koordinat[i][0]=x; --xStart;
            Koordinat[i][1]=y; --yStart;
            continue;
        }

        x=xStart, y=yStart;
        if(OK(++x,--y)&&(cTrazeni == cMatrix[x][y])) 
        {
            Koordinat[i][0]=x; ++xStart;
            Koordinat[i][1]=y; --yStart;
            continue;
        }

        x=xStart, y=yStart;
        if(OK(--x,++y)&&( cTrazeni == cMatrix[x][y])) 
        {
            Koordinat[i][0]=x; --xStart;
            Koordinat[i][1]=y; ++yStart;
            continue;
        }

        x=xStart, y=yStart;
        if( OK(--x,y)&&(cTrazeni == cMatrix[x][y])) 
        {
            Koordinat[i][0]=x; --xStart;
            Koordinat[i][1]=y;  
            continue;
        }

        x=xStart, y=yStart;
        if(OK(++x,y)&&(cTrazeni == cMatrix[x][y]))
        {
            Koordinat[i][0]=x; ++xStart;
            Koordinat[i][1]=y;
            continue;
        }

        x=xStart, y=yStart;
        if(OK(x,++y)&&(cTrazeni == cMatrix[x][y])) 
        {
            Koordinat[i][0]=x;
            Koordinat[i][1]=y; ++yStart;
            continue;
        }

        x=xStart, y=yStart;
        if( OK(x,--y)&&(cTrazeni == cMatrix[x][y]) )
        {
            Koordinat[i][0]=x;
            Koordinat[i][1]=y; --yStart;
            continue;
        }
    }

    std::cout<<"PATH IS"<<std::endl;
    for(int i=0; i< DIM_ROW*DIM_COL-4; i++)
        std::cout<<Koordinat[i][0]<<" "<<Koordinat[i][1]<<std::endl;
}

[Banfa]

The way you have written Functions.h is more than something I don't like. The moment you start creating projects with more than 1 cpp file this approach will cause you errors because you will have multiple definitions of all the functions you have put into your header. Headers should only contain declarations it should not contain definitions. A declaration indicates that something exists where as a definition causes something to be brought into existance.

Example

Function declaration

int add(int a, int b);

Function definition

int add(int a, int b)
{
  return a + b;
}

The declaration in a header file included into multiple cpp files will not be a problem, it only states that a function exists, although it would need to exist in one of the cpp files. Put the definition in the header and it exists in all translation units (cpp files) that the header is included into and when you try to link all those translation units together you will get multiple definition errors.

FindStart
Why are you calling this from main and not from FindThePath? The user just wants to find the path they do not want to perform unnecessary initialisation. This function can easily be called from FindThePath, it has all the data, reducing the user to a single function call. Additionally the user does not then need to declare xStart and yStart which they casically have no interest in and if they really need can get from the first entry of Koordinat.

You have hardcoded the initial letter to find in find start. This is unmaintainable, what if the sentance changes. You have to change the data of the sentance and this function when the first letter is readily available without hardcoding in the data for the sentance.

Finally in FindThePath there is repeated code and this seems to me to be a place that could be refactored into a function that is called multiple times rather than all this repeation.

[duskoKoscica]

Thanks for beeng interested.
And this is my respond to your coments>
1. This is just console app, I use that thing for OOP solutions like H.cpp + H.h files for class and its implementation. So, in this case I have just put it like that. But this is good question as well. I have not had intention to offend, anoy or what so ever, there is like more than 1 000 000 people at this site, it is statisticly inposlible to please everybody.

1. Well, the second one is very good. But it could be fixed easilly.

2. If yuo mean that I have not created the most flexible solution, well you are right at that. The matrix could change, the sentence could change to, and you could have more then one path of choice or the next element could be more far. For that thing I have flood a like algorithm, or the generations one.

3. Well the forth observation is the best, for that i have tought to create like two strings first_one x++ and the second_one and then to use it like [first_one][second_one], but did not make it. Also I have some other alternative solutions but this one, would really make my day!

[Banfa]

I am not offended, it is just that putting functions into a header is such an attrociously bad idea that you should avoid doing it in even the smallest project. Either put them in another cpp file if you intend to reuse them in another program or put them in your main.cpp.

[Schol-R-LEA]

duskoKoscica: I think you will find this post helpful in clarifying why you should avoid having function implementations in header files.

[duskoKoscica]

I did not say that I don't know how to use that thing, but the best part of Banfa post is the forth objection, it is how to create well this is the thing>

double
Add( double a, double b)
/
return a + b;
/

and
double
Substract( double a, double b)
/
return a-b;

As we could observe the difference is name of funciton and +/-.
It would be nice to do that thing more easy, you look like you repeat same code.
In another words yu create function in the string and then you run that function. I don't know how to fix that and it would be nit.

And that heder us it or not, well I can do that thing, I don't use it when it comes to OOP thing, but it would be nice to have like string table, you have it in Visual development apps.

[Banfa]

At anytime you think (while programming C++ (or C)) what would work here would be convert all my data to a string so I can interpret it you have made a design error. The computer handles binary data far better than string data the last thing you want to do is hold your data in strings if you can avoid it.

For the example you give with 2 small functions you are far better off using an if statement and then calling the right one of the 2 functions.

The refactoring I suggested in point 4 could be done with a function with the prototype of

int testMatrixCell(int x, int y,
        char cTrazeni,
        int (*Koordinat)[2],
        char cMatrixCellValue,
        int& xStart, int& yStart);

[duskoKoscica]

Nice, I was thinking about it earller, but I wanna take the string function from imput like
f(x) + g(x), and then just count the value of the x without analayzing the iput functins and...
And the thing I wish to do could be usefull about manny things.
And when you develop not so big app like photoshop or something less than that I would like to create like middle layer app generator, in witch you create UML like class, app and so on, instead of the wizard like we have it nowdays.