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 single-source shortest paths: Dijkstra algorithm implementation

A generic shortest path algorithm to find shortest path from single source vertex for graph is as following:

Given Graph(V, E, W), V is the set of vertices, E is the set of edges, W is the set of weights for each edge, and source vertex s.

distance[] array contains the distance from any vertex to source vertex s
parent[] array contains the previous vertex to any vertex on a given shortest path

1. initialize
 for any v:
  d[v] = infinity, parent[v] = null
d[s] = 0

2. relaxation
flag = true
while(flag)
 flag = false
 for any edge u, v
   if(d[v] > d[u] + w(u, v)){
    d[v] = d[u] + w(u, v)
    parent[v] = u
    flag = true
   }


Couple optimized shortest path algorithm exists to implement different ways of relaxation and make d[] converge fast. Dijkstra algorithm is one of them. It can handle any graph even with cycles, but all of the weights have to be non-negative.

public class ShortestPathQ {

/*

* Dijkstra algorithm for any graph with positive weights

* the algorithm essentially is BFS using a priority queue

*/

/*

* here i assume graph is represented as adjacent matrix, D

* vertex is represented as number of 0, 1, ..., n-1

* the value at each cell D[i][j] represent weight of the edge

* from vertex i to j

*/

//a custom PQ to hold the list of vertex ordered by their distances from source

class PQ {

//the binary heap represented as array

int[] heap;

//keep track of vertex position in the heap

int[] indices;

int[] distance;

int size;

//time complexity O(size)

PQ(int s, int[] d){

size = s;

heap = new int[s];

distance = d;

heapify();

}

//time complexity O(size)

void heapify(){

for(int i = 0; i<size; i++){

heap[i] = i;

indices[i] = i;

}

for(int i=size/2; i>=0; i--)

bubbleDown(i);

}

//time complexity O(lg(size))

void bubbleDown(int index){

int target = index;

int left = index*2+1;

if(left<size && distance[left] < distance[target])

target = left;

int right = index*2+1;

if(right<size && distance[right] < distance[target])

target = right;

if(target!=index){

swap(target, index);

bubbleDown(target);

}

}

void swap(int i, int j){

int tem = heap[i];

heap[i] = heap[j];

heap[j] = tem;

tem = indices[i];

indices[i] = indices[j];

indices[j] = tem;

}

//time complexity O(lg(size))

void bubbleUp(int index){

int target = index;

int parent = (index-1)/2;

if(parent>=0 && distance[parent] > distance[target])

target = parent;

if(target!=index){

swap(target, index);

bubbleUp(target);

}

}

int min(){

return heap[0];

}

//time complexity O(lg(size))

int removeMin(){

int i = heap[0];

heap[0] = heap[--size];

bubbleDown(0);

return i;

}

int indexOf(int vertex){

return indices[vertex];

}

boolean isEmpty(){

return size == 0;

}

}

class Graph {

int[][] w;

int size;

Graph(int size){

this.size = size;

w = new int[size][size]; 

}

/*

* undirected graph representation

* weight zero means no edge between two vertex

*/

void addEdge(int i, int j, int we){

w[i][j] = we;

w[j][i] = we;

}

/* given vertex, dijkstra algorithm will calculate 

* shortest path from it to any vertex in the graph 

*/

int[] dijkstra(int source){

  int[] distance;

int[] parent;

//initialize

distance = new int[this.size];

parent = new int[this.size];

for(int i=0;i<this.size; i++){

distance[i] = Integer.MAX_VALUE;

parent[i] = -1;

}

distance[source] = 0;

parent[source] = -1;

PQ queue = new PQ(this.size, distance);

while(!queue.isEmpty()){

int u = queue.removeMin();

for(int v = 0; v < size; v++){

if(w[u][v] != 0){//there is edge from u to v

//relaxation O(lgsize)

if(distance[v] > distance[u] + w[u][v]){

distance[v] = distance[u] + w[u][v];

parent[v] = u;

queue.bubbleUp(queue.indexOf(v));

}

}

}

}  

return distance;

}



//PQ implemented in java PriorityQueue but it doesn't have optimized update() or remove()
// method, time complexity is O(size) at relaxation step
int[] dijkstraUsingJavaPQ(int source){
final int[] distance;
int[] parent;

//initialize

distance = new int[this.size];
parent = new int[this.size];
for(int i=0;i<this.size; i++){
distance[i] = Integer.MAX_VALUE;
parent[i] = -1;
}

distance[source] = 0;
parent[source] = -1;

PriorityQueue<Integer> queue = new PriorityQueue<Integer>(this.size, new Comparator<Integer>(){

@Override

public int compare(Integer i, Integer j){
if(distance[i] == distance[j])
return 0;
else if(distance[i] > distance[j])
return 1;
else
return -1;
}
});

for(int i = 0; i<size; i++)
queue.add(i);

while(!queue.isEmpty()){
int u = queue.remove();
for(int v = 0; v < size; v++){

if(w[u][v] != 0){//there is edge from u to v

//relaxation O(size)

if(distance[v] > distance[u] + w[u][v]){
distance[v] = distance[u] + w[u][v];
parent[v] = u;
queue.remove(v);//remove by equals()
queue.add(v);
}
}
}
}

return distance;
}

}

}

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

}