Three ice water buckets challenge

This problem is found here: http://learningandtheadolescentmind.org/resources_02_bucket.html

I called it three "Ice Bucket Challenge" for fun. ;) Here is the problem description.

There are an 8-liter bucket filled with ice water and empty 3-liter and 5-liter buckets. You solve the puzzle by using the three buckets to divide the 8 liters of water into two equal parts of 4 liters. Try to solve the puzzle in the fewest number of moves.

Although to find a fewest number of moves is not easy, but I can design depth first search to find the necessary moves to distribute the waters.
Here is the code
The idea here is to for each possible case, we find the all possible cases which can be derived from it. For example, from 8, 0, 0, it could be 5, 0, 3 or 3, 5, 0. And we use a list keep track of the cases we already visited. Think of all possible cases as a graph, we essentially do a depth first search until we find the case contains 4. A potential solution to find the fewest moves is to use the breath first search. We can use a Queue to contain the list of cases we already visited, then generate the queue of next level based on that, also keep track of the parent case for each case in the queue until we find the case.

find all palidrome partitions for a string

This problem is from LeetCode:
http://www.programcreek.com/2013/03/leetcode-palindrome-partitioning-java/

      Given a string s, partition s such that every substring of the partition is a palindrome.
    
     we can think all possible palindromic substrings form a graph.
     each palindromic substring is the node
     two nodes connect each other when one's starting index is equal to
     the other ending index. There are multiple roots in this graph but only one leaf.     
     roots are the palidrome substrings starting at index 0
     leaf are the node with starting index equals to string's length
     a path from root to leaf is one palindrome partition
    
     
    public static void findAllPali(String s){
        dfs(s, 0, new ArrayList<String>());
    }
 
  public static void dfs(String s, int start, List<String> current){
        //reach leaf level, then we find the palidrome partition
        if(start==s.length()){
            System.out.println(current);
            return;
        }
        for(int j=start+1;j<=s.length();j++){
            //depth first search
            //find one node
            if(isPali(s, start, j-1)){
                /*
                 * before we go down this branch
                 * we make copy of the path
                 * then pass it down
                 */
                List<String> copy = new ArrayList<String>(current);
                copy.add(s.substring(start, j));
                dfs(s, j, copy);
            }
        }
    }
   
   
    public static boolean isPali(String s, int i, int j){
        while(i<j){
            if(s.charAt(i)!=s.charAt(j))
                return false;
            i++;j--;
        }
        return true;
    }

Topological sort of airports

A friend of mine presents the following problem to, given a list of airports, LAX, PHL, LGA, JFK, EWK and list of routes between them: LAX->PHL, LGA->EWK, JFK->LAX, construct the whole path to connect those airports. The route can start with any airports and end at any airports. 

Take a note the problem says the destination are unknown. so we need to sort them all. 

The key to topological sort is to do DFS, then add the visited node at the end, in that way the the nodes are sorted. 

public class Airport {

public Airport(String from) {

this.name = from;

this.destinations = new ArrayList<Airport>();

}

String name;

List<Airport> destinations;

}

public class Edge{

String from;

String to;

}

public Stack<Airport> sortAirports(List<Edge> edges){

Map<String, Airport> graph = new HashMap<String, Airport>();

buildGraph(edges, graph);

Set<String> visited = new HashSet<String>();

Stack<Airport> s = new Stack<Airport>();

for(Airport a : graph.values()){

sort(a, s, visited);

}

return s;

}

public void sort(Airport a, Stack<Airport> s, Set<String> visited){

if(visited.contains(a.name))

return;

visited.add(a.name);

for(Airport d : a.destinations){

sort(d, s, visited);

}

s.add(a); <== add the earlier visited airport at last

}

Find diameter for any tree

The diameter of a tree is the maximum length of path between any vertex in a tree. The simple solution is to start from any vertex, do a DFS, find a farthest vertex from it, then from that farthest vertex, do second DFS, find the farthest vertex from it.

//here is the graph node with adjacentList representation.
//for illustration purpose, the key of each vertex is character

public static class CNode {

char c;

Set<CNode> outgoing = new HashSet<CNode>();

CNode(char i){this.c=i;}

        public int hashCode() {}

        public boolean equals(Object o){}

}

public static int diameterOfTree(CNode[] vertices){

int[] max = new int[1];

CNode[] mNode = new CNode[1];

Set<CNode> visited = new HashSet<CNode>();

//start with any vertex in the tree

dfs(vertices[0], 0, visited, max, mNode);

CNode[] maxNode = new CNode[1];

max[0] = 0;

visited = new HashSet<CNode>();

dfs(mNode[0], 0, visited, max, maxNode);

return max[0];

}

public static void dfs(CNode start, int distance, Set<CNode> visited, int[] max, CNode[] maxNode){

visited.add(start);

max[0] = Math.max(max[0], distance);

if(max[0]==distance)

   maxNode[0] = start;

for(CNode n : start.outgoing){

if(!visited.contains(n)){

dfs(n, distance+1, visited, max, maxNode);

}

}

}