what is wrong with this code ? hi-q

Discussion in 'C Programming' started by Niklaus, Jun 2, 2004.

  1. Niklaus

    Niklaus Guest

    Hi,
    Can someone point out what is wrong with this code ? How can i make
    it better optimize it. When run it gives me seg fault in linux. But
    windows it works fine(runs for a long time).

    Do we have something like stack size growing enormously and then
    saying you can't access ,so a segfault ?

    It would be helpful if someone can run the code and give me the
    output. It takes a long time on my PC.

    Please give me comments about how to code better . This is just a hi-q
    problem solved using brute force approach.

    Here is the code.
    ------------BEGIN--------------------
    #include<stdio.h>
    #define SIZE 7
    int a[SIZE][SIZE];
    #define NOTVALID -1
    #define HOLE 8
    #define COIN 9
    #define TRUE 1
    #define FALSE 0

    void
    print_array (void)
    {
    int i, j;
    for (i = 0; i < SIZE; i++)
    {
    printf ("\n");
    for (j = 0; j < SIZE; j++)
    printf (" %2c",
    (a[j] == NOTVALID ? 32 : (a[j] == HOLE ? 48 : 49)));
    }
    printf ("\n#########################\n");
    }

    void
    initialize (void)
    {
    int i, j;
    for (i = 0; i < SIZE; i++)
    for (j = 0; j < SIZE; j++)
    a[j] = NOTVALID;

    for (i = 2; i < 5; i++)
    for (j = 0; j < SIZE; j++)
    a[j] = COIN;
    for (i = 0; i < SIZE; i++)
    for (j = 2; j < 5; j++)
    a[j] = COIN;
    a[3][3] = HOLE;
    }

    int
    within_l (int m, int n)
    {
    if (m < 0 || m > (SIZE - 1) || n < 0 || n > (SIZE - 1))
    return FALSE;
    if (a[m][n] == NOTVALID)
    return FALSE;
    return TRUE;
    }

    /* if i,j is a hole */
    int
    validposition1 (int i, int j)
    {
    if (within_l (i - 2, j) && (a[i - 1][j] == COIN) && a[i-2][j] ==
    COIN )
    return TRUE;
    return FALSE;
    }

    int
    validposition2 (int i, int j)
    {
    if (within_l (i + 2, j) && (a[i + 1][j] == COIN) && a[i+2][j] ==
    COIN )
    return TRUE;
    return FALSE;
    }

    int
    validposition3 (int i, int j)
    {
    if (within_l (i, j - 2) && (a[j - 1] == COIN) && a[j-2] ==
    COIN )
    return TRUE;
    return FALSE;
    }

    int
    validposition4 (int i, int j)
    {
    if (within_l (i, j + 2) && (a[j + 1] == COIN) && a[j+2] ==
    COIN )
    return TRUE;
    return FALSE;
    }

    int isonlythat(void)
    {
    int i,j;
    for(i=0;i<SIZE;i++)
    for(j=0;j<SIZE;j++)
    if(a[j] == COIN && (i!=3 ||j!=3))
    return FALSE;


    if(a[3][3] == HOLE)
    return FALSE;


    return TRUE;
    }



    void
    hiq (int p, int q, int count)
    {
    int flag = 0, i, j, tmp;
    // print_array();
    if (validposition1 (p, q))
    {
    flag = 1;
    a[p][q] = COIN;
    a[p - 1][q] = HOLE;
    a[p - 2][q] = HOLE;
    hiq (p - 2, q, count + 1);
    hiq (p - 1, q, count + 1);
    a[p][q] = HOLE;
    a[p - 1][q] = COIN;
    a[p - 2][q] = COIN;
    }

    if (validposition2 (p, q))
    {
    flag = 1;
    a[p][q] = COIN;
    a[p + 1][q] = HOLE;
    a[p + 2][q] = HOLE;
    hiq (p + 2, q, count + 1);
    hiq (p + 1, q, count + 1);
    a[p][q] = HOLE;
    a[p + 1][q] = COIN;
    a[p + 2][q] = COIN;
    }

    if (validposition3 (p, q))
    {
    flag = 1;
    a[p][q] = COIN;
    a[p][q - 1] = HOLE;
    a[p][q - 2] = HOLE;
    hiq (p, q - 2, count + 1);
    hiq (p, q - 1, count + 1);
    a[p][q] = HOLE;
    a[p][q - 1] = COIN;
    a[p][q - 2] = COIN;
    }

    if (validposition4 (p, q))
    {
    flag = 1;
    a[p][q] = COIN;
    a[p][q + 1] = HOLE;
    a[p + 2][q + 2] = HOLE;
    hiq (p, q + 2, count + 1);
    hiq (p, q + 1, count + 1);
    a[p][q] = HOLE;
    a[p][q + 1] = COIN;
    a[p][q + 2] = COIN;
    }


    if (flag == 0)
    {
    tmp = 0;

    for (i = 0; i < SIZE; i++)
    for (j = 0; j < SIZE; j++)
    if (a[j] == HOLE)
    {
    if (validposition1 (i, j) || validposition2 (i, j)
    || validposition3 (i, j) || validposition4 (i, j))
    {
    tmp = 1;
    hiq (i, j, count + 1);
    }
    }

    if (tmp == 0 )
    {
    if(isonlythat())
    print_array ();
    else
    return;
    }
    else
    return;
    }

    }

    int
    main ()
    {
    initialize ();
    print_array ();
    hiq (3, 3, 0);
    return 0;
    }

    ---------------------END--------------------
     
    Niklaus, Jun 2, 2004
    #1
    1. Advertising

  2. On Wed, 2 Jun 2004, Niklaus wrote:

    > Hi,
    > Can someone point out what is wrong with this code ? How can i make
    > it better optimize it. When run it gives me seg fault in linux. But
    > windows it works fine(runs for a long time).


    I hear this a lot from students. They learn to program C over the summer
    between highschool and university. They trying using code they created on
    Windows on our Solaris or Linux machines and it seg faults.

    Most the time the code has undefined behaviour. On the Windows machine it
    works. On the Unix machine it does not. Undefined behaviour means that
    anything can happen. Other times the code is actually corrupting memory.
    The Windows machine is happy to let you write to memory you shouldn't be.
    The Linux machine will seg fault.

    > Do we have something like stack size growing enormously and then
    > saying you can't access ,so a segfault ?


    First, an implementation doesn't necessarily have a stack. Even if it did,
    the behaviour would be dependant on the OS and compiler. If a stack
    overflow does happen it is more likely that the overflowing data is
    corrupting program code. Once execution reaches the corrupted program code
    you get a seg fault.

    > It would be helpful if someone can run the code and give me the
    > output. It takes a long time on my PC.


    You might want to hang out in a newsgroup that uses your compiler and OS
    or in comp.programming. Learning how to debug these problems would be
    good. An old proverb goes:

    Give a man a fish and he is fed for a day.
    Teach a man to fish and he is fed for life.

    Don't ask people to debug your code for you; ask people to teach you how
    to debug your code.

    > Please give me comments about how to code better . This is just a hi-q
    > problem solved using brute force approach.
    >
    > Here is the code.
    > ------------BEGIN--------------------
    > #include<stdio.h>
    > #define SIZE 7
    > int a[SIZE][SIZE];


    Global variables make debugging harder. You should try to design without
    using global variables.

    > #define NOTVALID -1
    > #define HOLE 8
    > #define COIN 9
    > #define TRUE 1
    > #define FALSE 0
    >
    > void
    > print_array (void)
    > {
    > int i, j;
    > for (i = 0; i < SIZE; i++)
    > {
    > printf ("\n");
    > for (j = 0; j < SIZE; j++)
    > printf (" %2c",
    > (a[j] == NOTVALID ? 32 : (a[j] == HOLE ? 48 : 49)));
    > }


    This is called 'magic numbers'. I've been coding long enough to know that
    you are assuming an ASCII system. The 32 will print a space, the 48 will
    print a zero and the 49 will print a one. Try using:

    (a[j] == NOTVALID ? ' ' : (a[j] == HOLE ? '0' : '1'))

    This is just good coding practice. It will not fix your seg fault problem.

    > printf ("\n#########################\n");
    > }


    The for loops did not access an array out of bounds so this code seems
    fine to me.

    > void
    > initialize (void)
    > {
    > int i, j;
    > for (i = 0; i < SIZE; i++)
    > for (j = 0; j < SIZE; j++)
    > a[j] = NOTVALID;


    These are all valid ranges for the array a so no seg fault here.

    > for (i = 2; i < 5; i++)
    > for (j = 0; j < SIZE; j++)
    > a[j] = COIN;


    A little whitespace would be nice. Why the magic numbers for the outer
    loop? If I scroll back up I can see that the array has the range of 0 to
    6. Thus setting i from 2 to 4 is fine. What if I change the value of SIZE
    to something smaller then 5? This could be a problem.

    Additionally, if you know you are going to be changing the values of
    a[2][0] to a[4][SIZE-1], why initialize them with NOTVALID? I'd write it
    as one double for loop or something that initialized the first bit as
    NOTVALID, drops to the second double for loop but has the second loop
    start where the last left off, i.e.

    for(i = 0; i < 2; i++)
    for(j = 0; j < SIZE; j++)
    a[j] = NOTVALID;

    for( ; i < 5; i++)
    for(j = 0; j < SIZE; j++)
    a[j] = COIN;

    Mind you, if you are looking to improve performance, initialize is
    probably call once. Look to improving code that is called many times.

    > for (i = 0; i < SIZE; i++)
    > for (j = 2; j < 5; j++)
    > a[j] = COIN;
    > a[3][3] = HOLE;
    > }
    >
    > int
    > within_l (int m, int n)
    > {
    > if (m < 0 || m > (SIZE - 1) || n < 0 || n > (SIZE - 1))
    > return FALSE;


    Good check. Guarantees you will not access outside the array bounds.

    > if (a[m][n] == NOTVALID)
    > return FALSE;
    > return TRUE;
    > }
    >
    > /* if i,j is a hole */
    > int
    > validposition1 (int i, int j)
    > {
    > if (within_l (i - 2, j) && (a[i - 1][j] == COIN) && a[i-2][j] ==
    > COIN )
    > return TRUE;
    > return FALSE;
    > }


    What if i == 0? Then you will be accessing a[-1][j]. Or if i == 1 and
    a[0][j] == COIN it will evaluate a[i-2][j] or a[-1][j]. This is a
    potential spot for a seg fault. If debugging, this is a good spot for a
    breakpoint and variable watch of i. With no guards, you can also call this
    function with bad values of j and get a seg fault.

    > int
    > validposition2 (int i, int j)
    > {
    > if (within_l (i + 2, j) && (a[i + 1][j] == COIN) && a[i+2][j] ==
    > COIN )
    > return TRUE;
    > return FALSE;
    > }


    Same sort of thing as the previous function but this time you want to look
    for i+1 and i+2 greater than SIZE-1.

    > int
    > validposition3 (int i, int j)
    > {
    > if (within_l (i, j - 2) && (a[j - 1] == COIN) && a[j-2] ==
    > COIN )
    > return TRUE;
    > return FALSE;
    > }


    More of the same thing.

    > int
    > validposition4 (int i, int j)
    > {
    > if (within_l (i, j + 2) && (a[j + 1] == COIN) && a[j+2] ==
    > COIN )
    > return TRUE;
    > return FALSE;
    > }


    More of the same thing.

    > int isonlythat(void)
    > {
    > int i,j;
    > for(i=0;i<SIZE;i++)
    > for(j=0;j<SIZE;j++)
    > if(a[j] == COIN && (i!=3 ||j!=3))
    > return FALSE;
    >
    >
    > if(a[3][3] == HOLE)
    > return FALSE;
    >
    > return TRUE;
    > }
    >
    > void
    > hiq (int p, int q, int count)
    > {
    > int flag = 0, i, j, tmp;
    > // print_array();
    > if (validposition1 (p, q))
    > {
    > flag = 1;
    > a[p][q] = COIN;
    > a[p - 1][q] = HOLE;
    > a[p - 2][q] = HOLE;


    What values does p take on? This is potential for array out of bounds.

    > hiq (p - 2, q, count + 1);
    > hiq (p - 1, q, count + 1);
    > a[p][q] = HOLE;
    > a[p - 1][q] = COIN;
    > a[p - 2][q] = COIN;
    > }
    >
    > if (validposition2 (p, q))
    > {
    > flag = 1;
    > a[p][q] = COIN;
    > a[p + 1][q] = HOLE;
    > a[p + 2][q] = HOLE;
    > hiq (p + 2, q, count + 1);
    > hiq (p + 1, q, count + 1);
    > a[p][q] = HOLE;
    > a[p + 1][q] = COIN;
    > a[p + 2][q] = COIN;
    > }
    >
    > if (validposition3 (p, q))
    > {
    > flag = 1;
    > a[p][q] = COIN;
    > a[p][q - 1] = HOLE;
    > a[p][q - 2] = HOLE;
    > hiq (p, q - 2, count + 1);
    > hiq (p, q - 1, count + 1);
    > a[p][q] = HOLE;
    > a[p][q - 1] = COIN;
    > a[p][q - 2] = COIN;
    > }
    >
    > if (validposition4 (p, q))
    > {
    > flag = 1;
    > a[p][q] = COIN;
    > a[p][q + 1] = HOLE;
    > a[p + 2][q + 2] = HOLE;
    > hiq (p, q + 2, count + 1);
    > hiq (p, q + 1, count + 1);
    > a[p][q] = HOLE;
    > a[p][q + 1] = COIN;
    > a[p][q + 2] = COIN;
    > }


    All this index-1, index-2, index+1 and index+2 instances are places for an
    array out of bounds. Step through your code and see where they go out of
    bounds.

    > if (flag == 0)
    > {
    > tmp = 0;
    >
    > for (i = 0; i < SIZE; i++)
    > for (j = 0; j < SIZE; j++)
    > if (a[j] == HOLE)
    > {
    > if (validposition1 (i, j) || validposition2 (i, j)
    > || validposition3 (i, j) || validposition4 (i, j))
    > {
    > tmp = 1;
    > hiq (i, j, count + 1);
    > }
    > }
    >
    > if (tmp == 0 )
    > {
    > if(isonlythat())
    > print_array ();
    > else
    > return;
    > }
    > else
    > return;
    > }
    >
    > }
    >
    > int
    > main ()
    > {
    > initialize ();
    > print_array ();
    > hiq (3, 3, 0);
    > return 0;
    > }
    >
    > ---------------------END--------------------
    >


    --
    Send e-mail to: darrell at cs dot toronto dot edu
    Don't send e-mail to
     
    Darrell Grainger, Jun 2, 2004
    #2
    1. Advertising

  3. Niklaus

    I. Appel Guest

    > On Wed, 2 Jun 2004, Niklaus wrote:

    > > int
    > > within_l (int m, int n)
    > > {
    > > if (m < 0 || m > (SIZE - 1) || n < 0 || n > (SIZE - 1))
    > > return FALSE;

    >
    > Good check. Guarantees you will not access outside the array bounds.
    >


    > > if (within_l (i - 2, j) && (a[i - 1][j] == COIN) && a[i-2][j] ==
    > > COIN )
    > > return TRUE;
    > > return FALSE;
    > > }

    >
    > What if i == 0? Then you will be accessing a[-1][j]. Or if i == 1 and
    > a[0][j] == COIN it will evaluate a[i-2][j] or a[-1][j]. This is a
    > potential spot for a seg fault. If debugging, this is a good spot for a
    > breakpoint and variable watch of i. With no guards, you can also call this
    > function with bad values of j and get a seg fault.


    That stuff is checked in within_l, so seg fault is somewhere else.
    The only thing I dislike in this function is parens around first
    comparation,
    while there none around second one.

    Ivan.
     
    I. Appel, Jun 2, 2004
    #3
  4. On 2 Jun 2004 04:37:56 -0700, (Niklaus) wrote:

    >Hi,
    > Can someone point out what is wrong with this code ? How can i make
    >it better optimize it. When run it gives me seg fault in linux. But
    >windows it works fine(runs for a long time).


    Give us a fighting chance. Tell us where it fails.

    >
    >Do we have something like stack size growing enormously and then
    >saying you can't access ,so a segfault ?


    Since hiq is called recursively, this is possible.

    >
    >It would be helpful if someone can run the code and give me the
    >output. It takes a long time on my PC.
    >
    >Please give me comments about how to code better . This is just a hi-q
    >problem solved using brute force approach.
    >
    >Here is the code.
    >------------BEGIN--------------------
    >#include<stdio.h>
    >#define SIZE 7
    >int a[SIZE][SIZE];
    >#define NOTVALID -1
    >#define HOLE 8
    >#define COIN 9
    >#define TRUE 1
    >#define FALSE 0
    >
    >void
    >print_array (void)
    >{
    > int i, j;
    > for (i = 0; i < SIZE; i++)
    > {
    > printf ("\n");
    > for (j = 0; j < SIZE; j++)
    > printf (" %2c",
    > (a[j] == NOTVALID ? 32 : (a[j] == HOLE ? 48 : 49)));


    What are 32, 48, and 49? They are not valid characters on my system.
    If you mean blank, 0, and 1, then use the appropriate character
    constants ' ', '0', and '1'.

    > }
    > printf ("\n#########################\n");
    >}
    >
    >void
    >initialize (void)
    >{
    > int i, j;
    > for (i = 0; i < SIZE; i++)
    > for (j = 0; j < SIZE; j++)
    > a[j] = NOTVALID;
    >
    > for (i = 2; i < 5; i++)
    > for (j = 0; j < SIZE; j++)
    > a[j] = COIN;
    > for (i = 0; i < SIZE; i++)
    > for (j = 2; j < 5; j++)
    > a[j] = COIN;
    > a[3][3] = HOLE;
    >}
    >
    >int
    >within_l (int m, int n)
    >{
    > if (m < 0 || m > (SIZE - 1) || n < 0 || n > (SIZE - 1))
    > return FALSE;
    > if (a[m][n] == NOTVALID)
    > return FALSE;
    > return TRUE;
    >}
    >
    >/* if i,j is a hole */
    >int
    >validposition1 (int i, int j)
    >{
    > if (within_l (i - 2, j) && (a[i - 1][j] == COIN) && a[i-2][j] ==
    >COIN )
    > return TRUE;
    > return FALSE;
    >}
    >
    >int
    >validposition2 (int i, int j)
    >{
    > if (within_l (i + 2, j) && (a[i + 1][j] == COIN) && a[i+2][j] ==
    >COIN )
    > return TRUE;
    > return FALSE;
    >}
    >
    >int
    >validposition3 (int i, int j)
    >{
    > if (within_l (i, j - 2) && (a[j - 1] == COIN) && a[j-2] ==
    >COIN )
    > return TRUE;
    > return FALSE;
    >}
    >
    >int
    >validposition4 (int i, int j)
    >{
    > if (within_l (i, j + 2) && (a[j + 1] == COIN) && a[j+2] ==
    >COIN )
    > return TRUE;
    > return FALSE;
    >}
    >
    >int isonlythat(void)
    >{
    > int i,j;
    > for(i=0;i<SIZE;i++)
    > for(j=0;j<SIZE;j++)
    > if(a[j] == COIN && (i!=3 ||j!=3))
    > return FALSE;


    You code uses both tabs and spaces for indenting, sometimes both on
    the same line. This really screws it up for people trying to help.
    Posted message should use only spaces. And while you are at it, learn
    to indent consistently.

    >
    >
    > if(a[3][3] == HOLE)
    > return FALSE;
    >
    >
    > return TRUE;
    >}
    >
    >
    >
    >void
    >hiq (int p, int q, int count)


    In my test, I uncommented the call to print_array and saw hiq being
    called with (3,3,0), (1,3,1), (2,3,2), (4,3,3), 6,3,4), (3,3,5),
    (3,1,6), (1,3,7), (3,3,8), and (5,3,9). At this point, print_array
    generated
    1 1 1
    1 1 1
    1 1 1 0 1 1 1
    1 0 0 1 0 1 1
    1 1 1 1 1 1 1
    1 0 1 0
    1 0 1

    It is obvious that the last 0 on line 6 is wrong. Maybe this will
    help you spot the error.

    The next set of calls were (2,3,10), (0,3,11), (1,3,12), (3,3,13),
    (2,3,14), (2,1,15), (0,3,16), (2,3,17), (2,5,18), (2,2,19), and
    (0,2,20). At this point, print_array produced
    0 1 1
    0 0 1
    1 0 1 1 0 1 1
    1 0 0 0 0 1 1
    1 1 1 1 1 0 1
    1 0 1 0
    1 0 1

    The next call was (0,4,21) and print_array produced
    1 0 1
    0 0 1
    1 0 1 1 0 1 1
    1 0 0 0 0 1 1
    1 1 1 1 1 0 1
    1 0 1 0
    1 0 1

    This is an illegal move in the game. The top row should be 1 0 0.
    Maybe this will help you some.

    >{
    > int flag = 0, i, j, tmp;
    >// print_array();
    > if (validposition1 (p, q))
    > {
    > flag = 1;
    > a[p][q] = COIN;
    > a[p - 1][q] = HOLE;
    > a[p - 2][q] = HOLE;
    > hiq (p - 2, q, count + 1);
    > hiq (p - 1, q, count + 1);
    > a[p][q] = HOLE;
    > a[p - 1][q] = COIN;
    > a[p - 2][q] = COIN;
    > }
    >
    > if (validposition2 (p, q))
    > {
    > flag = 1;
    > a[p][q] = COIN;
    > a[p + 1][q] = HOLE;
    > a[p + 2][q] = HOLE;
    > hiq (p + 2, q, count + 1);
    > hiq (p + 1, q, count + 1);
    > a[p][q] = HOLE;
    > a[p + 1][q] = COIN;
    > a[p + 2][q] = COIN;
    > }
    >
    > if (validposition3 (p, q))
    > {
    > flag = 1;
    > a[p][q] = COIN;
    > a[p][q - 1] = HOLE;
    > a[p][q - 2] = HOLE;
    > hiq (p, q - 2, count + 1);
    > hiq (p, q - 1, count + 1);
    > a[p][q] = HOLE;
    > a[p][q - 1] = COIN;
    > a[p][q - 2] = COIN;
    > }
    >
    > if (validposition4 (p, q))
    > {
    > flag = 1;
    > a[p][q] = COIN;
    > a[p][q + 1] = HOLE;
    > a[p + 2][q + 2] = HOLE;
    > hiq (p, q + 2, count + 1);
    > hiq (p, q + 1, count + 1);
    > a[p][q] = HOLE;
    > a[p][q + 1] = COIN;
    > a[p][q + 2] = COIN;
    > }
    >
    >
    > if (flag == 0)
    > {
    > tmp = 0;
    >
    > for (i = 0; i < SIZE; i++)
    > for (j = 0; j < SIZE; j++)
    > if (a[j] == HOLE)
    > {
    > if (validposition1 (i, j) || validposition2 (i, j)
    > || validposition3 (i, j) || validposition4 (i, j))
    > {
    > tmp = 1;
    > hiq (i, j, count + 1);
    > }
    > }
    >
    > if (tmp == 0 )
    > {
    > if(isonlythat())
    > print_array ();
    > else
    > return;
    > }
    > else
    > return;
    > }
    >
    >}
    >
    >int
    >main ()
    >{
    > initialize ();
    > print_array ();
    > hiq (3, 3, 0);
    > return 0;
    >}
    >
    >---------------------END--------------------




    <<Remove the del for email>>
     
    Barry Schwarz, Jun 3, 2004
    #4
  5. Niklaus

    Niklaus Guest

    Hi,
    Thank you for the help. I made a small typo . The actual code is
    below. It only had an error .
    Well the limits are being checked in within_l. I have made the
    modifications.

    Even i *feel*(i may be wrong) that because of a lot of backtracking
    the stack size setup by OS for the program is small so we have
    segfault ?

    --------------BEGIN----------------
    #include<stdio.h>
    #define SIZE 7
    int a[SIZE][SIZE];
    #define NOTVALID -1
    #define HOLE 8
    #define COIN 9
    #define TRUE 1
    #define FALSE 0

    void
    print_array (void)
    {
    int i, j;
    for (i = 0; i < SIZE; i++)
    {
    printf ("\n");
    for (j = 0; j < SIZE; j++)
    printf (" %2c",
    (a[j] == NOTVALID ? ' ' : (a[j] == HOLE ? '0' : '1')));
    }
    printf ("\n#########################\n");
    }

    void
    initialize (void)
    {
    int i, j;
    for (i = 0; i < SIZE; i++)
    for (j = 0; j < SIZE; j++)
    a[j] = NOTVALID;

    for (i = 2; i < 5; i++)
    for (j = 0; j < SIZE; j++)
    a[j] = COIN;
    for (i = 0; i < SIZE; i++)
    for (j = 2; j < 5; j++)
    a[j] = COIN;
    a[3][3] = HOLE;
    }

    int
    within_l (int m, int n)
    {
    if (m < 0 || m > (SIZE - 1) || n < 0 || n > (SIZE - 1))
    return FALSE;

    if (a[m][n] == NOTVALID)
    return FALSE;

    return TRUE;
    }

    /* if i,j is a hole */
    int
    validposition1 (int i, int j)
    {
    if (within_l (i - 2, j) && (a[i - 1][j] == COIN) && a[i-2][j] ==
    COIN )
    return TRUE;
    return FALSE;
    }

    int
    validposition2 (int i, int j)
    {
    if (within_l (i + 2, j) && (a[i + 1][j] == COIN) && a[i+2][j] ==
    COIN )
    return TRUE;
    return FALSE;
    }

    int
    validposition3 (int i, int j)
    {
    if (within_l (i, j - 2) && (a[j - 1] == COIN) && a[j-2] ==
    COIN )
    return TRUE;
    return FALSE;
    }

    int
    validposition4 (int i, int j)
    {
    if (within_l (i, j + 2) && (a[j + 1] == COIN) && a[j+2] ==
    COIN )
    return TRUE;
    return FALSE;
    }

    int isonlythat(void)
    {
    int i,j;
    for(i=0;i<SIZE;i++)
    for(j=0;j<SIZE;j++)
    if(a[j] == COIN && (i!=3 ||j!=3))
    return FALSE;


    if(a[3][3] == HOLE)
    return FALSE;


    return TRUE;
    }



    void
    hiq (int p, int q, int count)
    {
    int flag = 0, i, j, tmp;
    // printf("%d %d\n",p,q);
    // print_array();

    if (validposition1 (p, q))
    {
    flag = 1;
    a[p][q] = COIN;
    a[p - 1][q] = HOLE;
    a[p - 2][q] = HOLE;
    hiq (p - 2, q, count + 1);
    hiq (p - 1, q, count + 1);
    a[p][q] = HOLE;
    a[p - 1][q] = COIN;
    a[p - 2][q] = COIN;
    }

    if (validposition2 (p, q))
    {
    flag = 1;
    a[p][q] = COIN;
    a[p + 1][q] = HOLE;
    a[p + 2][q] = HOLE;
    hiq (p + 2, q, count + 1);
    hiq (p + 1, q, count + 1);
    a[p][q] = HOLE;
    a[p + 1][q] = COIN;
    a[p + 2][q] = COIN;
    }

    if (validposition3 (p, q))
    {
    flag = 1;
    a[p][q] = COIN;
    a[p][q - 1] = HOLE;
    a[p][q - 2] = HOLE;
    hiq (p, q - 2, count + 1);
    hiq (p, q - 1, count + 1);
    a[p][q] = HOLE;
    a[p][q - 1] = COIN;
    a[p][q - 2] = COIN;
    }

    if (validposition4 (p, q))
    {
    flag = 1;
    a[p][q] = COIN;
    a[p][q + 1] = HOLE;
    a[p][q + 2] = HOLE;
    hiq (p, q + 2, count + 1);
    hiq (p, q + 1, count + 1);
    a[p][q] = HOLE;
    a[p][q + 1] = COIN;
    a[p][q + 2] = COIN;
    }


    if (flag == 0)
    {
    tmp = 0;

    for (i = 0; i < SIZE; i++)
    for (j = 0; j < SIZE; j++)
    if (a[j] == HOLE)
    {
    if (validposition1 (i, j) || validposition2 (i, j)
    || validposition3 (i, j) || validposition4 (i, j))
    {
    tmp = 1;
    hiq (i, j, count + 1);
    }
    }

    if (tmp == 0 )
    {
    if(isonlythat())
    print_array ();
    else
    return;
    }
    else
    return;
    }

    }

    int
    main ()
    {
    initialize ();
    print_array ();
    hiq (3, 3, 0);
    return 0;
    }

    ----------------END--------------------
     
    Niklaus, Jun 3, 2004
    #5
  6. Niklaus wrote:
    >
    > Hi,
    > Thank you for the help. I made a small typo . The actual code is
    > below. It only had an error .
    > Well the limits are being checked in within_l. I have made the
    > modifications.
    >
    > Even i *feel*(i may be wrong) that because of a lot of backtracking
    > the stack size setup by OS for the program is small so we have
    > segfault ?
    >
    > --------------BEGIN----------------
    > #include<stdio.h>
    > #define SIZE 7
    > int a[SIZE][SIZE];
    > #define NOTVALID -1
    > #define HOLE 8
    > #define COIN 9
    > #define TRUE 1
    > #define FALSE 0
    >
    > void
    > print_array (void)
    > {
    > int i, j;
    > for (i = 0; i < SIZE; i++)
    > {
    > printf ("\n");
    > for (j = 0; j < SIZE; j++)
    > printf (" %2c",
    > (a[j] == NOTVALID ? ' ' : (a[j] == HOLE ? '0' : '1')));
    > }
    > printf ("\n#########################\n");
    > }
    >
    > void
    > initialize (void)
    > {
    > int i, j;
    > for (i = 0; i < SIZE; i++)
    > for (j = 0; j < SIZE; j++)
    > a[j] = NOTVALID;
    >
    > for (i = 2; i < 5; i++)
    > for (j = 0; j < SIZE; j++)
    > a[j] = COIN;
    > for (i = 0; i < SIZE; i++)
    > for (j = 2; j < 5; j++)
    > a[j] = COIN;
    > a[3][3] = HOLE;
    > }
    >
    > int
    > within_l (int m, int n)
    > {
    > if (m < 0 || m > (SIZE - 1) || n < 0 || n > (SIZE - 1))
    > return FALSE;
    >
    > if (a[m][n] == NOTVALID)
    > return FALSE;
    >
    > return TRUE;
    > }
    >
    > /* if i,j is a hole */
    > int
    > validposition1 (int i, int j)
    > {
    > if (within_l (i - 2, j) && (a[i - 1][j] == COIN) && a[i-2][j] ==
    > COIN )
    > return TRUE;
    > return FALSE;
    > }
    >
    > int
    > validposition2 (int i, int j)
    > {
    > if (within_l (i + 2, j) && (a[i + 1][j] == COIN) && a[i+2][j] ==
    > COIN )
    > return TRUE;
    > return FALSE;
    > }
    >
    > int
    > validposition3 (int i, int j)
    > {
    > if (within_l (i, j - 2) && (a[j - 1] == COIN) && a[j-2] ==
    > COIN )
    > return TRUE;
    > return FALSE;
    > }
    >
    > int
    > validposition4 (int i, int j)
    > {
    > if (within_l (i, j + 2) && (a[j + 1] == COIN) && a[j+2] ==
    > COIN )
    > return TRUE;
    > return FALSE;
    > }
    >
    > int isonlythat(void)
    > {
    > int i,j;
    > for(i=0;i<SIZE;i++)
    > for(j=0;j<SIZE;j++)
    > if(a[j] == COIN && (i!=3 ||j!=3))
    > return FALSE;
    >
    > if(a[3][3] == HOLE)
    > return FALSE;
    >
    > return TRUE;
    > }
    >
    > void
    > hiq (int p, int q, int count)
    > {
    > int flag = 0, i, j, tmp;
    > // printf("%d %d\n",p,q);
    > // print_array();
    >
    > if (validposition1 (p, q))
    > {
    > flag = 1;
    > a[p][q] = COIN;
    > a[p - 1][q] = HOLE;
    > a[p - 2][q] = HOLE;
    > hiq (p - 2, q, count + 1);
    > hiq (p - 1, q, count + 1);
    > a[p][q] = HOLE;
    > a[p - 1][q] = COIN;
    > a[p - 2][q] = COIN;
    > }
    >
    > if (validposition2 (p, q))
    > {
    > flag = 1;
    > a[p][q] = COIN;
    > a[p + 1][q] = HOLE;
    > a[p + 2][q] = HOLE;
    > hiq (p + 2, q, count + 1);
    > hiq (p + 1, q, count + 1);
    > a[p][q] = HOLE;
    > a[p + 1][q] = COIN;
    > a[p + 2][q] = COIN;
    > }
    >
    > if (validposition3 (p, q))
    > {
    > flag = 1;
    > a[p][q] = COIN;
    > a[p][q - 1] = HOLE;
    > a[p][q - 2] = HOLE;
    > hiq (p, q - 2, count + 1);
    > hiq (p, q - 1, count + 1);
    > a[p][q] = HOLE;
    > a[p][q - 1] = COIN;
    > a[p][q - 2] = COIN;
    > }
    >
    > if (validposition4 (p, q))
    > {
    > flag = 1;
    > a[p][q] = COIN;
    > a[p][q + 1] = HOLE;
    > a[p][q + 2] = HOLE;
    > hiq (p, q + 2, count + 1);
    > hiq (p, q + 1, count + 1);
    > a[p][q] = HOLE;
    > a[p][q + 1] = COIN;
    > a[p][q + 2] = COIN;
    > }
    >
    > if (flag == 0)
    > {
    > tmp = 0;
    >
    > for (i = 0; i < SIZE; i++)
    > for (j = 0; j < SIZE; j++)
    > if (a[j] == HOLE)
    > {
    > if (validposition1 (i, j) || validposition2 (i, j)
    > || validposition3 (i, j) || validposition4 (i, j))
    > {
    > tmp = 1;
    > hiq (i, j, count + 1);
    > }
    > }
    >
    > if (tmp == 0 )
    > {
    > if(isonlythat())
    > print_array ();
    > else
    > return;
    > }
    > else
    > return;
    > }
    >
    > }
    >
    > int
    > main ()
    > {
    > initialize ();
    > print_array ();
    > hiq (3, 3, 0);
    > return 0;
    > }
    >
    > ----------------END--------------------


    You don't say what this prograsm is supposed to be doing. But the
    problem might be that function hiq() seems to have the possibility of
    infinite recursion.

    --
    Fred L. Kleinschmidt
    Boeing Associate Technical Fellow
    Technical Architect, Common User Interface Services
    M/S 2R-94 (206)544-5225
     
    Fred L. Kleinschmidt, Jun 3, 2004
    #6
  7. Niklaus

    Old Wolf Guest

    (Niklaus) wrote:

    > Can someone point out what is wrong with this code ? How can i make
    > it better optimize it. When run it gives me seg fault in linux. But
    > windows it works fine(runs for a long time).
    >
    > Do we have something like stack size growing enormously and then
    > saying you can't access ,so a segfault ?


    Firstly, it looks to me as if there is no undefined behaviour anywhere
    (despite what others have said). About the worst I could say is that
    "validposition1" would check outside the array bounds if you call it
    with, say (-1, 0), but you never do this.

    However, at least one of the four validposition functions could
    always be TRUE, and in the hiq() function you call hiq() again
    if one of those functions was true. Most likely, you are running
    out of stack. You could confirm this by adding code to display
    the current value of "count" every time hiq() starts, and you
    should find that it is always the same or similar value each time
    the program crashes.

    To fix this problem you should design your program to not recurse
    so deeply (or even to not use recursion at all). If you used
    malloc to allocate new memory, then a) you could detect when
    you ran out of memory, and b) you would be less likely to run out
    (typically, malloc can use up to all of the PC's memory, whereas
    there might only be a fixed-size area that is allowed for stack space).

    As a stopgap measure, you could malloc your local variables and the
    next calls' function parameters all in one go, so that you have
    hiq(int *); and no local variables, this would probably allow you
    to go to 4* the depth that you were before (but could not be
    considered good programming style!)
     
    Old Wolf, Jun 3, 2004
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. walala
    Replies:
    3
    Views:
    2,249
    Ralf Hildebrandt
    Sep 10, 2003
  2. willem oosthuizen

    What is wrong with the following code?

    willem oosthuizen, Oct 10, 2003, in forum: VHDL
    Replies:
    9
    Views:
    1,331
  3. Matthew
    Replies:
    7
    Views:
    785
    Priscilla Walmsley
    Jan 7, 2005
  4. David. E. Goble
    Replies:
    9
    Views:
    495
    David. E. Goble
    Feb 2, 2005
  5. kiran
    Replies:
    12
    Views:
    1,188
    Scott Sauyet
    Dec 7, 2011
Loading...

Share This Page