5 replies to this topic

[wiwbiz]

Here is a snippet of a function code :

void ch(char *a,char *b,int i,int j,char *p)
{
    if(j==strlen(b)-1)sum++;
    while(j<strlen(b)-1)
        {
            int n=strlen(b);
            p+=i;j++;
            //printf("%s %d\n",p,j);
            if(*(p+1)==b[j]){i=1;ch(a,b,i,j,p);}
            if(*(p-1)==b[j]){i=-1;ch(a,b,i,j,p);}
            if(*(p+n)==b[j]){i=n;ch(a,b,i,j,p);}
            if(*(p-n)==b[j]){i=-n;ch(a,b,i,j,p);}
            if(*(p+n+1)==b[j]){i=n+1;ch(a,b,i,j,p);}
            if(*(p+n-1)==b[j]){i=n-1;ch(a,b,i,j,p);}
            if(*(p-n+1)==b[j]){i=1-n;ch(a,b,i,j,p);}
            if(*(p-n-1)==b[j]){i=-n-1;ch(a,b,i,j,p);}
            //else return 0;
        }
        
        //return sum;
}

there are 2 arrays a,b and elements of b are compared with the that of a at logical positions. The problem is it gives double of the expected value. Seems like a small bug but can't figure it out.

[dcs]

As always, a smallish but complete and compilable snippet will always get you answers faster than a mere stray snippet. If anyone else attempts to reproduce the issue you are dealing with, you are handicapping us by withholding information.

[wiwbiz]

Here's the code which I used for searching a string [any length] in a [nxn] 2D array, where the string letters can be located at the adjacent by sharing edge or at diagonal positions. It's working fine but wrong answers for n=2 and 1. Any additional detail for optimizing the code is appreciated.

#include<cstdio>
#include<iostream>

#define s(n) scanf("%d",&n)
#define c(n) scanf("%s",&n)
#define f(i,n) for(int i=0;i<n;i++)

int sum=0;
int n;
////////////////////////////////////////////////*
  p is pointer to an element in array 'a' matching 'j'th character of string 'b'
  'i' is the spaces between elements in 'a' matching subsequent characters in string 'b'

   [U]Sample running for n=3;[/U]

            2D array 'a': 
                             xax
                             bax
                             xax

                    'b':      aba

            Output:          9
*/////////////////////////////////

void ch(char *a,char *b,int i,int j,char *p)
{
    if(j==strlen(b)-1)sum++;     //  j reaching end of 'b'
    else if(j<strlen(b)-1)
        {     
            p+=i;j++;      
            if(*(p+n)==b[j]){i=n;ch(a,b,i,j,p);}
            if(*(p-n)==b[j]){i=-n;ch(a,b,i,j,p);}      

                    if((p-a)%n!=n-1 || n<=2)   //checking for character located at end of row
                        {
                            if(*(p+1)==b[j]){i=1;ch(a,b,i,j,p);}
                            if(*(p+n+1)==b[j]){i=n+1;ch(a,b,i,j,p);}
                            if(*(p-n+1)==b[j]){i=1-n;ch(a,b,i,j,p);}
                        }
                        
                    if((p-a)%n!=0 || n<=2) // checking characters at start of row
                        {
                            if(*(p-1)==b[j]){i=-1;ch(a,b,i,j,p);}
                            if(*(p+n-1)==b[j]){i=n-1;ch(a,b,i,j,p);}
                            if(*(p-n-1)==b[j]){i=-n-1;ch(a,b,i,j,p);}
                        } 
        }
}

int main()
{
    s(n);
    char a[n*n],b[n],*p;
    f(i,n)
    {
        c(b);            
        strcat(a,b);       // concatenating string b to string a
    }p=a;
    c(b);                      // The string to be searched.
    f(i,n*n)
    {        
        if(a[i]==b[0])ch(a,b,i,0,p);
    }printf("%d",sum);
    getchar();
    getchar();
}

Edited by wiwbiz, 28 January 2010 - 08:28 AM.

[bobdark]

I personally couldn't understand whats going on there.
Please post: (basically you should rewrite the code while writing comments explaining your actions - for example pointer arithmetic that you're doing there isn't trivial at all, and giving meaningful names to variables, functions, macros etc. Also don't put more than one command in a line, it doesn't make your code more readable)
1)what is the program supposed to do
2)what is the the 'ch' function supposed to do and by how it supposedly does it
3)what are all the variables in main function and 'ch' function supposed to represent (as I said before, they should be named in such way that their purpose can be understood just from the name. Same goes for functions)

This will enable others to understand what you wrote and help you much faster

[wiwbiz]

Ok I found the bug and amend code. But I'd still like to know if some better approach is there for solving 2D array problems. I was thinking of using map or something but nothing more struck to me.

Edited by wiwbiz, 28 January 2010 - 08:21 AM.

[dcs]

I would very highly recommend avoiding this like the plague:

#define s(n) scanf("%d",&n)
#define c(n) scanf("%s",&n)
#define f(i,n) for(int i=0;i<n;i++)