Daily Archives: May 24, 2015

Water jug problem

And I found this water jug problem when I’m reading Number Theory. It is interesting. Let me start by defining the problem:

Assume we have 2 jugs. Jug1 can contains 3 galons water, jug2 can contains 5 galons water. We can pour water into jug1 and jug2, empty 2 jugs, or we can pour water between 2 jugs. The question is how can we get a 4 galons water by pouring water between these 2 jugs.

Assume (x, y) is one of state of 2 jugs, which jug1 has x galons of water, jug2 has y galons of water. A possible movement is like this: (0, 5) -> (3, 2) -> (0, 2) -> (2, 0) -> (2, 5) -> (3, 4)

It turns out it is an AI problem. It has many states. Each state can transit to another state. And we find the goal state.

The transistion of a state can be described as below:
(x, y) -> (a, y) if x < a, fill first jug
(x, y) -> (x, b) if b < y, fill second jug
(x, y) -> (0, y) if x > 0, empty first jug
(x, y) -> (x, 0) if y > 0, empty second jug
(x, y) -> (a, y – (a – x)) if x + y > a, pour water from second jug to first jug
(x, y) -> (x – (b – y), b) if x + y > b, pour water from first jug to second jug
(x, y) -> (x + y, 0) if x + y <= a, pour water from second jug to first jug
(x, y) -> (0, x + y) if x + y <= b, pour water from first jug to second jug

During the search, we find if x or y becomes the goal volume we want. Below my code is a DFS implementation. It is a basic solution for water jug. The result may not be optimized.

package com.pli.project.algorithm.ai;

import java.math.BigInteger;
import java.util.HashSet;
import java.util.Stack;

/**
 * Created by lipeng on 2015/5/23.
 */
public class WaterJug {

    public static void waterJug(int a, int b, int target){
        /** Eliminate unproper input. */
        if(a <= 0 || b <= 0 || target > b){
            System.out.println("no solution for " + a + ", " + b + ", " + target);
            return;
        }
        BigInteger bigA = new BigInteger(String.valueOf(a));
        BigInteger bigB = new BigInteger(String.valueOf(b));
        int gcd = bigA.gcd(bigB).intValue();
        if(target % gcd != 0){
            System.out.println("no solution for " + a + ", " + b + ", " + target);
            return;
        }
        if(a > b){
            System.out.println("b is supposed to greater than a.");
            return;
        }
        HashSet stateSpace = new HashSet();   //stores all the states.
        WjState firstState = new WjState(0, 0);
        Stack stateStack = new Stack();
        stateStack.add(firstState);
        WjState curState = firstState;
        /** DFS to find target result. Result is not guaranteed to be optimized **/
        while(stateStack.size() > 0 && curState.x != target && curState.y != target){
            curState = stateStack.peek();
            WjState nextState = new WjState(0, 0, curState.step + 1, curState);
            if(curState.x < a && !stateSpace.contains(nextState.setPos(a, curState.y))){
                stateSpace.add(nextState);
                stateStack.add(nextState);
            }
            else if(curState.y < b && !stateSpace.contains(nextState.setPos(curState.x, b))){
                stateSpace.add(nextState);
                stateStack.add(nextState);
            }
            else if(curState.x > 0 && !stateSpace.contains(nextState.setPos(0, curState.y))){
                stateSpace.add(nextState);
                stateStack.add(nextState);
            }
            else if(curState.y > 0 && !stateSpace.contains(nextState.setPos(curState.x, 0))){
                stateSpace.add(nextState);
                stateStack.add(nextState);
            }
            else if(curState.x + curState.y > a && !stateSpace.contains(nextState.setPos(a, curState.y - a + curState.x))){
                stateSpace.add(nextState);
                stateStack.add(nextState);
            }
            else if(curState.x + curState.y > b && !stateSpace.contains(nextState.setPos(curState.x - b + curState.y, b))){
                stateSpace.add(nextState);
                stateStack.add(nextState);
            }
            else if(curState.x + curState.y <=a && !stateSpace.contains(nextState.setPos(curState.x + curState.y, 0))){
                stateSpace.add(nextState);
                stateStack.add(nextState);
            }
            else if(curState.x + curState.y <=b && !stateSpace.contains(nextState.setPos(0, curState.x + curState.y))){
                stateSpace.add(nextState);
                stateStack.add(nextState);
            }
            else{
                stateStack.pop();
            }
        }// while
        /** Output result */
        StringBuffer output = new StringBuffer();
        while(curState != null){
            output.insert(0, " -> " + curState);
            curState = curState.pre;
        }
        output.delete(0, 4);
        System.out.println(output);
    }


    public static class WjState{
        int x, y;
        int step;   //How many steps is needed in order to reach the state
        WjState pre;    //to define the state before it.

        public boolean posEquals(WjState state){
            if(this.x==state.x&&this.y==state.y){
                return true;
            }
            return false;
        }

        public WjState(int x, int y){
            this.x = x;
            this.y = y;
        }

        public WjState(int x, int y, int step, WjState pre){
            this.x = x;
            this.y = y;
            this.step = step;
            this.pre = pre;
        }

        public WjState setPos(int x, int y){
            this.x = x;
            this.y = y;
            return this;
        }

        public int hashCode() {
            int hash = 1 ;
            hash = hash * 31 + x;
            hash = hash * 31 + y;
            return hash;
        }

        public String toString(){
            return "(" + this.x + ", " + this.y + ")";
        }

        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            WjState wjState = (WjState) o;
            if (x != wjState.x) return false;
            return y == wjState.y;
        }
    }

    public static void main(String[] args) {
        waterJug(3, 5, 4);
    }
}

gcd

Euclid’s algorithm: gcd of 2 number equals gcd of smaller number and their difference.

Use Euclid’s algorithm to calculate gcd(a, b).

package com.pli.project.algorithm.gcd;

import java.math.BigInteger;

/**
 * Created by lipeng on 2015/5/23.
 */
public class Gcd {

    /**
     * Keep a is the max value.
     * gcd{a,b}=gcd{−a,b}=gcd{a,−b}=gcd{−a,−b}
     * https://proofwiki.org/wiki/GCD_for_Negative_Integers
     */
    public static int gcd(int a, int b){
        a = Math.abs(a);
        b = Math.abs(b);
        if(b > a){
            int tmp = b; b = a; a = tmp;
        }
        if(b==0){
            return a;
        }
        int remainder = 0;
        do {
            remainder = a % b;
            a = b;
            b = remainder;
        } while(remainder!=0);
        return a;
    }

    public static void main(String[] args) {
        BigInteger a = new BigInteger("-10");
        BigInteger b = new BigInteger("5");
        System.out.println(a.gcd(b));
        System.out.println(gcd(-10, 5));
    }

}