Java RSS Java RSS

Algorithm Problems

Reply

•
•
Join Date: Dec 2004
Posts: 7
Reputation: Lord Felix is an unknown quantity at this point 
Solved Threads: 0
Lord Felix Lord Felix is offline Offline
Newbie Poster

Algorithm Problems

 
0
  #1
Feb 5th, 2005
Well once again I have some trouble getting my lab to work. I am currently having trouble on an algorithm that is supposed to count the neighbors next to a cell in a Two-dimensional array which is supposed to resemble with the algorithm of Conway's Game of Life. For some reason becuase reason it doesnt seem to be working. I have everything else done and would gladly appriciate some help.

Java Syntax (Toggle Plain Text) 
  1. import apcslib.*; import chn.util.*;
  2.  
  3. public class Life
  4. {
  5. 	boolean alive = false;
  6. 	boolean[][] board = new boolean[21][21];
  7. 	boolean[][] nextBoard = new boolean[21][21];
  8.  
  9. 	FileInput inFile;
  10. 	FileOutput outFile;
  11.  
  12. 	public Life(String input, String output)
  13. 	{
  14. 		inFile = new FileInput(input);
  15.   		outFile = new FileOutput(output);	
  16. 	}
  17.  
  18. 	public void cellConstruct()
  19. 	{
  20. 		int pairNumbers = inFile.readInt();
  21. 		int count = 0;
  22. 		int x, y;
  23. 		int width = 20;
  24.  
  25. 		while (inFile.hasMoreTokens())
  26.   		{
  27.   			x = inFile.readInt();
  28.   			y = inFile.readInt();
  29.   			count++;
  30.  
  31.         	board[x][y] = true;
  32.         }
  33.  
  34. 	}
  35.  
  36. 	public void setAlive(int x, int y, boolean alive)
  37. 	{
  38.     	board[x][y] = true;
  39. 	}
  40.  
  41. 	public boolean CellIsAlive(int i, int j)
  42. 	{
  43. 		return board[i][j];
  44. 	}
  45.  
  46. 	public int countLiveNeighbors (int i, int j)
  47.     {
  48.     	int limit = 21 - 1;
  49.     	int count = 0;
  50.     	for (int ii = i - 1; ii <= i + 1; ii++)
  51.     	{
  52.       		for (int jj = j - 1; jj <= j + 1; jj++)
  53.       			{
  54. 					if (ii == i && jj == j) continue;
  55. 						if (ii < 0 || ii > limit) continue;
  56. 							if (jj < 0 || jj > limit) continue;
  57. 								if (CellIsAlive (ii, jj) == true) count++;
  58.       			}
  59.     	}
  60.     	return count;
  61.     }
  62.  
  63.   public void execute(int numberSteps)
  64.   {
  65.   	int numberOfSteps = numberSteps;
  66.   	int numberOfNeighbors;
  67.  
  68.     	for (int step = 0; step < numberOfSteps; step++)
  69.     	{
  70.     		for (int row = 0; row < nextBoard.length; row++)
  71.     		{
  72.       			for (int col = 0; col < nextBoard[row].length; col++)
  73.       			{
  74.       				nextBoard[row][col] = board[row][col];
  75.       			}
  76.       		}
  77.  
  78.       		// Set up an empty board and fill it with value for next step
  79.       		for (int i = 0; i < 21; i++)
  80.         	{	
  81.         		for (int j = 0; j < 21; j++)
  82.         		{
  83.           			numberOfNeighbors = countLiveNeighbors(i, j);
  84.           			if (CellIsAlive(i, j))
  85. 	  				{
  86. 	    				if (numberOfNeighbors == 2 || numberOfNeighbors == 3)
  87. 	      					nextBoard[i][j] = true;
  88. 	  				}
  89. 	  				else // cell is dead
  90. 	    				if (numberOfNeighbors != 3 || numberOfNeighbors != 2)
  91. 	     					nextBoard[i][j] = false;
  92.  
  93.         		}
  94. 			}
  95.  
  96.       		for (int row = 0; row < board.length; row++)
  97.     		{
  98.       			for (int col = 0; col < board[row].length; col++)
  99.       			{
  100.       				board[row][col] = nextBoard[row][col];
  101.       			}
  102.       		}
  103.  
  104.       		print();
  105.       		outFile.close();
  106.     	}
  107.     }
  108.  
  109.   	public void print ()
  110.   	{
  111.   		outFile.println(Format.left("      1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20",4));
  112.   		outFile.println("");
  113.  
  114.    	 	for (int row = 1; row < board.length; row++)
  115.     	{
  116.     		outFile.print(Format.left(row,4));
  117.  
  118.       		for (int col = 1; col < board[row].length; col++)
  119.       		{
  120.       			if (board[row][col] == true)
  121.       			{
  122.       				outFile.print(Format.right("*",3));
  123.       			}
  124.       			else
  125. 				{
  126.         			outFile.print(Format.right(" ",3));
  127.         		}
  128.         	}
  129.       	outFile.println();
  130.     	}
  131.   	}
  132. }
  133.  
  134. class LifeOutput
  135. {
  136. 	public static void main (String args[])
  137.   	{
  138.   		ConsoleIO input = new ConsoleIO();
  139.   		int numberOfSteps;
  140.   		String fileInput;
  141.  
  142.   		System.out.println("Welcome to Life.");
  143.   		System.out.println("");
  144.   		System.out.println("Please enter name of the file to be read: ");
  145.   		fileInput = input.readLine();
  146.   		System.out.println("Please enter the # of generations to elaspe: ");
  147.   		numberOfSteps = input.readInt();
  148.   		System.out.println("");
  149.   		System.out.println("Executing....");
  150.   		System.out.println("");
  151.  
  152.     	Life lifeS = new Life(fileInput,"fileout.txt");
  153.  
  154.     	lifeS.cellConstruct();
  155.     	lifeS.execute(numberOfSteps);
  156.   	}
  157. }

The lab to this program can be found 'Here'

Once again thanks in advance,

Lord Felix

PS: I figured out the error with my previous post so thanks anyways.
Reply With Quote Quick reply to this message  
•
•
Join Date: Nov 2004
Posts: 6,143
Reputation: jwenting is just really nice jwenting is just really nice jwenting is just really nice jwenting is just really nice 
Solved Threads: 212
Team Colleague
jwenting's Avatar
jwenting jwenting is offline Offline
duckman

Re: Algorithm Problems

 
0
  #2
Feb 5th, 2005
•
•
•
•
For some reason becuase reason it doesnt seem to be working
huh? What are you trying to say here?

What isn't working and why isn't it working.
What is it doing and what is it supposed to be doing?
Reply With Quote Quick reply to this message  
•
•
Join Date: Dec 2004
Posts: 7
Reputation: Lord Felix is an unknown quantity at this point 
Solved Threads: 0
Lord Felix Lord Felix is offline Offline
Newbie Poster

Re: Algorithm Problems

 
0
  #3
Feb 5th, 2005
Sorry for making it unclear. I have to write a program that simulates the game of Life using Two-Dimensional arrays. The size of the grid will be a square 20 x 20 (Which is size of the Two-Dimensional Array). My program is supposed to read the locations of the cells that are in a text file and then store them into the Two-Dimension array. Once stored I have to use an algorithm to read the Two-Dimensional array and search for cells that have neighboring cells and apply Conway's Game of Life rules to them for a set amount of generations (Loops).

His rules of the Game are here if you arn't familiar with them:

•
•
•
•
A "neighbor" of a cell is defined as any cell touching that cell, for example the eight blue cells in the diagram are the neighbors of the cell in the middle.

Every empty cell with three living neighbors will come to life in the next generation (a "birth").

Any cell with one or zero neighbors will die of loneliness, while any cell with four or more neighbors will die from overcrowding (a "death").

Any cell with two or three neighbors will live into the next generation (no change).

All births and deaths occur simultaneously.
Well the problem I have my the code is that my method to count the number of cells that surround a cell is either wrong or not functional. I need someone to go over my code to see if Im using my methods write and help me fix my "public int countLiveNeighbors (int i, int j)" method.

Sorry for confusion,

Lord Felix
Reply With Quote Quick reply to this message  
•
•
Join Date: Nov 2004
Posts: 6,143
Reputation: jwenting is just really nice jwenting is just really nice jwenting is just really nice jwenting is just really nice 
Solved Threads: 212
Team Colleague
jwenting's Avatar
jwenting jwenting is offline Offline
duckman

Re: Algorithm Problems

 
0
  #4
Feb 5th, 2005
Java Syntax (Toggle Plain Text) 
  1. 	public int countLiveNeighbors (int i, int j)
  2.     {
  3.     	int limit = 21 - 1;
  4.     	int count = 0;
  5.     	for (int ii = i - 1; ii <= i + 1; ii++)
  6.     	{
  7.       		for (int jj = j - 1; jj <= j + 1; jj++)
  8.       		{
  9. 			if (ii == i && jj == j) continue;
  10. 			if (ii < 0 || ii > limit) continue;
  11. 			if (jj < 0 || jj > limit) continue;
  12. 			if (CellIsAlive (ii, jj) == true) count++;
  13.       		}
  14.     	}
  15.     	return count;
  16.     }

looks correct.
Your actual problem is over here:
Java Syntax (Toggle Plain Text) 
  1.       for (int i = 0; i < 21; i++)
  2.       {	
  3.         	for (int j = 0; j < 21; j++)
  4.         	{
  5.           		numberOfNeighbors = countLiveNeighbors(i, j);
  6.           		if (CellIsAlive(i, j))
  7. 	 	{
  8. 	    		if (numberOfNeighbors == 2 || numberOfNeighbors == 3)
  9. 	      			nextBoard[i][j] = true;
  10. 	  	}
  11. 	  	else // cell is dead
  12. 	    		if (numberOfNeighbors != 3 || numberOfNeighbors != 2)
  13. 	     			nextBoard[i][j] = false;
  14.  
  15.         	}
  16. }

This doesn't take into account that cells can come alive if they're dead.
While you ARE taking celldeath into account on life cells, you're not taking cellbirth into account therefore your simulation will either die quickly or reach a single stable and unchanging state.

change
Java Syntax (Toggle Plain Text) 
  1. 	  	else // cell is dead
  2. 	    		if (numberOfNeighbors != 3 || numberOfNeighbors != 2)
  3. 	     			nextBoard[i][j] = false;
to take that condition into account.
Remember that the default values for an array of booleans are all false, so setting them to false is not needed.
But explicitly setting them to true when they should be IS needed, and you're not doing that.

Also I don't think you need to prefill the board with the old position.
Just initialising the array and setting those positions to true that hold life cells in the new position based on calculating the count and status from the old position should be enough.
This will remove an entire loop from your simulation, possibly speeding it up quite a bit.
Reply With Quote Quick reply to this message  
•
•
Join Date: Nov 2004
Posts: 6,143
Reputation: jwenting is just really nice jwenting is just really nice jwenting is just really nice jwenting is just really nice 
Solved Threads: 212
Team Colleague
jwenting's Avatar
jwenting jwenting is offline Offline
duckman

Re: Algorithm Problems

 
0
  #5
Feb 5th, 2005
a P.S.: be careful with indentation and braces.
Having it poorly done (like in your code, with braces not lined up and indenting with both tabs and spaces interspersed) can make code a lot harder to read.
I had to reformat your code to be able to quickly see how it is structured.
Reply With Quote Quick reply to this message  
•
•
Join Date: Dec 2004
Posts: 7
Reputation: Lord Felix is an unknown quantity at this point 
Solved Threads: 0
Lord Felix Lord Felix is offline Offline
Newbie Poster

Re: Algorithm Problems

 
0
  #6
Feb 5th, 2005
Thanks jwenting, that helped alot. As for the messy coding, I initially had to copy and paste the code from the computer in my school so it messed up the format of the coding. Sorry for that inconveinance. Ill go revise that part of the code. :cheesy:

Lord Felix
Reply With Quote Quick reply to this message  
•
•
Join Date: Dec 2004
Posts: 7
Reputation: Lord Felix is an unknown quantity at this point 
Solved Threads: 0
Lord Felix Lord Felix is offline Offline
Newbie Poster

Re: Algorithm Problems

 
0
  #7
Feb 7th, 2005
Alright, I revised that part of the code:

Java Syntax (Toggle Plain Text) 
  1. for (int i = 0; i < 21; i++)
  2.       		{	
  3.         		for (int j = 0; j < 21; j++)
  4.         		{
  5.           			numberOfNeighbors = countLiveNeighbors(i, j);
  6.           			if (CellIsAlive(i, j) == true)
  7. 				 	{
  8. 			    		if (numberOfNeighbors <= 1 || numberOfNeighbors > 3)
  9. 			      			nextBoard[i][j] = false;
  10. 	  				}
  11.  
  12. 	 				if (CellIsAlive(i, j) == false)
  13. 	 				{
  14. 	 					if (numberOfNeighbors == 3)
  15. 	 						nextBoard[i][j] = true;
  16. 	 				}
  17.  
  18. 				}
  19. 			}

The program is stuck on the first generation however.
Reply With Quote Quick reply to this message  
•
•
Join Date: Dec 2004
Posts: 7
Reputation: Lord Felix is an unknown quantity at this point 
Solved Threads: 0
Lord Felix Lord Felix is offline Offline
Newbie Poster

Re: Algorithm Problems

 
0
  #8
Feb 9th, 2005
Aliright, I figured out that I closed the file too soon and thats what cuased the program to appear to be stuck at the first generation. The only problem I have right now is that cells that do not have neighbors are not dying in the next generation. I did some debugging and it seems that the program is reading in the cells that have no neighbors to have 2 neighbors. With this in mind, I think am currently looking over the program to see why this is so. Help would gladly be accepted as I am wanting to get it done.

Thanks,

Lord Felix

PS: I would edit my posts if there was a funtion to edit even after one day, sorry for the triple post.
Reply With Quote Quick reply to this message  
Reply

Quick Reply to Thread
This thread is more than three months old.
Perhaps start a new thread instead?
•
•
•
•
•
•
•
•
Message:
•
•
•
•



Similar Threads
Other Threads in the Java Forum
Thread Tools Search this Thread



-xlint add android api applet application applications array arrays automation bank bi binary blackberry bluetooth chat class client code compile compiler component database development digit eclipse equation error event fractal freeze functiontesting game gameprogramming givemetehcodez graphics gui health html hyper ide idea image infinite input int integer j2me java javame javaprojects jetbrains jni jpanel jtable julia learningresources linux list login loop main map method methods mobile myregfun netbeans newbie nonstatic notdisplaying pearl problem program programming project qt recursion scanner screen scrollbar server set sms sort sorting spamblocker sql sqlserver string superclass swing system text-file thread threads tree variablebinding windows xor
About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC