Question & Answer: For this last programming project, you will be imp… (3 bookmarks) For this last programming project, you will…..

Main.java
———————————————————
import java.io.File;
import java.io.FileNotFoundException;
import java.util.InputMismatchException;
import java.util.Scanner;

public class Main {
public static void main(String[] args)
{
try(Scanner in = new Scanner(System.in))
{
String fileName = args[0];
TheMaze maze =readFile(fileName);
mazeDisplay(maze);
//Randomly generate a new maze
System.out.println(“Maze generator. Input the maze length: n =”);
int mazeLength = in.nextInt();
TheMaze randomMaze = new TheMaze(mazeLength);
randomMaze.mazeGeneration();
mazeDisplay(randomMaze);
}
catch(InputMismatchException e)
{
System.out.println(“Inappropriate Input”);
}
}

public static TheMaze readFile(String fileName)
{
try(Scanner in = new Scanner(new File(fileName)))
{
TheMaze maze = new TheMaze(in.nextInt());
int i =0;
while(in.hasNext())
{
maze.setRoom(i);
for(int count = 0;count < 4;count++)
{
int open = in.nextInt();
if(open == 0) maze.getRoom(i).openDoor(count);
}
i++;
}
return maze;
}
catch(FileNotFoundException e)
{
System.out.println(“File Not Found”);
}
return null;
}
public static void mazeDisplay(TheMaze m)
{
System.out.println(“Structure of the maze:”);
m.drawMaze();
System.out.println(“Breadth First Search:”);
m.BFSSolve();
System.out.println(“Depth First Search:”);
m.DFSSolve();
}
}
————————————————————————————-
Room.java
——————————————–
import java.util.Arrays;

public class Room {
private int index;
private int[] doors;
private boolean visited;
public Room()
{
this.index=-1;
doors = new int[4];
Arrays.fill(doors, 1);
visited=false;
}
public void setIndex(int index)
{
this.index=index;
}
public int getIndex()
{
return index;
}
public boolean checkDoor(int direction)
{
return doors[direction]==0;
}
public void refresh()
{
visited = false;
}

public String roomShape()
{

String result = “*–*n| |n*–*”;
result =”*”;
if(doors[0]==1) result+=”–*n”;
else           result+=” *n”;
if(this.visited)
{
if(doors[3]==1) result+=”|XX”;
else           result+=” XX”;
}
else
{
if(doors[3]==1) result+=”| “;
else           result+=”   “;
}
if(doors[2]==1) result+=”|n*”;
else           result+=” n*”;

if(doors[1]==1) result+=”–*”;
else           result+=” *”;
return result;
}

public void visit()
{
visited=true;
}

public boolean isVisited()
{
return visited;
}

public void openDoor(int direction)
{
this.doors[direction]=0;
}
}
——————————————————————————–
TheLinkedList.java
————————————–
public class TheLinkedList {
class Node {
private String data;
private Node next;
private Node prev;

public Node(String data)
{
this.data=data;
}
}
private Node first;
private Node last;

public TheLinkedList()
{
first = null;
last = null;
}public void a()
{
System.out.println(“a1″);
}

public boolean insertFirst(String data)
{
boolean result = false;
try{
Node newNode = new Node(data);
if(this.isEmpty())
{
last = newNode;
}
else
{
newNode.next=first;
first.prev=newNode;
}
first = newNode;
result = true;
}
catch (Exception e)
{
}
return result;

}

public boolean insertLast(String data)
{
boolean result = false;
try{
Node newNode = new Node(data);
if(this.isEmpty())
{
first = newNode;
}
else
{
last.next=(newNode);
newNode.prev=last;
}
last = newNode;
result = true;
}
catch(Exception e)
{
}
return result;
}

public String removeFirst()
{
if(!this.isEmpty())
{
if(first.next==null)
last = null;
String result = first.data;
first = first.next;
if (first!=null)first.prev=null;
return result;
}
else return null;
}

public String removeLast()
{
if(!this.isEmpty())
{
if(last.prev==null)
{
first = null;
}
String result = last.data;
last = last.prev;
if(last!=null)last.next=null;
return result;
}
else return null;
}

public boolean isEmpty()
{
return first == null;
}

public String getFirst()
{
if(!this.isEmpty())
{
String result = first.data;
return result;
}
else return null;
}

public String toString ()
{
String result=””;
Node current = first;
while(current != null)
{
result+=” “+current.data;
current = current.next;
}
return result;
}
}
——————————————————————–
TheMaze.java
——————————-
import java.util.Random;

public class TheMaze {
private int mazeLength;
private Room[] theRooms;

public TheMaze(int mazeLength)
{
this.mazeLength=mazeLength;
theRooms = new Room[mazeLength*mazeLength];
}

public void setRoom(int number)
{
theRooms[number] = new Room();
}

public Room getRoom(int number)
{
return theRooms[number];
}
public void mazeReconstruct()
{
//Create a new maze
theRooms = new Room[mazeLength*mazeLength];
for(int count=0;count<mazeLength*mazeLength;count++)
{
theRooms[count] = new Room();
}
//Open the North door of the entrance and the South door of the exit
theRooms[0].openDoor(0);
theRooms[mazeLength*mazeLength-1].openDoor(1);
}

public void mazeGeneration()
{
this.mazeReconstruct();
//While the entrance and the exit is not on the same set
while (this.find(0)!=this.find(mazeLength*mazeLength-1))
{
//The method randomly generate an array of two adjacent room numbers
int[] randomRooms = this.findRandomPair();
int i = randomRooms[0];
int j = randomRooms[1];
//If the two rooms are not on the same set, union the sets and open the door between the rooms
if(this.find(i)!=this.find(j))
{
this.connectRooms(i, j);
this.union(this.find(i),this.find(j));
}
}
}

public int find(int number)
{
int index = theRooms[number].getIndex();
if(index<0) return number;
else return this.find(index);

}

public void union(int root1, int root2)
{
int firstIndex = theRooms[root1].getIndex();
int secondIndex = theRooms[root2].getIndex();
if(secondIndex<firstIndex)
{
theRooms[root2].setIndex(firstIndex+secondIndex);
theRooms[root1].setIndex(root2);
}
else
{
theRooms[root1].setIndex(firstIndex+secondIndex);
theRooms[root2].setIndex(root1);
}
}

public void connectRooms(int first, int second)
{
int subtraction = first – second;
//The second room is north of the first room
if(subtraction==mazeLength)
{
theRooms[first].openDoor(0);
theRooms[second].openDoor(1);
}
//The second room is south of the first room
if(subtraction==-mazeLength)
{
theRooms[first].openDoor(1);
theRooms[second].openDoor(0);
}
//The second room is east of the first room
if(subtraction==-1)
{
theRooms[first].openDoor(2);
theRooms[second].openDoor(3);
}
//The second room is west of the first room
if(subtraction==1)
{
theRooms[first].openDoor(3);
theRooms[second].openDoor(2);
}
}

public int[] findRandomPair()
{
Random random = new Random();
int[] result = new int[2];
//Generate the first room number between 0 and n^2-1
int firstRoom = random.nextInt(mazeLength*mazeLength);
result[0]=firstRoom;
//The method returns an array of maximum four rooms adjacent to the first, in N, S, E and W
//The walls are marked “-1″
int[] adjacentRooms = this.findAdjacentRooms(firstRoom);
int adjacent;
//Randomly choose a room in the adjacent rooms
do
{
adjacent = random.nextInt(4);
}
while(adjacentRooms[adjacent]<0);

result[1]=adjacentRooms[adjacent];
return result;
}

public int[] findAdjacentRooms(int center)
{
int[] result ={-1,-1,-1,-1};
//If the room is bounded north
if(!this.isNorthBound(center)) result[0]=center-mazeLength;
//If the room is bounded south
if(!this.isSouthBound(center)) result[1]=center+mazeLength;
//If the room is bounded east
if(!this.isEastBound(center)) result[2]=center+1;
//If the room is bounded west
if(!this.isWestBound(center)) result[3]=center-1;
return result;
}

public boolean isNorthBound(int number)
{
return number<mazeLength;
}

public boolean isSouthBound(int number)
{
return number>mazeLength*(mazeLength-1)-1;
}

public boolean isEastBound(int number)
{
for(int count = 1;count<=mazeLength;count++)
{
if(number==count*mazeLength-1) return true;
}
return false;
}

public boolean isWestBound(int number)
{
for(int count = 0;count<mazeLength;count++)
{
if(number==count*mazeLength) return true;
}
return false;
}

public void refreshVisit()
{
for(Room room: theRooms)
{
room.refresh();
}
}

public void BFSSolve()
{
TheQueue Q = new TheQueue();
Q.enqueue(0+””);
theRooms[0].visit();
String result=”0″;
String path = “”;
while(!Q.isEmpty())
{
Q.dequeue();
int i = Integer.parseInt(Q.getData());

int[] adjacentRooms =this.findAdjacentRooms(i);
for(int count=0;count<4;count++)
{
int roomNumber = adjacentRooms[count];
if(roomNumber>=0&&this.adjacentPassage(i, roomNumber, count)&&!theRooms[roomNumber].isVisited())
{
result+=” “+roomNumber;
Q.enqueue(roomNumber+””);
theRooms[roomNumber].visit();
//If the search find the exit, print the path found
if(roomNumber==mazeLength*mazeLength-1)
{
System.out.println(“Rooms visited by BFS: “+result);
path = this.findPath(result);
System.out.println(“This is the path (in reverse): “+this.findPath(result));
break;
}
}
}

}
//Refresh the visited rooms and draw the maze path
this.refreshVisit();
this.drawSolvedMaze(path);

}

public void DFSSolve()
{
TheStack Q = new TheStack();
Q.push(0+””);
theRooms[0].visit();
String result=””;
String path=””;
while(!Q.isEmpty())
{
Q.pop();
int i = Integer.parseInt(Q.getData());
result+=” “+i;
int[] adjacentRooms =this.findAdjacentRooms(i);
//If the search find the exit, print the path found
if(i==mazeLength*mazeLength-1)
{
result = result.substring(1);
System.out.println(“Rooms visited by DFS: “+result);
path = this.findPath(result);
System.out.println(“This is the path (in reverse): “+path);
break;
}
for(int count=0;count<4;count++)
{
int roomNumber = adjacentRooms[count];
if(roomNumber>=0&&this.adjacentPassage(i, roomNumber, count)&&!theRooms[roomNumber].isVisited())
{

Q.push(roomNumber+””);
theRooms[roomNumber].visit();

}
}

}
//Refresh the visited rooms and draw the maze path
this.refreshVisit();
this.drawSolvedMaze(path);

}

public boolean adjacentPassage(int first, int second,int direction)
{
//Check if the rooms are adjacent
int[] adjacentRooms = this.findAdjacentRooms(first);
//Check if the doors connecting the two rooms are connected
if(second == adjacentRooms[direction])
{
if(theRooms[first].checkDoor(direction)&&theRooms[second].checkDoor(Math.floorMod(5-direction, 4)))
{
return true;
}
}
return false;
}

public String findPath(String search)
{
String[] rooms = search.split(“\s+”);
String result = rooms[rooms.length-1];
int before = Integer.parseInt(result);
for(int count = rooms.length-2;count >=0;count–)
{
//Start from the exit room
int current = Integer.parseInt(rooms[count]);
int direction = 0;
//Check if the current room is connected to the “before” room
while(direction<4)
{
if(this.adjacentPassage(before, current, direction))
{
result+=” “+current;
before = current;
break;
}
direction++;
}
}
return result;
}

public void drawSolvedMaze(String path)
{
String[] rooms = path.split(” “);
//Visit the rooms whose number appear in the given path
for(String room: rooms)
{
theRooms[Integer.parseInt(room)].visit();
}
this.drawMaze();
this.refreshVisit();
}

public void drawMaze()
{

for(int i = 0;i<mazeLength;i++)
{
String result=””;
for(int j=0;j<mazeLength;j++)
{
//Draw the rooms from left to right, from top to bottom
int number = i*mazeLength+j;
//Concatenate the room drawings
result = connectString(result, theRooms[number].roomShape());
}
System.out.print(result);
}

}

public String connectString(String s1, String s2)
{
String result=””;
if(s1.length()==0) return s2;
int n = (s1.length()-2)/12;
result+=s1.substring(0,4*n)+s2.substring(0, 4)+”n”;
result+=s1.substring(4*n+1, 8*n+1)+s2.substring(5, 9)+”n”;
result+=s1.substring(8*n+2,12*n+2)+s2.substring(10, 14)+”n”;
return result;
}

}
—————————————————————
TheQueue.java
——————————–
public class TheQueue extends TheLinkedList
{
private TheLinkedList queueList;
private String topData;

public void a()
{
System.out.println(“a2”);
}

public TheQueue()
{
queueList = new TheLinkedList();
}
public boolean isEmpty()
{
return queueList.isEmpty();
}
public boolean enqueue(String data)
{
return queueList.insertLast(data);
}
public boolean dequeue()
{
topData =this.queueList.removeFirst();
return topData!=null;

}
public String getData()
{
return topData;
}

public void print ()
{
System.out.println(“Contents of queue: “+queueList.toString());
}

}
————————————————————————
TheStack.java
—————————————
public class TheQueue extends TheLinkedList
{
private TheLinkedList queueList;
private String topData;

public void a()
{
System.out.println(“a2”);
}

public TheQueue()
{
queueList = new TheLinkedList();
}
public boolean isEmpty()
{
return queueList.isEmpty();
}
public boolean enqueue(String data)
{
return queueList.insertLast(data);
}
public boolean dequeue()
{
topData =this.queueList.removeFirst();
return topData!=null;

}
public String getData()
{
return topData;
}

public void print ()
{
System.out.println(“Contents of queue: “+queueList.toString());
}

}
————————————————————–
maze.text
——————————–
5
0 0 1 1
1 1 0 1
1 0 1 0
1 1 0 1
1 0 1 0
0 0 1 1
1 1 0 1
0 1 0 0
1 0 1 0
0 0 1 0
0 1 0 1
1 1 0 0
1 0 0 0
0 0 0 0
0 0 1 0
1 1 0 1
1 0 1 0
0 0 1 1
0 0 1 1
0 1 1 1
1 1 0 1
0 1 0 0
0 1 1 0
0 1 0 1
1 0 1 0