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[i][j] == NOTVALID ? 32 : (a[i][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[i][j] == NOTVALID ? ' ' : (a[i][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[i][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[i][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[i][j] = NOTVALID;
for( ; i < 5; i++)
for(j = 0; j < SIZE; j++)
a[i][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[i][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[i][j - 1] == COIN) && a[i][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[i][j + 1] == COIN) && a[i][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[i][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[i][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
Similar Threads
, and (5,3,9). At this point, print_array
