Coding Discussion
Here is one solution not using a Stack
import java.io.*;
import java.util.*;
public class Johnson {
public static void main(String[] args) throws IOException {
Scanner scan = new Scanner(new File("johnson.dat"));
int n = scan.nextInt();
scan.nextLine();
while (n-- > 0) {
String str = scan.nextLine().trim();
char[] arr = str.replaceAll("[^\\[\\}\\{\\)\\(\\]]", "").toCharArray();// only parens etc no extraneous chars
if (!(arr[0] == '(' || arr[0] == '[' || arr[0] == '{')) { // fails if not the right start
System.out.println("Invavid Johnsons");
continue;
}
//call solve which tests for each open char one by one
boolean ok = solve(arr, '{') && solve(arr, '(') && solve(arr, '[');
System.out.println(ok ? "Johnson and Johnson" : "Invalid Johnsons");
}
}
// Basic idea here is to feed an open char (test) into solve() as well as the string. Check to see if open test is followed by a closed (not test),
// check to see if there are ever more closed then opens and handle the edge case at the last char of the string.
static boolean solve(char[] arr, char test) {
int open = 0;
String otherClosed = ""; // to test if we have the wrong closed after an open we first build a string of the wrong closed for test
char closed = '0';
switch (test) {
case '(' -> {
closed = ')';
otherClosed = "}]";
}
case '[' -> {
closed = ']';
otherClosed = ")}";
}
case '{' -> {
closed = '}';
otherClosed = ")]";
}
}
// basic idea is to count test opens as we go from left to right. If at any time there are more test closed than opens return false
// at the end there should be the same number of opens and closed
for (int i = 0; i < arr.length; i++) {
if (arr[i] == closed) {
open--;
}
if (arr[i] == test) {
open++;
if (i == arr.length - 1) {
return false; //if ends with an open, return false
}
if (arr[i + 1] == closed) {
open--;
i++;
} else if (i < arr.length - 1 && otherClosed.contains("" + arr[i + 1])) {
// if we have the wrong closed after open test return false
return false;
}
}
if (open < 0) {
//too many closed
return false;
}
}
//
return open == 0; //
}
}
Maze Traveral
import java.util.*;
import java.util.*;
public class Wyatt {
static int[][] moves = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};// this are the possible moves left and right
public static void main(String[] args) throws IOException {
Scanner scan = new Scanner(new File("wyatt.dat"));
int n = scan.nextInt();
while (n-- > 0) {
int rows = scan.nextInt();
int cols = scan.nextInt();
scan.nextLine();
char[][] arr = new char[rows][cols]; // this is our maze
for (int i = 0; i < rows; i++) {
arr[i] = scan.nextLine().toCharArray();
// System.out.println(Arrays.toString(arr[i])+rows+" "+ cols);
}
//now find start
int startX = -1;
int startY = -1;
loop:
for (int i = 0; i < arr.length; i++)
for (int j = 0; j < arr.length; j++) {
if (arr[i][j] == 'T') {
startX = i;
startY = j;
break loop;
}
}
if(startX == -1){ // there is no start
System.out.println("No Can DO");
continue;
}
// System.out.println("start:"+ startX+ " "+ startY);
boolean ans = solve(arr, startX, startY); // this is the BFS
System.out.println(ans ? "PHForestry" : "No Can Do");
}
}
//BFS for finding if there is a path to P
static boolean solve(char[][] arr, int x, int y) {
boolean[][] visited = new boolean[arr.length][arr[0].length]; //holds true if we have visited a square
visited[x][y] = true; //we have been to the start and it is not the goal
Queue<int[]> queue = new LinkedList<>(); // Key data structure for a BFS , the int[] will store the row and col of a square
queue.offer(new int[]{x, y});
while (!queue.isEmpty()) {
int[] temp = queue.poll(); //pull the last sqare on the path from the queue
// now we will consider all legal moves from temp
for (int i = 0; i < 4; i++) {
int row = moves[i][0] + temp[0];
int col = moves[i][1] + temp[1];
//System.out.println(row +" "+ col);
if (row >= 0 && col >= 0 && row < arr.length && col < arr[0].length && !visited[row][col] && (arr[row][col] == '.' || arr[row][col] == 'P')) {
//System.out.println(row +" "+ col);
if (arr[row][col] == 'P') // are we done?
return true;
//if not we add {row,col} to the queue
visited[row][col] = true;
int[] ar1 = {row, col};
queue.offer(ar1);
}
}
}
//queue is empty, we have failed to get to P
return false;
}
}
Using a Comparator in Modern JAVA
