2
\$\begingroup\$

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();
    }
\$\endgroup\$
5
\$\begingroup\$
    private static ArrayList<Node> nodeStore = new ArrayList<Node>();
    // Stores all Nodes

It's more common to put comments before the code. However, in this case, the comment is redundant. Either expand it to be more descriptive or remove it.

    private static List<Node> nodeStore = new ArrayList<>();

If you are using Java 8, you don't need to write out <Node> the second time.

I also changed your ArrayList variable to simply a List. As a general rule in Java, the variable type should be just the interface. You should only specify the implementation as the type if the implementation allows some needed functionality that the interface does not. This makes your code more maintainable, as you can change implementations without having to change the type everywhere.

    private static Scanner eyes = new Scanner(System.in);

The name eyes is cute but not really descriptive. More common names would be scan or scanner.

    private static ArrayList<Node> Peggy = new ArrayList<Node>();
    private static ArrayList<Node> Sam = new ArrayList<Node>();
    // Stores Peggy Nodes and Sam Nodes.

Again, I could easily tell that these stored Peggy and Sam Nodes. What I don't know at this point of the code is what a Peggy or Sam Node is. This suggests to me that this is the wrong place to be declaring these variables. You may want to thing about how you use class fields. I see no reason why any of these couldn't have been set in the methods where they were used. As a general rule, Main shouldn't need class fields. If you do need fields, perhaps you should have created another class where fields would make more sense. Perhaps Graph. Your depth-first search and other methods might make more sense there as well.

    private static HashMap<String, Node> check = new HashMap<String,Node>();
    // Stores Nodes and their corresponding names after being added to Storage ArrayList

This comment is backwards. The Map doesn't store Nodes and their corresponding names. It stores names and their corresponding Nodes.

It's unclear to me why this field is called check. Perhaps NodesByName might be better.

Again, the variable type should be the interface rather than the implementation.

    private static Map<String, Node> check = new HashMap<>();

And here too it's unnecessary to specify the type parameters on the right in Java 8.

    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)

Why name these lol? That says laugh out loud to me, which doesn't really seem to match the descriptions given. Why not name them avoidLocations, startPeggy, and startSam?

        // Debugging print line statement below
        // System.out.println(currentNode.myself);

By the time that you send out for code review, debugging code should be gone.

        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;
        }

You make currentNode as true. Then you mark it true again if a condition holds. Then you do it a third time if another condition holds. Wasn't the first time enough?

Why only return if the targetNode has no children? Reaching the targetNode would seem to be a base case for the recursive search. Aren't we done regardless?

        if (currentNode.equals(targetNode)) {
            // Check if we reached our target node
            return;
        }

Why isn't this sufficient? If we found the target node, return it as part of the path.

By the way, I changed "out" to "our" in the comment. I think that's what was meant there.

Note that you'd need to change the method to return List<Node> rather than void.

        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;
        }

If you adopt my change and stop when you reach the targetNode, then you'll know that the latter part is true.

        if (currentNode.getChildren().isEmpty()) {
            // If Node doesn't have children
            // Return to previous Node
            return;
        }

I don't quite understand why you are marking it as unvisited. You did visit it. You just found that it wasn't on a valid path. OK. So markStore is not visit status. The earlier comment was wrong.

        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;
                    }
                }
            }
        }

Hmm...you just returned if currentNode had no children. Why check again?

What's a gee? It looks like you are counting the number of visited children. Why is that called gee?

You correctly used the more modern version of the for loop here. You should do that more often. Iterating over an index that goes to .size() is almost never necessary.

    public void setNeighbors(Node gee){
        this.neighbors.add(gee);
    }

Last time, gee was an int. Why is this Node given the same name? What does it mean? The name neighbor would make more sense here.

    public void addNeighbor(Node neighbor){
        neighbors.add(neighbor);
    }

You aren't setting neighbors. You're just adding one.

You don't need to use this. here. You only need it when you want to disambiguate the object field from another variable. That's not the case here.

public class Node implements Comparable {

You shouldn't leave Comparable as the bare type. Go ahead and say

public class Node implements Comparable<Node> {

Now it won't think that you believe a Node is comparable with other objects.

    public int compareTo(Object o) {
        return 0;
    }

So a Node is equal to every other kind of object? That seems unlikely.

    public int compareTo(Node o) {

At least this way, it's only equal to other nodes. It's not clear to me what's comparable about nodes though. What makes one Node less than another?

    public boolean equals(Object obj) {
        if(obj instanceof Node){
            Node toCompare = (Node) obj;
            return this.myself.equals(toCompare.myself);
        }
        return false;
    }

Why not just

    public boolean equals(Node toCompare) {
        return myself.equals(toCompare.myself);
    }

Although I'm not sure that myself is sufficient. You do nothing in Node to ensure that two nodes won't have the same myself strings.

Node could use an isVisited method that would return a boolean.

It's not clear to me why a Node will change color when visited.

Hopefully that gives you some things to consider while looking for your bug. Hint: what happens if there are two (or more) paths between a start node for Peggy and a start node for Sam?

\$\endgroup\$
1
\$\begingroup\$

Very Positive Aspects of the Code

  1. Many of the comments are meaningful.
  2. Many of the routine names are descriptive.

Basic Comments

  1. The assumption that the graph is undirected is mistaken:

    Each segment of river is listed as pairs of addresses, from upstream to downstream.

  2. In my opinion trying to define a graph based on nodes is a poor starting point. See my comments here and here.
  3. Thinking about problems mathematically and writing a specification before writing code is recommended by at least one Turing Award winner.

Decoupling

It would be helpful to separate the business logic abstractions of Peggy and Sam and swimming, from the underlying mathematical abstractions of graphs and nodes upon which the business logic is built. Both the business logic and the mathematics should be separated from raw Java arrays and lists etc.

Modularity

Decoupling the code provides natural module boundaries. Node.java is a step in this direction, but more separation of abstractions would be beneficial.

Program Specification

Summary of Problem

  1. The Map is given as a directed graph from upstream to downstream.
  2. A list of vertices which must be avoided is given.
  3. Peggy Piranha swims only downstream.
  4. Sam Salmon swims only upstream.
  5. Find the set of vertices reachable by both Peggy and Sam.

Given:

  • a digraph Map = {V, E} (vertices are implied).
  • a list of dead vertices dead
  • a list of Peggy starting vertices peggyStart
  • a list of Sam starting vertices samStart

1. Initialize:

  • Create digraph G by removing all edges u -> v such that dead.member(u) || dead.member(v) == TRUE
  • Create digraph G' such that for each edge u -> v in G there is an edge v -> u in G'.

2. Find strongly connected components:

  1. peggyPaths = the set of strongly connected components in G containing at least one element of peggyStart.
  2. samPaths = the strongly connected component in G' containing at least one element of samStart.

3. Find the set of common vertices:

  1. peggyCanReach = the union of all vertices in peggyPaths.
  2. samCanReach = the union of all vertices in samPaths.
  3. return intersection (peggyCanReach, samCanReach)

Implementation Details

Finding the strongly connected components of a digraph can be done in linear time [O(n + m)] using Kosaraju's Algorithm.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.