The code included below was written in response to a programming exercise that was sent to me by a company that I am applying to. The purpose of the code is explained at this link.
This code passes 89% of all correctness tests for finding valid meeting locations as specified within the programming exercise information sheet. I am aware of the fact that my code is full of software debt and is in need of re-factoring such that it is more easily maintained, updated, and debugged. Please provide any advice or words of wisdom to provide for improving on this code with respect to readability and functionality (passing 100% of all correctness tests).
Main.java
/** This class when compiled runs a Depth First Search for an undirected Graph
* that is entered into the compiler by the user. The user must paste in all
* input into the compiler via the following patterns:
* Map:
* - Node pairs: Example --> (x1 x2)
* Avoid:
* - Nodes: Example --> (x1 x2 x3 x4 ...)
* Peggy:
* - Nodes: Example --> (x1 x2 x3 x4 ...)
* Sam:
* - Nodes: Example --> (x1 x2 x3 x4 ...)
*
* Upon entering in all node information press enter and all valid meeting
* locations will be printed out in alphabetical order by the program upon its
* completion.
*/
class Main{
private static ArrayList<Node> nodeStore = new ArrayList<Node>();
// Stores all Nodes
private static Scanner eyes = new Scanner(System.in);
// Scanner Object - reads in all input.
private static ArrayList<Node> Peggy = new ArrayList<Node>();
private static ArrayList<Node> Sam = new ArrayList<Node>();
// Stores Peggy Nodes and Sam Nodes.
private static HashMap<Node,Boolean> markStore = new HashMap<Node,Boolean>();
// Stores all Nodes and a marker for if it is a valid meeting location for each DFS call.
private static HashMap<Node,Boolean> markStore2 = new HashMap<Node,Boolean>();
// Stores all Nodes that are valid meeting locations.
private static HashMap<String, Node> check = new HashMap<String,Node>();
// Stores Nodes and their corresponding names after being added to Storage ArrayList
private static Node nuguy = new Node();
private static Node nuguy2 = new Node();
// Node objects used for storing actual Nodes entered by user
private static String[] lol1, lol2, lol3;
// String Arrays used to store strings of Node names
// (Which ones to avoid, where Peggy starts, and where Sam starts)
/** Method receives a Node to start with and a target Node, and marks all valid
* meeting locations between these Nodes by iterating through the map using a
* Recursive DFS Algorithm.
*
* @param currentNode current Node to analyze and iterate from
* @param targetNode target Node to reach using DFS Algorithm
*/
private static void graphDFSByRecursion(Node currentNode, Node targetNode){
if (null == currentNode) {
return;
// Back track or exit if nodeStore is empty
}
currentNode.visitNode();
// Change Node color from white to black (visited)
// Debugging print line statement below
// System.out.println(currentNode.myself);
markStore.put(currentNode,true);
// Mark as visited
if (currentNode.equals(targetNode)) {
// Check if we reached out target node
// Mark as valid meeting Location if target Node
markStore.put(currentNode,true);
}
if (currentNode.equals(targetNode) && currentNode.getChildren().isEmpty()){
// Check if we reached out target node and if Node has children
// Valid meeting Location
markStore.put(currentNode,true);
// Return to previous Node
return;
}
if (currentNode.getChildren().isEmpty() && !currentNode.equals(targetNode)){
// Check if we reached out target node and if Node doesn't have children
// Invalid meeting location
markStore.put(currentNode,false);
// Return to previous Node
return;
}
int gee = 0;
if (!currentNode.getChildren().isEmpty()) {
for (Node n : currentNode.getChildren()) {
if (markStore.containsKey(n)) {
if (n.color.equals("black") && !markStore.get(n)) {
gee++;
}
// Increase gee variable to check if all children are visited and
// that they are not valid meeting locations
if (markStore.get(n)){
// If a child is valid, mark current Node as valid
markStore.put(n,true);
// Return to previous Node
return;
}
}
}
}
if (gee == currentNode.getChildren().size()){
// If all children of current Node are visited and invalid, mark as
// invalid meeting location
markStore.put(currentNode,false);
// Return to previous Node
return;
}
boolean win = false;
if (!currentNode.getChildren().isEmpty()) {
// Recursively visit all of unvisited neighbors if current Node has children
for (Node Neighbor : currentNode.getChildren()) {
if (Neighbor.color.equals("white") && markStore.containsKey(Neighbor)) {
// If neighbor isn't visited, visit it
graphDFSByRecursion(Neighbor, targetNode);
// Debugging print line statement below
// System.out.println(currentNode.myself);
if (markStore.get(Neighbor)) {
// If neighbor is valid meeting place, change Boolean marker
win = true;
}
}
}
}
if (!win) {
// If neighbor is not a valid meeting place, change its validity to false
markStore.put(currentNode, false);
return;
}
}
/** This method takes valid meeting location Node values and
* Sorts them in alphabetical order.
* @param map
* @return
*/
private static List sortByValues(HashMap map) {
List sortedKeys = new ArrayList();
for(int t = 0; t < map.size(); t++){
sortedKeys.add(t,map.keySet().toArray()[t].toString());
// Populate sortedKeys list
}
// Tests if map that was sent was null
Set<String> sorts = null;
if (sortedKeys != null) {
sorts = new HashSet<String>(sortedKeys);
}
// Sorts values in map sent to Method
Collections.sort(sortedKeys,String.CASE_INSENSITIVE_ORDER);
return sortedKeys;
}
/** This method takes a String array consisting of either Peggy or
* Sam values Node names along with an ArrayList containing the corresponding
* Nodes themselves, and initializes the aforementioned ArrayList with all
* correct Nodes from the Node storage ArrayList
*
* @param con
* @param hold
*/
private static void boundaryNodeInit(String[] con, ArrayList<Node> hold ){
for (int b = 1; b <= con.length; b++) {
for (int e = 0; e < nodeStore.size(); e++){
// Finds each Node in Node Storage ArrayList and imports them into Boundary Node ArrayList
if ((nodeStore.get(e)).myself.equals(con[b-1])){
hold.add(nodeStore.get(e));
}
}
}
}
/** Runs Let's Do Lunch Program as directed in original problem statement
* found at: http://ensoftupdate.com/download/jobs/programming-exercise-0114.pdf
*
* @param args
*/
public static void main(String[] args) {
String[] temp;
int b;
while (eyes.hasNextLine()) {
// While input is able to read in lines from console, read in lines
String input = eyes.nextLine();
// get the entire input set after the prompt
if(input.isEmpty()){
// Exit if empty
break;
}
if (input.equals("Map:")) {
// If input line is map section, store Node pairs
while (eyes.hasNextLine()){
// While there is input, store nodes in nodeStore ArrayList
input = eyes.nextLine();
temp = input.split(" ");
// Array that holds a pair of nodes - updated each line
if (input.startsWith("Avoid:")){
// Exits loop upon reading in all Node pairs
break;
}
if(temp.length == 2) {
if (!check.containsKey(temp[0]) && !check.containsKey(temp[1])) {
// If both Nodes are new (not in storage ArrayList), store as follows
// Initialize 1st and 2nd Node color, neighbors, and children
nuguy = new Node(temp[0]);
nuguy.color = "white";
nuguy2 = new Node(temp[1]);
nuguy2.color = "white";
nuguy.setChildren(nuguy2);
nuguy.setNeighbors(nuguy2);
nuguy2.setNeighbors(nuguy);
// Add both Nodes to testing HashMap
check.put(temp[0], nuguy);
check.put(temp[1],nuguy2);
// Add Nodes to ArrayList of Nodes
nodeStore.add(nuguy);
nodeStore.add(nuguy2);
// Initialize meeting place HashMap markers to false
markStore.put(nuguy, false);
markStore.put(nuguy2,false);
} else if (check.containsKey(temp[0]) && !check.containsKey(temp[1])) {
// If first Node is old and second is new, store as follows
// Sets Node attributes equal to preceding Nodes in Node Storage ArrayList
nuguy = check.get(temp[0]);
// Initialize 1st and 2nd Node color, neighbors, and children
nuguy.color = "white";
nuguy2 = new Node(temp[1]);
nuguy2.color = "white";
nuguy.setChildren(nuguy2);
nuguy.setNeighbors(nuguy2);
nuguy2.setNeighbors(nuguy);
// Add 2nd Node to testing HashMap
check.put(temp[1], nuguy2);
// Add 2nd Node to Node Storage ArrayList
nodeStore.add(nuguy2);
// Initialize meeting place HashMap marker for 2nd Node to false
markStore.put(nuguy2,false);
} else if (!check.containsKey(temp[0]) && check.containsKey(temp[1])){
// If first Node is new and second is old, store as follows
// Sets Node attributes equal to preceding Nodes in Node Storage ArrayList
nuguy2 = check.get(temp[1]);
// Initialize 1st and 2nd Node color, neighbors, and children
nuguy = new Node(temp[0]);
nuguy.color = "white";
nuguy2.color = "white";
nuguy.setChildren(nuguy2);
nuguy.setNeighbors(nuguy2);
nuguy2.setNeighbors(nuguy);
// Add 1st Node to testing HashMap
check.put(temp[0], nuguy);
// Add 1st Node to Node Storage ArrayList
nodeStore.add(nuguy);
// Initialize meeting place HashMap marker for 1st Node to false
markStore.put(nuguy,false);
} else {
// If both Nodes are old, configure as follows
// Add both Nodes to testing HashMap
nuguy = check.get(temp[0]);
nuguy2 = check.get(temp[1]);
// Initialize neighbors and children for both Nodes
nuguy.setChildren(nuguy2);
nuguy.setNeighbors(nuguy2);
nuguy2.setNeighbors(nuguy);
}
}
}
}
if (input.startsWith("Av")) {
input = eyes.nextLine();
lol1 = input.split(" ");
// Reads in Nodes to avoid
for (b = 0; b < lol1.length; b++) {
for (int e = 0; e < nodeStore.size(); e++){
if ((nodeStore.get(e)).myself.equals(lol1[b])){
// Removes Nodes from Node Storage ArrayList and from meeting place HashMap
markStore.keySet().removeAll(Collections.singleton(nodeStore.get(e)));
nodeStore.removeAll(Collections.singleton(nodeStore.get(e)));
}
}
}
}
if (input.equalsIgnoreCase("Peggy:")) {
input = eyes.nextLine();
lol2 = input.split(" ");
// Reads in Starting Nodes for Peggy
boundaryNodeInit(lol2,Peggy);
}
if (input.equalsIgnoreCase("Sam:")) {
input = eyes.nextLine();
lol3 = input.split(" ");
// Reads in Starting Nodes for Sam
boundaryNodeInit(lol3,Sam);
}
}
// Debugging Print Line Statements - print out node sets and each node's child
//System.out.println(markStore.keySet());
//System.out.println(nodeStore);
//for (int t =0; t < nodeStore.size(); t++){
//System.out.println(nodeStore.get(t));
//System.out.println(nodeStore.get(t).getChildren());
//}
for (int p = 0; p < Peggy.size(); p++) {
for (int s = 0; s < Sam.size(); s++) {
// Re-Initializes meeting place HashMap for next DFS Implementation
markStore.clear();
// Re-initializes Node Storage ArrayList
for (int z = 0; z < nodeStore.size(); z++) {
nodeStore.get(z).color = "white";
markStore.put(nodeStore.get(z),false);
}
// Visits and marks all valid paths between Peggy and Sam
if(p==0 && s==0){
graphDFSByRecursion(Peggy.get(0),Sam.get(0));
} else graphDFSByRecursion(Peggy.get(p), Sam.get(s));
for (int q = 0; q < nodeStore.size(); q++){
// Catalogues all meeting places that are valid and stores them in new HashMap
if (markStore.get(nodeStore.get(q))){
// If old HashMap has valid meeting locations, add to new HashMap
markStore2.put(nodeStore.get(q),true);
}
}
// Print Line statements used for debugging
//System.out.println(markStore.values());
//System.out.println(markStore.keySet());
//System.out.println(markStore2.values());
//System.out.println(markStore2.keySet());
}
}
List map = sortByValues(markStore2);
// List map contains sorted valid meeting locations
for (int x = 0; x < map.size(); x++) {
// Prints valid meeting locations in console
System.out.println(map.get(x).toString());
}
}
}
Node.java
/**
* Created by Ian on 2/3/2015.
*
* This Node class has various methods within it used to correctly
* identify and access all vertices as necessary. Each Node can have
* its name stored (myself), its color stored (color), and its children
* and neighbors, along with whether it has been visited as seen in
* variables initialized below.
*
* @author Ian Norris
*/
public class Node implements Comparable{
public boolean visited;
public ArrayList<Node> neighbors = new ArrayList<Node>();
public ArrayList<Node> children = new ArrayList<Node>();
public String myself, color;
/** Adds Node to neighbors ArrayList of this Node
*
* @param gee Node which is added to ArrayList
*/
public void setNeighbors(Node gee){
this.neighbors.add(gee);
}
/** Adds Node child to ArrayList of this Node's children
*
* @param ch Node which is added to ArrayList
*/
public void setChildren(Node ch){
this.children.add(ch);
}
/** Returns this Node's children
*
* @return children
* */
public ArrayList<Node> getChildren(){
return this.children;
}
/** Sets this Node's name to a given String value
*
* @param y name
*/
public Node(String y){
this.myself = y;
}
/** Default Node method
*
*/
public Node(){
}
/** Marks Node as visited
*
* @param visited
*/
public void setVisited(boolean visited) {
// Set current Node as visited
this.visited = visited;
}
/** Adds Node to neighbors ArrayList of this Node
*
*/
public void visitNode() {
// Changes color of Node if not visited, and identifies as visited
if(this.color.equals("white")){
this.setVisited(true);
this.color = "black";
}
}
/** Override CompareTo method so that default Equals method analyzes Nodes correctly
*
* @param o Node object
* @return
*/
@Override
public int compareTo(Object o) {
return 0;
}
/** Override toString() method such that value of Node can be displayed
*
* @return Return name of Node
*/
@Override
public String toString() {
return myself;
}
/** Overrides equals default method such that Node values can be compared
*
* @param obj
* @return Returns whether this Node equals Node sent to method
*/
@Override
public boolean equals(Object obj) {
if(obj instanceof Node){
Node toCompare = (Node) obj;
return this.myself.equals(toCompare.myself);
}
return false;
}
/** This method Overrides default hashCode method such that HashMap can be
* reconfigured to store Nodes and Boolean markers. It also sets and returns
* this Node's hashCode.
*
* @return Return hashCode of this Node's value
*/
@Override
public int hashCode() {
return this.myself.hashCode();
}
