package _365;

import java.util.HashSet;

/**
 * Error: StackOverFlow!!!
 */
class OldSolution {
    public boolean canMeasureWater(int x, int y, int z) {
        HashSet<String> set = new HashSet<>();
        return canMeasureWaterIter(x, y, z, 0, 0, set);
    }

    /**
     * @param _x  The water in bottle x
     * @param _y  The water in bottle y
     * @param set The set of old states
     */
    private boolean canMeasureWaterIter(int x, int y, int z, int _x, int _y, HashSet<String> set) {
        boolean isDone = _x == z || _y == z || (_x + _y) == z;
        if (isDone)
            return true;
        boolean isTried = set.contains(_x + ":" + _y);
        if (isTried)
            return false;
        set.add(_x + ":" + _y);
        int _x_x2y, _y_x2y, _x_y2x, _y_y2x;
        int sum_xy = _x + _y;
        if (sum_xy > x) {
            _x_x2y = x;
            _y_x2y = sum_xy - x;
        } else {
            _x_x2y = sum_xy;
            _y_x2y = 0;
        }
        if (sum_xy > y) {
            _y_y2x = y;
            _x_y2x = sum_xy - y;
        } else {
            _y_y2x = sum_xy;
            _x_y2x = 0;
        }
        return canMeasureWaterIter(x, y, z, x, _y, set) || canMeasureWaterIter(x, y, z, _x, y, set)
                || canMeasureWaterIter(x, y, z, 0, _y, set) || canMeasureWaterIter(x, y, z, _x, 0, set)
                || canMeasureWaterIter(x, y, z, _x_x2y, _y_x2y, set) || canMeasureWaterIter(x, y, z, _x_y2x, _y_y2x, set);
    }

    private static void testCanMeasureWater(int x, int y, int z) {
        OldSolution solution = new OldSolution();
        System.out.println(solution.canMeasureWater(x, y, z));
    }

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