365. Water and Jug Problem

/*
 * Multimap to keep track of what coordinates we have seen to prevent looping
 * Depth first search, there are 6 actions possible at each (x,y)
 *   - fill x up to max
 *   - fill y up to max
 *   - transfer x to y (if applicable)
 *   - transfer y to x (if applicable)
 *   - drop x
 *   - drop y
 *
 * no multimap in java, so lets use a map of first index -> hashset // or override hashCode
 *
 *
 * OR: just use Bezout's identity
 * */

// Bezout's identity version:

/*
public boolean canMeasureWater(int x, int y, int z) {
  //limit brought by the statement that water is finallly in one or both buckets
  if(x + y < z) return false;
  //case x or y is zero
  if( x == z || y == z || x + y == z ) return true;

  //get GCD, then we can use the property of Bézout's identity
  return z%GCD(x, y) == 0;
}

public int GCD(int a, int b){
  while(b != 0 ){
    int temp = b;
    b = a%b;
    a = temp;
  }
  return a;
}
*/


public class Solution {
  private static class Pair {
    public int x;
    public int y;

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

  private static class HashPairSet {
    private HashMap<Integer, HashSet<Integer>> map;

    public HashPairSet() {
      map = new HashMap<Integer, HashSet<Integer>>();
    }

    public void insert(Pair pair) {
      HashSet<Integer> ySet = map.get(pair.x);
      
      if (ySet == null) {
        ySet = new HashSet<Integer>();
        map.put(pair.x, ySet);
      }

      ySet.add(pair.y);
    }

    public boolean contains(Pair pair) {
      HashSet<Integer> ySet = map.get(pair.x);

      if (ySet == null) return false;

      return ySet.contains(pair.y);
    }
  }

  // Modifies stack and set if pair is unique, otherwise do nothing
  public static void addPossibility(Pair pair, ArrayDeque<Pair> stack, HashPairSet set) {
    if (!set.contains(pair)) {
      stack.addFirst(pair);
      set.insert(pair);
    }
  }

  public boolean canMeasureWater(int xMax, int yMax, int target) {
    HashPairSet set = new HashPairSet();

    ArrayDeque<Pair> stack = new ArrayDeque<Pair>();
    stack.addFirst(new Pair(0, 0));

    while(!stack.isEmpty()) {
      Pair pair = stack.removeFirst();

      if (pair.x == target ||
          pair.y == target ||
          (pair.x + pair.y) == target) {
        return true;
      }

      // Fill 'x' up to max
      if (pair.x != xMax) {
        addPossibility(new Pair(xMax, pair.y), stack, set);
      }

      // Fill 'y' up to max
      if (pair.y != yMax) {
        addPossibility(new Pair(pair.x, yMax), stack, set);
      }

      // Transfer 'x' to 'y'
      if (yMax != pair.y) {
        int transfer = Math.min(yMax - pair.y, pair.x);
        addPossibility(new Pair(pair.x - transfer, pair.y + transfer), stack, set);
      }

      // Transfer 'y' to 'x'
      if (xMax != pair.x) {
        int transfer = Math.min(pair.y, xMax - pair.x);
        addPossibility(new Pair(pair.x + transfer, pair.y - transfer), stack, set);
      }

      // Drop 'x'
      if (pair.x != 0) {
        addPossibility(new Pair(0, pair.y), stack, set);
      }

      // Drop 'y'
      if (pair.y != 0) {
        addPossibility(new Pair(pair.x, 0), stack, set);
      }
    }

    return false;
  }
}