|
Ok, so this project is due in 2 hours, and I've been working on it all day. It's pretty much done but it's just not working and I just can't stare at it any more. Can someone help?
The project is basically analyzing contiguous spaces in a two-dimensional array (find the blobs). A blob is 2 or more contiguous spaces in the array. I've figured out how to find the blobs using a stack, and I think I implemented it correctly but it's not working for some reason. The code hangs within the while loop so I'm assuming something in there is wrong. here is the code:
http://pastebin.com/d30e116f3
^^pastebin now.
I know its way over commented, I'm a total noob at c++ (mostly code in java,asm, and python) and it got confusing with braces and shit. I also know this could be done way more efficiently but I don't really care at this point, I just need it to work. The following DOES work: importing grid from text file, displaying the grid, and everything else. the above method hangs in the while loop and I can't figure out why. Help PLEASE!
|
|
|
with no identation its impossible to read anything
|
|
|
Wow that's way to messy, sorry I'm not touching that
was the //startif //endif comments really necessary? lol
Where exactly does it hang? use the debugger, might give you a clue
|
On October 14 2009 11:08 Eti307 wrote:
Wow that's way to messy, sorry I'm not touching that
was the //startif //endif comments really necessary? lol
Where exactly does it hang? use the debugger, might give you a clue
the startif endif i put it so i could check and see if i was missing a bracket when i was fixing syntax errors. i can clean it real fast.
|
What are the INPUTs and OUTPUTs of this function supposed to be?
|
On October 14 2009 11:12 tossinYoSalad wrote:Show nested quote +On October 14 2009 11:08 Eti307 wrote:
Wow that's way to messy, sorry I'm not touching that
was the //startif //endif comments really necessary? lol
Where exactly does it hang? use the debugger, might give you a clue the startif endif i put it so i could check and see if i was missing a bracket when i was fixing syntax errors. i can clean it real fast.
instead of doing that just type in both brackets each and everytime you are using something with brackets. Prevents those type of errors
|
On October 14 2009 11:12 yenta wrote:
What are the INPUTs and OUTPUTs of this function supposed to be?
all it does is count the number of blobs and keep track of the recursion depth. numBlobs is incremented immediately after the while loop and recDepth is incremented at the end of the function.
there is no input it acts on a grid held in the class (just a two-dim array of ints) its called gridCopy. theGrid is the same thing only its an arr of chars (this teacher is psycho, i had to do it this way)
i know its a horrible implementation believe me.
|
On October 14 2009 11:16 Eti307 wrote:Show nested quote +On October 14 2009 11:12 tossinYoSalad wrote:On October 14 2009 11:08 Eti307 wrote:
Wow that's way to messy, sorry I'm not touching that
was the //startif //endif comments really necessary? lol
Where exactly does it hang? use the debugger, might give you a clue the startif endif i put it so i could check and see if i was missing a bracket when i was fixing syntax errors. i can clean it real fast. instead of doing that just type in both brackets each and everytime you are using something with brackets. Prevents those type of errors
ya i do, i also needed to put a a few lines in specific places at the end and there were 5 braces in a row at the end lol.
|
On October 14 2009 11:16 tossinYoSalad wrote:Show nested quote +On October 14 2009 11:12 yenta wrote:
What are the INPUTs and OUTPUTs of this function supposed to be? all it does is count the number of blobs and keep track of the recursion depth. numBlobs is incremented immediately after the while loop and recDepth is incremented at the end of the function. i know its a horrible implementation believe me.
Rewrite it like this:
RECURSIVE CALLER
Initialize count
Initialize array of array with flags (w/e you want)
FOR( 0...x )
FOR( 0..y )
if point @ x,y is unchecked & x.y is a space, call recursive worker
//FOR
//FOR
return w/e
RECURSIVE WORKER ( root, current_x, current_y, pointer to 2D array, ref to count )
base case:
return if out of bounds
return if space you're looking has been marked 'looked at'
recursive case:
count adj spaces by calling self with: ( x-1,y ), ( x+1, y), (x, y+1), (x, y-1) + diagonals if they count.
if adj spaces > 0 & root == true, increment counter //endif
mark current space as read
END
|
On October 14 2009 11:29 yenta wrote:Show nested quote +On October 14 2009 11:16 tossinYoSalad wrote:On October 14 2009 11:12 yenta wrote:
What are the INPUTs and OUTPUTs of this function supposed to be? all it does is count the number of blobs and keep track of the recursion depth. numBlobs is incremented immediately after the while loop and recDepth is incremented at the end of the function. i know its a horrible implementation believe me. Rewrite it like this: RECURSIVE CALLER Initialize count Initialize array of array with flags (w/e you want) FOR( 0...x ) FOR( 0..y ) if point @ x,y is unchecked & x.y is a space, call recursive worker //FOR //FOR return w/e RECURSIVE WORKER ( root, current_x, current_y, pointer to 2D array, ref to count ) base case: return if out of bounds return if space you're looking has been marked 'looked at' recursive case: count adj spaces by calling self with: ( x-1,y ), ( x+1, y), (x, y+1), (x, y-1) + diagonals if they count. if adj spaces > 0 & root == true, increment counter //endif mark current space as read END
thanks alot, what do you mean by root though? and because the 2d array is a class var i dont need to pass it though do i?
|
I only very briefly skimmed it so I may be way off, but it looks like your bounds checking is wrong?
Your Code:
if (rowPtr-1 > 0)
if(rowPtr+1 < theGrid.getRows())
I'm assuming you're trying to make sure that 0 <= rowPtr < theGrid.getRows(). If that's the case, then shouldn't it be:
if (rowPtr+1 > 0)
if(rowPtr < theGrid.getRows())
|
On October 14 2009 11:38 Slithe wrote:
I only very briefly skimmed it so I may be way off, but it looks like your bounds checking is wrong?
Your Code:
if (rowPtr-1 > 0)
if(rowPtr+1 < theGrid.getRows())
I'm assuming you're trying to make sure that 0 <= rowPtr < theGrid.getRows(). If that's the case, then shouldn't it be:
if (rowPtr+1 > 0)
if(rowPtr < theGrid.getRows())
uhh you were sorta right, but you DID point out an error it needs to be if(rowPtr-1 >= 0) otherwise itll never enter those code segments on the leftmost or rightmost bounds.
but yes it needs to be within the bounds of [0,theGrid.getRows()], but because it can only exceed the left bound on a -1, and it can only exceed the right bound on a +1 i ommited those calls.
fixed it to that and still didnt work. I think its a stack error in the original code, but now im rewriting with yenta's suggestion, only thing i dont get is how to actually count the blobs using that method, i can get it to pass over all the blocks, but no way to tell when the end of a blob has been reached.
|
 due in 2 hours.. if it was due in 2 days, i could help
|
|
|
Well, that's a major change from when I started looking at it...
As far as I can tell, the previous version of the code did not work because you never modified the value of a cell when you added it to the stack in the while loop. And since you keep on adding more items to the stack which each added more since nothing was being ruled out on subsequent loops, the while loop never ends. Also, you are probably supposed to check your bounds to be "var >= 0" instead of "var > 0" unless you don't need to check the 0 index for some reason.
In your new code your upper bound should be comparing ">=" theGrid.getRows() instead. Same for the .getCols() one.
else if(gridCopy[curr_x][curr_y] == 0){return;}
Use double equal signs for comparisons. Common mistake.
gridCopy[curr_x][curr_y] = 0;
That should go before you make the recursive calls or you'll get the same error.
Hope this helps.
|
No idea what this thing is supposed to do, but your counter doesn't increment.
edit: oh, didn't read the whole OP I guess
|
I'm pretty sure that's supposed to count the number of blobs. Unfortunately, the code doesn't ever determine whether each location is part of a blob or not.
|
On October 14 2009 11:34 tossinYoSalad wrote:Show nested quote +On October 14 2009 11:29 yenta wrote:On October 14 2009 11:16 tossinYoSalad wrote:On October 14 2009 11:12 yenta wrote:
What are the INPUTs and OUTPUTs of this function supposed to be? all it does is count the number of blobs and keep track of the recursion depth. numBlobs is incremented immediately after the while loop and recDepth is incremented at the end of the function. i know its a horrible implementation believe me. Rewrite it like this: RECURSIVE CALLER Initialize count Initialize array of array with flags (w/e you want) FOR( 0...x ) FOR( 0..y ) if point @ x,y is unchecked & x.y is a space, call recursive worker //FOR //FOR return w/e RECURSIVE WORKER ( root, current_x, current_y, pointer to 2D array, ref to count ) base case: return if out of bounds return if space you're looking has been marked 'looked at' recursive case: count adj spaces by calling self with: ( x-1,y ), ( x+1, y), (x, y+1), (x, y-1) + diagonals if they count. if adj spaces > 0 & root == true, increment counter //endif mark current space as read END thanks alot, what do you mean by root though? and because the 2d array is a class var i dont need to pass it though do i?
look at this:
http://pastebin.com/m7c4ab47d
|
Wow, that's messy :S needs mass refactoring.
A tip for writing procedurally complex code like that is to employ comment-first coding which allows you to understand exactly what it is you need to do before you even write it. This code was obviously written "as you went along".
Start fresh, write a bunch of pseudocode in comments, then all you should have to do is fill in the logic under the comments.
|
On October 14 2009 12:48 prOxi.swAMi wrote:
Wow, that's messy :S needs mass refactoring.
A tip for writing procedurally complex code like that is to employ comment-first coding which allows you to understand exactly what it is you need to do before you even write it. This code was obviously written "as you went along".
Start fresh, write a bunch of pseudocode in comments, then all you should have to do is fill in the logic under the comments.
uhh were you looking at the most recent version? cuz its very simple now lol. and.. this is due in 10 mins so i dont really have time to do it. its logically correct, ive had 4 people look at it and agree, but for some reason its endlessly looping between 4 method calls and.. well idk. ill just submit it as is and hope for the best. oddly enough correctness is NOT a huge part of our project grades.
thanks for help everyone, especially yenta.
|
Did you move gridCopy[curr_x][curr_y] = 0; to before the recursive calls?
On October 14 2009 12:53 tossinYoSalad wrote:
oddly enough correctness is NOT a huge part of our project grades.
Yeah, I'd take clean code that doesn't quite work over that mess you started with any day. Adding anything to that would be a nightmare, but fixing the newer version should be easy.
|
On October 14 2009 12:56 SonuvBob wrote:
Did you move gridCopy[curr_x][curr_y] = 0; to before the recursive calls?
yes i did
edit: haha well thats what i get when i wait till last day to do programming assignments. this is like the 10th class ive taken involving programming and this is the only assignment ive EVER had problems with.
|
On October 14 2009 12:35 yenta wrote:Show nested quote +On October 14 2009 11:34 tossinYoSalad wrote:On October 14 2009 11:29 yenta wrote:On October 14 2009 11:16 tossinYoSalad wrote:On October 14 2009 11:12 yenta wrote:
What are the INPUTs and OUTPUTs of this function supposed to be? all it does is count the number of blobs and keep track of the recursion depth. numBlobs is incremented immediately after the while loop and recDepth is incremented at the end of the function. i know its a horrible implementation believe me. Rewrite it like this: RECURSIVE CALLER Initialize count Initialize array of array with flags (w/e you want) FOR( 0...x ) FOR( 0..y ) if point @ x,y is unchecked & x.y is a space, call recursive worker //FOR //FOR return w/e RECURSIVE WORKER ( root, current_x, current_y, pointer to 2D array, ref to count ) base case: return if out of bounds return if space you're looking has been marked 'looked at' recursive case: count adj spaces by calling self with: ( x-1,y ), ( x+1, y), (x, y+1), (x, y-1) + diagonals if they count. if adj spaces > 0 & root == true, increment counter //endif mark current space as read END thanks alot, what do you mean by root though? and because the 2d array is a class var i dont need to pass it though do i? look at this: http://pastebin.com/m7c4ab47d
quoting myself incase you missed the solution i posted :p
|
On October 14 2009 13:00 yenta wrote:Show nested quote +On October 14 2009 12:35 yenta wrote:On October 14 2009 11:34 tossinYoSalad wrote:On October 14 2009 11:29 yenta wrote:On October 14 2009 11:16 tossinYoSalad wrote:On October 14 2009 11:12 yenta wrote:
What are the INPUTs and OUTPUTs of this function supposed to be? all it does is count the number of blobs and keep track of the recursion depth. numBlobs is incremented immediately after the while loop and recDepth is incremented at the end of the function. i know its a horrible implementation believe me. Rewrite it like this: RECURSIVE CALLER Initialize count Initialize array of array with flags (w/e you want) FOR( 0...x ) FOR( 0..y ) if point @ x,y is unchecked & x.y is a space, call recursive worker //FOR //FOR return w/e RECURSIVE WORKER ( root, current_x, current_y, pointer to 2D array, ref to count ) base case: return if out of bounds return if space you're looking has been marked 'looked at' recursive case: count adj spaces by calling self with: ( x-1,y ), ( x+1, y), (x, y+1), (x, y-1) + diagonals if they count. if adj spaces > 0 & root == true, increment counter //endif mark current space as read END thanks alot, what do you mean by root though? and because the 2d array is a class var i dont need to pass it though do i? look at this: http://pastebin.com/m7c4ab47d quoting myself incase you missed the solution i posted :p
holy shit i didnt see that before lol. thanks man but its too late now. you can see my final solution at http://pastebin.com/d3918f10e.
i modified your solution slightly to simply have every call of processWork mark off an entire blob and then every iteration of the loop in processGrid increment the number of blobs.
|
line 13:
you have an assignment instead of condition
|
hey if anyone is curious.. i fixed it, 10 minutes after project was due. sonovbob found the broken code like 10 posts back i just missed it lol. it was the comparison == , and i was using =. fucking stupid c++ compiler should catch that lol.
anyway... thats what it does.
|
On October 14 2009 13:14 tossinYoSalad wrote:
sonovbob found the broken code like 10 posts back i just missed it lol.
... did he now?
|
The compiler's not going to catch it because it's a legal operation, not an error. When you do an assignment, the assigned variable is the return value.
|
|
|
On October 14 2009 13:14 tossinYoSalad wrote:
hey if anyone is curious.. i fixed it, 10 minutes after project was due. sonovbob found the broken code like 10 posts back i just missed it lol. it was the comparison == , and i was using =. fucking stupid c++ compiler should catch that lol.
anyway... thats what it does.
It's not a compile error so it shouldn't catch that. Doing assignment within a conditional is a pretty normal thing to do.
If you want some help from the compiler I believe there are certain warning flags you can set that will give a warning if you do not parenthesize the assignment within the conditional.
if( something = newSomething)
...
Could be set up to give you a compiler warning which would then go away if it was changed to
if( (something = newSomething) )
...
Can't remember the exact flag you need but I'm sure you can google it easily enough.
|
On October 14 2009 14:16 AeTheReal wrote:Show nested quote +On October 14 2009 13:14 tossinYoSalad wrote:
sonovbob found the broken code like 10 posts back i just missed it lol. ... did he now?
yes.. yes.. he did.
as to the assignment within a conditional, yeah i know its a legal operation i was just mad that i didnt catch it lol. I normally don't mess that up so I don't think to check it.
also, when would you need to do an assignment within a conditional? i cant really find a use for that..
|
On October 14 2009 14:16 AeTheReal wrote:Show nested quote +On October 14 2009 13:14 tossinYoSalad wrote:
sonovbob found the broken code like 10 posts back i just missed it lol. ... did he now?
I must've used my admin powers to post it as someone else.
|
On October 14 2009 13:14 tossinYoSalad wrote:hey if anyone is curious.. i fixed it, 10 minutes after project was due. sonovbob found the broken code like 10 posts back i just missed it lol. it was the comparison == , and i was using =. fucking stupid c++ compiler should catch that lol. anyway... thats what it does.
Recursion depth 534 o.O
Didn't read the code, though that seems like a lot of recursion. Prolly would've done it by recursively calling hasBlobProperty() and having the outer layer go through every array position that hasn't already been marked as having a part of a blob there, and the second layer would keep track of the # of blobs. But apparently your method works so it's all good =)
|
Jesus christ, you guys are so awesome. I wish I knew a programming language. Just looking at the way you talk makes my head hurt.
Is C++ hard to learn?
|
nah C++ is pretty easy, although nowadays I suggest you learn Java or C#
EDIT: Although, if I recall correctly C# can execute up to 40 times slower than C++, and the JVM means Java is slower as well (but you would learn the details yourself in a Java course). Of course, efficiency usually won't matter too much... though I think most games are not made with Java/C# (WoW for instance is written in C++), but you would use a lot of C# and Java in other programming jobs.
|
On October 14 2009 15:31 tossinYoSalad wrote:Show nested quote +On October 14 2009 14:16 AeTheReal wrote:On October 14 2009 13:14 tossinYoSalad wrote:
sonovbob found the broken code like 10 posts back i just missed it lol. ... did he now? yes.. yes.. he did. as to the assignment within a conditional, yeah i know its a legal operation i was just mad that i didnt catch it lol. I normally don't mess that up so I don't think to check it. also, when would you need to do an assignment within a conditional? i cant really find a use for that..
I don't think it's ever a necessity (could be wrong), it's just a nice convenience for a lot of things.
|
Damn, this looks a lot harder than Java. Does C++ use the same operators?
|
The issue with c++ is that there are a lot of nuances to it that gives it a steeper learning curve. As a result, one is a lot more error-prone when writing c++ code.
Regarding the assignment inside a conditional, here's random example code where it might be used:
char[] str = "Hello TeamLiquid!"
char c;
for (int i = 0; (c=str[i]) != 0; i++) {
printf("Letter: %c", c);
}
From a stylistic point of view, I don't think it's usually a particularly good idea, but it would be inconsistent to treat the assignment differently just because it was placed inside a conditional statement.
|
compiling with -Wall may have brought up that error.
something like g++ -Wall project.cpp
|
On October 14 2009 16:14 Slithe wrote:
The issue with c++ is that there are a lot of nuances to it that gives it a steeper learning curve. As a result, one is a lot more error-prone when writing c++ code.
Regarding the assignment inside a conditional, here's random example code where it might be used:
char[] str = "Hello TeamLiquid!"
char c;
for (int i = 0; (c=str[i]) != 0; i++) {
printf("Letter: %c", c);
}
From a stylistic point of view, I don't think it's usually a particularly good idea, but it would be inconsistent to treat the assignment differently just because it was placed inside a conditional statement.
Huh that does make a lot of sense actually lol. I'm just used to java where if the if() statement doesn't resolve to a boolean it doesn't compile. C++ is nice and I like the fact that you have more freedom and it compiles directly to machine language and all, but some things about it just frustrate me. Like the fact that you can't declare an array without having a definite size for it ( yes I tried using extern.)
Also thanks a ton to everyone who helped me out. You guys rock  .
oh and Sonovbob didnt catch the error. Sorry aethereal. He found another error though .
|
On October 15 2009 04:10 tossinYoSalad wrote:Show nested quote +On October 14 2009 16:14 Slithe wrote:
The issue with c++ is that there are a lot of nuances to it that gives it a steeper learning curve. As a result, one is a lot more error-prone when writing c++ code.
Regarding the assignment inside a conditional, here's random example code where it might be used:
char[] str = "Hello TeamLiquid!"
char c;
for (int i = 0; (c=str[i]) != 0; i++) {
printf("Letter: %c", c);
}
From a stylistic point of view, I don't think it's usually a particularly good idea, but it would be inconsistent to treat the assignment differently just because it was placed inside a conditional statement. Huh that does make a lot of sense actually lol. I'm just used to java where if the if() statement doesn't resolve to a boolean it doesn't compile. C++ is nice and I like the fact that you have more freedom and it compiles directly to machine language and all, but some things about it just frustrate me. Like the fact that you can't declare an array without having a definite size for it ( yes I tried using extern.) Also thanks a ton to everyone who helped me out. You guys rock . oh and Sonovbob didnt catch the error. Sorry aethereal. He found another error though .
You can use vectors if you want to implement dynamic arrays, or use pointers, like:
int *ptr;
ptr = new int[5];
...
int *ptr2 = new int[10];
for ( ... ) ptr2[i] = ptr[i];
delete[] ptr;
|
On October 14 2009 15:43 EtherealDeath wrote:
nah C++ is pretty easy, although nowadays I suggest you learn Java or C#
EDIT: Although, if I recall correctly C# can execute up to 40 times slower than C++, and the JVM means Java is slower as well (but you would learn the details yourself in a Java course). Of course, efficiency usually won't matter too much... though I think most games are not made with Java/C# (WoW for instance is written in C++), but you would use a lot of C# and Java in other programming jobs.
if you want to do game programming i believe you should learn C++ but you can also do some C#/XNA stuff if you're more inclined to do so that way..
However I do believe more software jobs (outside of games) use C#/Java for newer stuff. At the place where i interned at, their old utilities were written in VB6 with the newer ones using C#.
|
On October 15 2009 05:08 ph33r wrote:Show nested quote +On October 15 2009 04:10 tossinYoSalad wrote:On October 14 2009 16:14 Slithe wrote:
The issue with c++ is that there are a lot of nuances to it that gives it a steeper learning curve. As a result, one is a lot more error-prone when writing c++ code.
Regarding the assignment inside a conditional, here's random example code where it might be used:
char[] str = "Hello TeamLiquid!"
char c;
for (int i = 0; (c=str[i]) != 0; i++) {
printf("Letter: %c", c);
}
From a stylistic point of view, I don't think it's usually a particularly good idea, but it would be inconsistent to treat the assignment differently just because it was placed inside a conditional statement. Huh that does make a lot of sense actually lol. I'm just used to java where if the if() statement doesn't resolve to a boolean it doesn't compile. C++ is nice and I like the fact that you have more freedom and it compiles directly to machine language and all, but some things about it just frustrate me. Like the fact that you can't declare an array without having a definite size for it ( yes I tried using extern.) Also thanks a ton to everyone who helped me out. You guys rock . oh and Sonovbob didnt catch the error. Sorry aethereal. He found another error though . You can use vectors if you want to implement dynamic arrays, or use pointers, like: int *ptr; ptr = new int[5]; ... int *ptr2 = new int[10]; for ( ... ) ptr2[i] = ptr[i]; delete[] ptr;
Yeah I could have done that but it was unnecessary as it just required a two-dim array of fixed size. It created a problem because I wanted to have all references to the size of the array come from a single method, and you cannot do this upon creating the array (apparently). It wasn't a huge issue but it just irked me because I couldn't follow basic good programming principles.
|
|
|
|
|
|
EPT![[image loading]](http://i80.photobucket.com/albums/j175/darkness5723/proj2working.png)
