-
Notifications
You must be signed in to change notification settings - Fork 0
/
Driver_prj2.java
124 lines (96 loc) · 3.77 KB
/
Driver_prj2.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
/** CMPT_435L_800
* Project 2 -- Shortest-Path Word-Melt Solver
* Filename: Driver_prj2.java
* Student Name: Eric Stenton
* Due Date: February 26, 2020
* Version 1.0
*
* This file contains the main function for the Shortest-Path Word-Melt Solver
* project. It uses a breadth-first search in order to find a path from the
* start location to the end location. In this project, the locations are
* words.
*/
import java.util.Scanner;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;
/**
* Driver_prj2
*
* This class implements Location, ArrayQueue, and Maze objects to
* find the solution to a given word-melt 'maze' in system input.
*/
public class Driver_prj2 {
/** main
* parameters:
* args -- the array of command line argument values
* return value: nothing
*
* This function uses a breadth-first search to determine whether a
* solution exists for a given word-melt 'maze' in system input.
* It prints its results.
*/
public static void main(String[] args) {
// Initialize scanner variable
Scanner input = new Scanner(System.in);
// Create maze object and read maze from system input
Maze maze = new Maze();
maze.streamIn(input);
// Initialize array queue
ArrayQueue locationQueue = new ArrayQueue();
// Initialize map
Map<String, String> map = new HashMap<String, String>();
// Initialize starting location
Location startLocation = maze.getStartLocation();
locationQueue.add(startLocation);
map.put(startLocation.word, startLocation.word);
// Check if only start location
if ( maze.isEndLocation(startLocation) ) {
System.out.println("Solution found:");
startLocation.streamOut();
return;
}
// Explore the maze until end location is found or queue is empty
Location neighbor;
Location currentLocation;
while ( locationQueue.getLength() != 0 ){
// Get next location
currentLocation = locationQueue.getFront();
locationQueue.remove();
assert(currentLocation != null);
currentLocation.start();
while ( !currentLocation.isDone() ) {
// Get possible next neighbor
neighbor = currentLocation.nextNeighbor();
assert(neighbor != null);
// Add location to the queue if it is valid and its shortest
// path hasn't been found
if ( maze.isValidLocation(neighbor) &&
!map.containsKey(neighbor.word) ) {
locationQueue.add(neighbor);
map.put(neighbor.word, currentLocation.word);
// Check if neighbor is the end word
if ( maze.isEndLocation(neighbor) ) {
System.out.println("Solution found:");
// Create path using a stack
String currentWord = neighbor.word;
Stack<String> outputStack = new Stack<String>();
outputStack.push(currentWord);
while ( !currentWord.equals(startLocation.word) ) {
currentWord = map.get(currentWord);
outputStack.push(currentWord);
}
// Print the path
while ( !outputStack.empty() ) {
System.out.println( outputStack.pop() );
}
return;
}
}
}
}
// No solution was found
System.out.println("No solution found");
return;
}
}