(UVA) Jugs - Solution

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=646&page=show_problem&problem=512

The solution below used Breadth-First Search (BFS) to solve this problem.

We can use this algorithm because the structure resultant of the operations is like a tree, and a tree is a graph. Then, we can apply graph algorithms to solve it.


import java.io.*;
import java.util.*;

class Main {
    public int capacityA;
    public int capacityB;
    public int target;
    public ArrayList<String> operations;
   
    public void bfs(int startA, int startB) {
        Queue<Jug> queue = new ArrayDeque<>();
        queue.add(new Jug(startA, startB, "", -1, -1));
       
        Jug[][] visited = new Jug[capacityA+1][capacityB+1];
       
        while (queue.size() > 0) {
            Jug curr = queue.poll();
            int currA = curr.a;
            int currB = curr.b;
            String currOp = curr.op;
            int currPreviousA = curr.previousA;
            int currPreviousB = curr.previousB;
           
            if (visited[currA][currB] != null) {
                continue;
            }
            visited[currA][currB] = curr;
           
            if (currB == target) {
                int cA = currA;
                int cB = currB;
                while (cA != 0 || cB != 0) { // until it reaches the initial state
                    operations.add(visited[cA][cB].op);
                    int tmpCA = visited[cA][cB].previousA;
                    cB = visited[cA][cB].previousB;
                    cA = tmpCA;
                }
                return;
            }
           
            queue.add(new Jug(capacityA, currB, "fill A", currA, currB)); // fill A
            queue.add(new Jug(currA, capacityB, "fill B", currA, currB)); // fill B
            queue.add(new Jug(0, currB, "empty A", currA, currB)); // empty A
            queue.add(new Jug(currA, 0, "empty B", currA, currB)); // empty B
            int capacityDest = capacityB-currB;
            int pour = Math.min(currA, capacityDest);
            queue.add(new Jug(currA-pour, currB+pour, "pour A B", currA, currB)); // pour A B
            capacityDest = capacityA-currA;
            pour = Math.min(currB, capacityDest);
            queue.add(new Jug(currA+pour, currB-pour, "pour B A", currA, currB)); // pour B A
        }
    }
   
    public void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        while (sc.hasNext()) {
            capacityA = sc.nextInt();
            capacityB = sc.nextInt();
            target = sc.nextInt();
           
            operations = new ArrayList<>();
            bfs(0, 0);

            for (int i = operations.size()-1; i >= 0; i--) {
                bw.write(operations.get(i)+"\n");
            }
            bw.write("success\n");
        }  
                                              
        bw.flush();
        bw.close();
       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}

class Jug {
    int a;
    int b;
    String op;
    int previousA;
    int previousB;
   
    public Jug(int a, int b, String op, int previousA, int previousB) {
        this.a = a;
        this.b = b;
        this.op = op;
        this.previousA = previousA;
        this.previousB = previousB;
    }
}