6 Replies - 3020 Views - Last Post: 16 November 2012 - 05:39 PM Rate Topic: -----

#1 Bigredaltoid  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 30-October 12

Having a lot of trouble on a Java Maze Program using Stacks...

Posted 16 November 2012 - 11:42 AM

Hi all - so the end goal is to have a program that reads in the size of a 2d array, the contents of the 2d array, and the starting coordinates and then navigates through the maze using stacks.

The text file looks like so:

6 6
5 5 5 5 5 5
0 0 0 0 0 5
5 5 0 5 0 5
5 5 0 5 5 5
5 0 0 0 0 0
5 5 5 5 5 5
1 0

I have written code to read the array size and the contents, which is as follows:

package programfour;

import java.util.Scanner;
import java.io.File;
import java.io.FileNotFoundException;

public class ArrayReader {
	
	public static void main(String[] args) throws FileNotFoundException{
		
	File inputFile = new File("maze1.txt");
	Scanner sc = new Scanner(inputFile);
	int arrayRowSize = sc.nextInt();
	int arrayColumnSize = sc.nextInt();
	int[][] mazeArray = new int[arrayRowSize][arrayColumnSize];
	
	

	for(int i = 0; i < arrayRowSize; i++){
		for(int j = 0; j < arrayColumnSize; j++){
			mazeArray[i][j] = sc.nextInt();
				
			}
			
		}
		sc.nextLine();
	

	for(int i = 0; i < mazeArray.length; i++){
		for(int j = 0; j < mazeArray[i].length; j++){
			System.out.print(mazeArray[i][j]);
		}
		System.out.println();
	}
	
	sc.close();
			
	}
	

}



A stack class and an emptystackexception class was provided to us as is as follows:

package stackpackage;

import java.util.LinkedList;

public class Stack {
	private LinkedList stack;
		
	public Stack() {
		stack = new LinkedList();
	}
	
	public boolean isEmpty() {
		return stack.size() == 0;
	}
	
	public Object pop() {
		if (isEmpty()) {
			throw new EmptyStackException();
		}
		return stack.removeFirst();
	}
	
	public void push(Object obj) {
		stack.addFirst(obj);
	}
	
	public Object peek() {
		if (isEmpty()) {
			throw new EmptyStackException();
		}
		return stack.peek();
	}
}


public class EmptyStackException extends RuntimeException {
	public EmptyStackException(String msg) {
		super(msg);
	}
	
	public EmptyStackException() {
		super();
	}
}


And we have also had a Coordinate class given to us...:

package programfour;

import stackpackage.*;

public class Coordinate {
	private Integer row;
	private Integer column;
	
	public Coordinate(Integer row, Integer column){
		this.row = row;
		this.column= column;
	}
	
	public void setRow(Integer row){
		this.row = row;
	}
	
	public void setColumn(Integer column){
		this.column = column;
	}
	
	public Integer getRow(){
		return row;
	}
	
	public Integer getColumn(){
		return column;
	}
	
	public String toString(){
		return "<" + row.toString() + "," + column.toString() + ">";
	}

}



I am at a complete loss of what the next step here would be and if someone could point me in the right direction I would be ecstatic.

Is This A Good Question/Topic? 0
  • +

Replies To: Having a lot of trouble on a Java Maze Program using Stacks...

#2 Bigredaltoid  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 30-October 12

Re: Having a lot of trouble on a Java Maze Program using Stacks...

Posted 16 November 2012 - 11:48 AM

Edit: The program should solve a maze by using a stack to keep track of the cells that have been visited. It should change the value of the starting cell from 0 to 1..and I need to make an instance of the Coordinate class that is related to the starting cell and push it onto the stack..I am so confused this is horrible.
Was This Post Helpful? 0
  • +
  • -

#3 GregBrannon  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2205
  • View blog
  • Posts: 5,239
  • Joined: 10-September 10

Re: Having a lot of trouble on a Java Maze Program using Stacks...

Posted 16 November 2012 - 12:14 PM

The stack is used to keep track of the path taken through the maze, like Hansel and Gretel dropping bread crumbs. Instead of bread crumbs, each location visited in the maze (coordinate) will be pushed to the stack. Then, if a dead end is encountered, the solver backtracks to the last location in the maze where multiple moves existed.

Along the way, it's helpful to keep track of:

locations visited (coordinates)
locations visited with moves available

Those characteristics can be made part of your Coordinate class or an extension of Coordinate, if you're not allowed to change it. But there are other ways to do the same thing.
Was This Post Helpful? 0
  • +
  • -

#4 Bigredaltoid  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 30-October 12

Re: Having a lot of trouble on a Java Maze Program using Stacks...

Posted 16 November 2012 - 01:11 PM

So the starting Coordinate is 1 0 (from the File...)..I am confused as to how I would read these into the Coordinate class to get the starting position..and we are not allowed to change the Coordinate class at all.
Was This Post Helpful? 0
  • +
  • -

#5 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8347
  • View blog
  • Posts: 31,910
  • Joined: 06-March 08

Re: Having a lot of trouble on a Java Maze Program using Stacks...

Posted 16 November 2012 - 01:16 PM

As far as I can see, the Coordinate class is just to hold togeter a X and a Y

Usaually we use the Point class for that purpose
http://docs.oracle.c.../awt/Point.html

The Coordinate objects can be push/pop from your Stack to remember from where you come from
Was This Post Helpful? 0
  • +
  • -

#6 Bigredaltoid  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 30-October 12

Re: Having a lot of trouble on a Java Maze Program using Stacks...

Posted 16 November 2012 - 01:21 PM

Would the Point class work with a 2D Array of ints? I see that that the Point class returns in doubles.
Was This Post Helpful? 0
  • +
  • -

#7 Bigredaltoid  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 30-October 12

Re: Having a lot of trouble on a Java Maze Program using Stacks...

Posted 16 November 2012 - 05:39 PM

Alright so I have made a significant amount of progress on the code, however I am still not getting exactly what I should be.

package programfour;


import java.util.Scanner;
import java.io.File;
import java.io.FileNotFoundException;
import stackpackage.*;

public class MazeArray {
	public static void main(String[] args) throws FileNotFoundException{
		File inputFile = new File("maze1.txt");
		Scanner sc = new Scanner(inputFile);
		int maze[][] = null;
		
		maze = createMaze(sc, maze);
		
		mazePathFinder(sc, maze);
		printMaze(maze);

	}
	
	public static int[][] createMaze(Scanner sc, int[][] maze){
		int arrayRowSize = sc.nextInt();
		int arrayColumnSize = sc.nextInt();
		maze = new int[arrayRowSize][arrayColumnSize];
		for(int i = 0; i < arrayRowSize; i++){
			for(int j = 0; j < arrayColumnSize; j++){
				maze[i][j] = sc.nextInt();
				}
		}
		return maze;
	}
	
	
	public static void printMaze(int[][] maze){
		for(int i = 0; i < maze.length; i++){
			for(int j = 0; j < maze[i].length; j++){
				System.out.print(maze[i][j]);
			}
			System.out.println();
		}
	}
	
	public static void mazePathFinder(Scanner sc, int[][] maze){
		Stack mazeStack = new Stack();
		int count = 0;
		boolean done = false;
		String rowCoordinates = sc.next();
		String columnCoordinates = sc.next();
		int row = Integer.parseInt(rowCoordinates);
		int column = Integer.parseInt(columnCoordinates);
		Coordinate startingCoord = new Coordinate(row, column);
		mazeStack.push(startingCoord);
		count++;
		maze[row][column] = 1;
		
		//Looks North, if the value is a 0, converts it to 1 and pushes coordinates onto the stack
		try{
			if(maze[row - 1][column] == 0){
				row -= 1;
				maze[row][column] = 1;
				Coordinate secondCoord = new Coordinate(row, column);
				mazeStack.push(secondCoord);
				count++;
			}
			
		}
		catch(ArrayIndexOutOfBoundsException aiooe){
			}
		//Looks East
		try{
			if(maze[row][column + 1] == 0){
				column += 1;
				maze[row][column] = 1;
				Coordinate secondCoord = new Coordinate(row, column);
				mazeStack.push(secondCoord);
				count++;
				
			}
		}
		catch(ArrayIndexOutOfBoundsException aiooe){
		}
		//Looks South
		try{
			if(maze[row + 1][column] == 0){
				row += 1;
				maze[row + 1][column] = 1;
				Coordinate secondCoord = new Coordinate(row, column);
				mazeStack.push(secondCoord);
				count++;
			}
		}
		catch(ArrayIndexOutOfBoundsException aiooe){
		}
		//Looks West
		try{
			if(maze[row][column - 1] == 0){
				column -= 1;
				maze[row][column] = 1;
				Coordinate secondCoord = new Coordinate(row, column);
				mazeStack.push(secondCoord);
				count++;
			}
		}
		catch(ArrayIndexOutOfBoundsException aiooe){
		}
		
		try{
			while(!done){
				Coordinate nextCoord = new Coordinate(row, column);
				//Pushes nextCoord to stack if == 0
				if (maze[row - 1][column] == 0){
					maze[row - 1][column] = 1;
					row -= 1;
					mazeStack.push(nextCoord);
					count++;
					continue;
					
				}
				//Pushes nextCoord to stack if == 0
				else if(maze[row][column + 1] == 0){
					maze[row][column + 1] = 1;
					column += 1;
					mazeStack.push(nextCoord);
					count++;
					continue;
				}
				
				//Pushes nextCoord to stack if == 0
				else if(maze[row + 1][column] == 0){
					maze[row + 1][column] = 1;
					row += 1;
					mazeStack.push(nextCoord);
					count++;
					continue;
				}
				 //Pushes nextCoord to stack if == 0
				else if(maze[row][column - 1] == 0){
					maze[row][column - 1] = 1;
					column -= 1;
					mazeStack.push(nextCoord);
					count++;
					continue;
				}
				mazeStack.pop();
				row = nextCoord.getRow();
				column = nextCoord.getColumn();
				break;
			}
		}
		catch(ArrayIndexOutOfBoundsException aiooe){
			done = true;
		}
		
		Stack reorderCoords = new Stack();
		for(int i = 0; i < count - 1; i++){
			reorderCoords.push(mazeStack.pop());
		}
		
		for(int i = 0; i < count - 1; i++){
			System.out.println(reorderCoords.pop());
		}
	}
			
	}
	
			
		






The output is as follows:

<1,0>
<1,1>
<1,1>
<1,2>
<1,3>

The maze , after the program runs is:
555555
111115
550515
550555
500000
555555

I can see that the program is stuck when it reaches coordinates < 2, 4 >..but I am not sure how I can fix it..any tips?
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1