Scramble Elements in Array

fcommisso · 10-07-2009, 12:15 PM

Hi, I am working on a project for my C programming class. We have not covered pointers yet, and this project is primarily focused on Arrays mainly.

I have coded most of it but I'm stuck at the function I've created to "shuffle" or "scramble" the elements in the "game board"

my function is as follows:

Code:

void scramble(char gameBoard[][COLS], int w) // incomplete
{
	int g;
	char *b;
	
	if ( w < 50) 
	{
		srand(time(NULL));
		// search for zero in array and store position in x (row) & y (col)
		char x = find_Zero_In_Row(gameBoard);
		char y = find_Zero_In_Col(gameBoard);
		
		char unsigned z = rand()%4; // random number between 0 and 3, 0 and 3 included
		
		if ( z == 0 &&  y+1 < COLS) // case 1
		{
			gameBoard[x][y] = gameBoard[x][y+1];
			gameBoard[x][y+1] = 0;
		}
		else if ( z == 1 && y-1 > COLS) // case 2
		{
			gameBoard[x][y] = gameBoard[x][y]-1;
			gameBoard[x][y-1] = 0;
		}
		else if ( z == 2 && x+1 < ROWS) // case 3
		{
			gameBoard[x][y] = gameBoard[x+1][y];
			gameBoard[x+1][y] = 0;
		}
		else if ( z== 3 &&  x-1 > ROWS) // case 4
		{
			gameBoard[x][y] = gameBoard[x-1][y];
			gameBoard[x-1][y] = 0;
		}
		w += 1;
		scramble(gameBoard, w);
	}
	else print_Board(gameBoard);
}

I called my function from the Menu() funciton as:

Code:

   scramble(gameBoard, 0);

I know its pretty naiive, and it obviously isn't working as I would hope because my output is as follows:

$./a.out
Initial configuration [1-Random, 2-Specified configuration]: 1
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15

as you can see my board is still in order and not scrambled. Is there anything in my code that isn't working? I'm thinking it might just be bypassing all my conditions and just printing the array as it was passed by reference initially.

TIA

kcpilot · 10-07-2009, 12:24 PM

I may be wrong, but if memory serves me correctly, the rand() function may not be returning the type of values you think they are. I know I've found occasions where the value returned was a double value between 0.999999999 and 0.000000000, so to find a value between 0 - 3, you would first have to multiply by 100. Check your documentation for your particular compiler to see what the rand() function is returning.

**laserlight** · 10-07-2009, 12:39 PM

Quote:

Originally Posted by fcommisso

as you can see my board is still in order and not scrambled. Is there anything in my code that isn't working?

I am not sure what find_Zero_In_Row() and find_Zero_In_Col() do, but going by their names perhaps the problem is that there are no zeroes in your 2D array.

You might want to try another approach: swap gameBoard[0][0] with a randomly selected element of gameBoard. Then swap gameBoard[0][1] with a randomly selected element of gameBoard, excluding gameBoard[0][0]. Then swap gameBoard[0][2] with a randomly selected element of gameBoard, excluding those elements that have already been processed (i.e., gameBoard[0][0] and gameBoard[0][1]). When you only have one element left to process, you're done and the 2D array should be scrambled.

Quote:

Originally Posted by kcpilot

I may be wrong, but if memory serves me correctly, the rand() function may not be returning the type of values you think they are. I know I've found occasions where the value returned was a double value between 0.999999999 and 0.000000000, so to find a value between 0 - 3, you would first have to multiply by 100.

If you have come across such a standard library implementation, then you have found a major bug in that implementation. rand() must return an int, not a double.

fcommisso · 10-07-2009, 12:39 PM

here's a sample code I just whipped out to prove my range is indeed form 0 to 3:

Code:

#include <stdio.h>
#include <stdlib.h>

int main()
{
	int i;
	srand(time(NULL));
	for ( i = 0; i < 11; ++i)
	{
		char i = rand()%4;
		printf("%d\n", i);
	}
}

output:

$./a.out
2
3
1
2
0
0
2
1
0
1
2
~/Desktop $

fcommisso · 10-07-2009, 12:44 PM

Quote:

Originally Posted by laserlight

I am not sure what find_Zero_In_Row() and find_Zero_In_Col() do, but going by their names perhaps the problem is that there are no zeroes in your 2D array.

yes the array i made manually and does have a zero, else it would be pointless. I guarantee they return a valid position where the ever existant zero appears in the array.

Quote:

Originally Posted by laserlight

If you have come across such a standard library implementation, then you have found a major bug in that implementation. rand() must return an int, not a double.

Thanks, I did notice that as well and have changed it to an int type, yet my code it still not doing what I intend it to.
It prints out the original array I pass in with the '0' as a space as specified in my print_Board() funciton.

tabstop · 10-07-2009, 12:51 PM

Did you ever fix this?

Code:

gameBoard[x][y] = gameBoard[x][y]-1;

fcommisso · 10-07-2009, 12:52 PM

so this is my newest version of that function. Now it just swaps one element in the array.
so if my original array is:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15

then my output looks like this:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15

Code:

void scramble(char gameBoard[][COLS], int w) // incomplete
{
	srand(time(NULL));
	
	while ( w < 50) 
	{
		
		// search for zero in array and store position in x (row) & y (col)
		char x = find_Zero_In_Row(gameBoard);
		char y = find_Zero_In_Col(gameBoard);
		
		int unsigned z = rand()%4; // random number between 0 and 3, 0 and 3 included
		
		if ( z == 0 &&  y+1 < COLS) // case 1
		{
			gameBoard[x][y] = gameBoard[x][y+1];
			gameBoard[x][y+1] = 0;
		}
		else if ( z == 1 && y-1 > COLS) // case 2
		{
			gameBoard[x][y] = gameBoard[x][y]-1;
			gameBoard[x][y-1] = 0;
		}
		else if ( z == 2 && x+1 < ROWS) // case 3
		{
			gameBoard[x][y] = gameBoard[x+1][y];
			gameBoard[x+1][y] = 0;
		}
		else if ( z== 3 &&  x-1 > ROWS) // case 4
		{
			gameBoard[x][y] = gameBoard[x-1][y];
			gameBoard[x-1][y] = 0;
		}
		w += 1;
	}
	
	print_Board(gameBoard);
	print_Instructions();
	
}

fcommisso · 10-07-2009, 12:55 PM

ok, this thread doens't let me show the spaces how they are displayed in the terminal, but take my word for it that the number 15 in the array is originally to the far right and then after scramble the 15 swaps with the original empty space to the left of it.

fcommisso · 10-07-2009, 12:56 PM

I'm thinking my logic is flawed in the actual swapping of array elements...anyone?

fcommisso · 10-07-2009, 12:56 PM

Quote:

Originally Posted by tabstop

Did you ever fix this?

Code:

gameBoard[x][y] = gameBoard[x][y]-1;

oops...

**laserlight** · 10-07-2009, 12:59 PM

Well, considering that what you are doing is just moving the empty space around in the 2D array (and performing relatively expensive operations to find it on each iteration instead of just keeping track of its location), I suspect that the array will never be scrambled no matter what you do.

Why not go with what I suggested?

EDIT:
Oh, but that is not right: moving the empty space around should result in an eventual scrambling of the array, but it is probably just slow since you are only swapping the empty space with adjacent elements, and there are times when the swap does not even happen.

tabstop · 10-07-2009, 01:33 PM

Quote:

Originally Posted by laserlight

Well, considering that what you are doing is just moving the empty space around in the 2D array (and performing relatively expensive operations to find it on each iteration instead of just keeping track of its location), I suspect that the array will never be scrambled no matter what you do.

Why not go with what I suggested?

EDIT:
Oh, but that is not right: moving the empty space around should result in an eventual scrambling of the array, but it is probably just slow since you are only swapping the empty space with adjacent elements, and there are times when the swap does not even happen.

I think the point is to make the slider puzzle and to actually do the moves so that you know the puzzle that you present is solvable. It would be easier to (a) not do recursion (b) keep track of the empty block (c) not call srand each time, as it would not surprise me if you got 50 of the same move each time.

abachler · 10-07-2009, 02:58 PM

Quote:

Originally Posted by kcpilot

I may be wrong, but if memory serves me correctly, the rand() function may not be returning the type of values you think they are. I know I've found occasions where the value returned was a double value between 0.999999999 and 0.000000000, so to find a value between 0 - 3, you would first have to multiply by 100. Check your documentation for your particular compiler to see what the rand() function is returning.

rand() is a standardized function, it always returns an int, there is no room for alternate implementations, although a particular run-time may implement overloaded versions.

fcommisso · 10-07-2009, 03:09 PM

Quote:

Originally Posted by tabstop

I think the point is to make the slider puzzle and to actually do the moves so that you know the puzzle that you present is solvable. It would be easier to (a) not do recursion (b) keep track of the empty block (c) not call srand each time, as it would not surprise me if you got 50 of the same move each time.

yes very good observations guys...i'll will work on a better method.

10-07-2009, 12:15 PM	#1
fcommisso Registered User Join Date: Oct 2009 Posts: 21	Scramble Elements in Array Hi, I am working on a project for my C programming class. We have not covered pointers yet, and this project is primarily focused on Arrays mainly. I have coded most of it but I'm stuck at the function I've created to "shuffle" or "scramble" the elements in the "game board" my function is as follows: Code: void scramble(char gameBoard[][COLS], int w) // incomplete { int g; char b; if ( w < 50) { srand(time(NULL)); // search for zero in array and store position in x (row) & y (col) char x = find_Zero_In_Row(gameBoard); char y = find_Zero_In_Col(gameBoard); char unsigned z = rand()%4; // random number between 0 and 3, 0 and 3 included if ( z == 0 && y+1 < COLS) // case 1 { gameBoard[x][y] = gameBoard[x][y+1]; gameBoard[x][y+1] = 0; } else if ( z == 1 && y-1 > COLS) // case 2 { gameBoard[x][y] = gameBoard[x][y]-1; gameBoard[x][y-1] = 0; } else if ( z == 2 && x+1 < ROWS) // case 3 { gameBoard[x][y] = gameBoard[x+1][y]; gameBoard[x+1][y] = 0; } else if ( z== 3 && x-1 > ROWS) // case 4 { gameBoard[x][y] = gameBoard[x-1][y]; gameBoard[x-1][y] = 0; } w += 1; scramble(gameBoard, w); } else print_Board(gameBoard); } I called my function from the Menu() funciton as: Code: scramble(gameBoard, 0); I know its pretty naiive, and it obviously isn't working as I would hope because my output is as follows: $./a.out Initial configuration [1-Random, 2-Specified configuration]: 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 as you can see my board is still in order and not scrambled. Is there anything in my code that isn't working? I'm thinking it might just be bypassing all my conditions and just printing the array as it was passed by reference initially. TIA Last edited by fcommisso; 10-07-2009 at 12:19 PM.*
fcommisso is offline

10-07-2009, 12:24 PM	#2
kcpilot Registered User Join Date: Jan 2007 Location: Euless, TX Posts: 135	I may be wrong, but if memory serves me correctly, the rand() function may not be returning the type of values you think they are. I know I've found occasions where the value returned was a double value between 0.999999999 and 0.000000000, so to find a value between 0 - 3, you would first have to multiply by 100. Check your documentation for your particular compiler to see what the rand() function is returning.
kcpilot is offline

10-07-2009, 12:39 PM	#4
fcommisso Registered User Join Date: Oct 2009 Posts: 21	not quite here's a sample code I just whipped out to prove my range is indeed form 0 to 3: Code: #include <stdio.h> #include <stdlib.h> int main() { int i; srand(time(NULL)); for ( i = 0; i < 11; ++i) { char i = rand()%4; printf("%d\n", i); } } output: $./a.out 2 3 1 2 0 0 2 1 0 1 2 ~/Desktop $
fcommisso is offline

10-07-2009, 12:51 PM	#6
tabstop and the Hat of Guessing Join Date: Nov 2007 Posts: 8,740	Did you ever fix this? Code: gameBoard[x][y] = gameBoard[x][y]-1;
tabstop is offline

10-07-2009, 12:55 PM	#8
fcommisso Registered User Join Date: Oct 2009 Posts: 21	ok, this thread doens't let me show the spaces how they are displayed in the terminal, but take my word for it that the number 15 in the array is originally to the far right and then after scramble the 15 swaps with the original empty space to the left of it.
fcommisso is offline

10-07-2009, 12:56 PM	#9
fcommisso Registered User Join Date: Oct 2009 Posts: 21	I'm thinking my logic is flawed in the actual swapping of array elements...anyone?
fcommisso is offline

10-07-2009, 12:59 PM	#11
laserlight C++ Witch Join Date: Oct 2003 Location: Singapore Posts: 10,368	Well, considering that what you are doing is just moving the empty space around in the 2D array (and performing relatively expensive operations to find it on each iteration instead of just keeping track of its location), I suspect that the array will never be scrambled no matter what you do. Why not go with what I suggested? EDIT: Oh, but that is not right: moving the empty space around should result in an eventual scrambling of the array, but it is probably just slow since you are only swapping the empty space with adjacent elements, and there are times when the swap does not even happen. __________________ C + C++ Compiler: MinGW port of GCC Build + Version Control System: SCons + Bazaar Look up a C/C++ Reference and learn How To Ask Questions The Smart Way Last edited by laserlight; 10-07-2009 at 01:02 PM.
laserlight is offline

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Adding More Array Elements?	Vermillion	C++ Programming	2	09-14-2008 10:02 PM
coping elements not in array	lord	C++ Programming	2	08-04-2008 07:53 PM
way to check 3 elements of array and set 4th	Syneris	C++ Programming	3	01-09-2006 11:30 AM
Class Template Trouble	pliang	C++ Programming	4	04-21-2005 04:15 AM
A simple question about selecting elements in an array	Unregistered	C++ Programming	1	08-30-2001 10:37 PM