2
\$\begingroup\$

There are n balls kept on a table and connected by same singe connected string (which can be cyclic or maynot). Write the code to select a ball such that after lifting the whole structure from that ball height will be minimum. (algo+code+ mathematical proof of correctness)

Note, I do understand merits of unit testing in separate files. But deliberately added it to main method for personal convenience, so request you don’t consider that in your feedback. Looking for request code review, optimizations and best practices and complexity verification.

  • Complexity:
  • O(EV) - time complexity
  • O(V) - space complexity

class GraphLiftBall<T> implements Iterable<T> {

    /* A map from nodes in the graph to sets of outgoing edges.  Each
     * set of edges is represented by a map from edges to doubles.
     */
    private final Map<T, List<T>> graph = new HashMap<T, List<T>>();

    /**
     *  Adds a new node to the graph. If the node already exists then its a
     *  no-op.
     * 
     * @param node  Adds to a graph. If node is null then this is a no-op.
     * @return      true if node is added, false otherwise.
     */
    public boolean addNode(T node) {
        if (node == null) {
            throw new NullPointerException("The input node cannot be null.");
        }
        if (graph.containsKey(node)) return false;

        graph.put(node, new ArrayList<T>());
        return true;
    }

    /**
     * Given the source and destination node it would add an arc from source 
     * to destination node. If an arc already exists then the value would be 
     * updated the new value.
     *  
     * @param source                    the source node.
     * @param destination               the destination node.
     * @param length                    if length if 
     * @throws NullPointerException     if source or destination is null.
     * @throws NoSuchElementException   if either source of destination does not exists. 
     */
    public void addEdge (T source, T destination) {
        if (source == null || destination == null) {
            throw new NullPointerException("Source and Destination, both should be non-null.");
        }
        if (!graph.containsKey(source) || !graph.containsKey(destination)) {
            throw new NoSuchElementException("Source and Destination, both should be part of graph");
        }
        /* A node would always be added so no point returning true or false */
        graph.get(source).add(destination);
        graph.get(destination).add(source);
    }

    /**
     * Given a node, returns the edges going outward that node,
     * as an immutable map.
     * 
     * @param node The node whose edges should be queried.
     * @return An immutable view of the edges leaving that node.
     * @throws NullPointerException   If input node is null.
     * @throws NoSuchElementException If node is not in graph.
     */
    public List<T> edgesFrom(T node) {
        if (node == null) {
            throw new NullPointerException("The node should not be null.");
        }
        List<T> edges = graph.get(node);
        if (edges == null) {
            throw new NoSuchElementException("Source node does not exist.");
        }
        return Collections.unmodifiableList(graph.get(node));
    }

    /**
     * Returns the iterator that travels the nodes of a graph.
     * 
     * @return an iterator that travels the nodes of a graph.
     */
    @Override public Iterator<T> iterator() {
        return graph.keySet().iterator();
    }
}


final class BallPick<T> {
    private final T ballId;
    private final int depth;

    BallPick (T ballId, int depth) {
        this.ballId = ballId;
        this.depth = depth;
    }

    public T getBallId() {
        return ballId;
    }

    public int getDepth() {
        return depth;
    }

    @Override
    public String toString() {
        return "BallPick [ballId=" + ballId + ", depth=" + depth + "]";
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((ballId == null) ? 0 : ballId.hashCode());
        result = prime * result + depth;
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null) return false;
        if (getClass() != obj.getClass()) return false;
        BallPick other = (BallPick) obj;
        if (ballId == null) {
            if (other.ballId != null)
                return false;
        } else if (!ballId.equals(other.ballId))
            return false;
        if (depth != other.depth)
            return false;
        return true;
    }
}


public final class LiftBall<T> {

    /**
     * Returns the ball, which when picked, the distance/height/depth from the picked ball to 
     * last ball on the surface would be minimal.
     * If two balls would result in the same height, eg: an isoceles triangle, then any ball would be valid answer
     * 
     * @param graph - the graph, which represents balls connected by a string.
     * @return      - the ball which results in minimal height.
     */
    public static <T> BallPick<T> leastMemory(GraphLiftBall<T> graph) {
        final Iterator<T> itr = graph.iterator();
        BallPick<T> ballPick = null;
        int minValue = Integer.MAX_VALUE;

        while (itr.hasNext()) {
            T currNode = itr.next();
            int val = bfs(currNode, graph);
            if (val < minValue) {
                minValue = val;
                ballPick = new BallPick<T>(currNode, minValue);
            }
        }
        return ballPick;
    }

    private static <T> int bfs(T node, GraphLiftBall<T> graph) {
        Queue<T> thisLevel = new LinkedList<T>(); 
        Queue<T> nextLevel = new LinkedList<T>();

        final Set<T> visited = new HashSet<T>();
        visited.add(node);

        thisLevel.add(node);

        int depth = -1;
        while (!thisLevel.isEmpty()) {
            T currNode = thisLevel.poll();

            for(T neighbor : graph.edgesFrom(currNode)) {
                if (!visited.contains(neighbor)) {
                    nextLevel.add(neighbor);
                    visited.add(neighbor);
                }
            }

            if (thisLevel.isEmpty()) {
                thisLevel = nextLevel;
                nextLevel = new LinkedList<T>();
                depth++;
            }
        }

        return depth;
    }


    public static void main(String[] args) {

        // A straight line of 3 balls 1 - 2 - 3, picking ball 2 would result in shortest depth.
        GraphLiftBall<Integer> graphLiftBall1 = new GraphLiftBall<Integer>();
        graphLiftBall1.addNode(1);
        graphLiftBall1.addNode(2);
        graphLiftBall1.addNode(3);
        graphLiftBall1.addEdge(1, 2);
        graphLiftBall1.addEdge(2, 3);
        assertEquals(new BallPick<Integer>(2, 1), LiftBall.leastMemory(graphLiftBall1));

        // A triangle of 3 balls 
        GraphLiftBall<Integer> graphLiftBall2 = new GraphLiftBall<Integer>();
        graphLiftBall2.addNode(1);
        graphLiftBall2.addNode(2);
        graphLiftBall2.addNode(3);
        graphLiftBall2.addEdge(1, 2);
        graphLiftBall2.addEdge(2, 3);
        graphLiftBall2.addEdge(3, 1);
        assertEquals(new BallPick<Integer>(1, 1), LiftBall.leastMemory(graphLiftBall2));

        // A square of 4 balls 
        GraphLiftBall<Integer> graphLiftBall3 = new GraphLiftBall<Integer>();
        graphLiftBall3.addNode(1);
        graphLiftBall3.addNode(2);
        graphLiftBall3.addNode(3);
        graphLiftBall3.addNode(4);
        graphLiftBall3.addEdge(1, 2);
        graphLiftBall3.addEdge(2, 3);
        graphLiftBall3.addEdge(3, 4);
        graphLiftBall3.addEdge(4, 1);
        assertEquals(new BallPick<Integer>(1, 2), LiftBall.leastMemory(graphLiftBall3));

        // A pyramid of 5 balls
        GraphLiftBall<Integer> graphLiftBall4 = new GraphLiftBall<Integer>();
        graphLiftBall4.addNode(1);
        graphLiftBall4.addNode(2);
        graphLiftBall4.addNode(3);
        graphLiftBall4.addNode(4);
        graphLiftBall4.addNode(5);
        graphLiftBall4.addEdge(1, 2);
        graphLiftBall4.addEdge(2, 3);
        graphLiftBall4.addEdge(3, 4);
        graphLiftBall4.addEdge(4, 1);

        graphLiftBall4.addEdge(5, 1);
        graphLiftBall4.addEdge(5, 2);
        graphLiftBall4.addEdge(5, 3);
        graphLiftBall4.addEdge(5, 4);

        assertEquals(new BallPick<Integer>(5, 1), LiftBall.leastMemory(graphLiftBall4));

    }
}
\$\endgroup\$
  • 4
    \$\begingroup\$ What is E and what is V in your complexity comments? \$\endgroup\$ – rolfl Apr 21 '14 at 2:05
2
\$\begingroup\$

Your assignment sounds like the traveling salesman problem (TSP).

If you're looking for the exact shortest path, you have to pretty much brute force the answer, since TSP is NP-hard problem.

If near optimal path is acceptable to you I suggest you look into genetic algorithms or ant colony system. The best algorithm really depends on acceptable error and ball count.

(I would've added comment, but I can't for the lack of points)

| improve this answer | |
\$\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.