Water Jug Problem

[btl1903]

Hallo Leute,
ich habe mich mit dem Problem von Water Pouring (mit 2 Becher und mit 3 Becher) auseinandergesetzt und habe auch sehr viel geschafft zum Programmieren. Leider bekomme ich Nullpointer Exception. Ich wäre sehr dankbar wenn mir jemand weiterhelfen könnte .. Danke im voraus .
Hier sind meine codes:
Node :

public class Node {

    public int[] state;

    public Node parent;

    public Move move;

    /**
     * Create a new node
     */
    public Node(int[] state, Move move, Node parent) {
        this.state = state;
        this.move = move;
        this.parent = parent;
    }
}

Move :

public class Move {

    public String from;

    public String to;

    public int quantity;

    public Move(String from, String to, int quantity) {
        this.from = from;
        this.to = to;
        this.quantity = quantity;
    }
}

WaterProblem:

import java.io.PrintStream;
import java.util.ArrayList;

public class WaterProblem implements P1 {

    public ArrayList<Node> frontier;
    public ArrayList<int[]> explored;
   
    @Override
    public int solve(int xCapacity, int yCapacity, int goal, PrintStream out) {
        Node solution = search(xCapacity, yCapacity, goal);
        int steps = countMoves(solution);
        return steps;
    }

    public Node search(int xCapacity, int yCapacity, int goal) {

        // Initial state
        int[] initial_state = { 0, 0 };

        // Current node
        Node curr_node = new Node(initial_state, null, null);

        // List of frontier nodes at each iteration
        this.frontier = new ArrayList<Node>();

        // List of nodes already explored
        this.explored = new ArrayList<int[]>();

        frontier.add(curr_node);

        while (true) {
            // If we have exhausted our frontier, we have no solution
            if (frontier.size() == 0) {
                return null;
            }

            // Pop new node from frontier to consider
            curr_node = frontier.remove(0);

            // Add chosen node to explored list if not already there
            if (!this.isAlreadyExplored(curr_node.state)) {
                explored.add(curr_node.state);
            }

            // List of actions that can be applied based on the state and the description of
            // the problem
            Move[] moves = this.getFeasibleMoves(curr_node.state, xCapacity, yCapacity);

            // Apply our transition model to generate child nodes from current node
            for (Move move : moves) {
                Node child = this.getChildNode(curr_node, move);

                if (!this.inFrontier(child) && !this.isAlreadyExplored(child.state)) {
                    if (this.containsGoal(child.state, goal)) {
                        return child;
                    }
                    frontier.add(child);
                }
            }
        }
    }

    /**
     * Get the list of actions that should be applied when given a state
     */
    public Move[] getFeasibleMoves(int[] state, int xCapacity, int yCapacity) {
        int x = state[0];
        int y = state[1];
        ArrayList<Move> movesList = new ArrayList<Move>();
       
        // Fill X
        if (x == 0) {
            movesList.add(new Move("source", "x", xCapacity));
        }
        // Fill Y
        if (y == 0) {
            movesList.add(new Move("source", "y", yCapacity));
        }
        // Empty X
        if (x == xCapacity) {
            movesList.add(new Move("x", "ground", x));
        }
        // Empty Y
        if (y == yCapacity) {
            movesList.add(new Move("y", "ground", y));
        }
        // Transfer from X to Y
        if ((x > 0) && ((yCapacity - y) > 0)) {
            movesList.add(new Move("x", "y", Math.min((yCapacity - y), x)));
        }
        // Transfer from X to Y
        if ((y > 0) && ((xCapacity - x) > 0)) {
            movesList.add(new Move("y", "x", Math.min((xCapacity - x), y)));
        }

        Move[] actionsArray = new Move[movesList.size()];
        return movesList.toArray(actionsArray);
    }

    /**
     * Get a child node when given a node and action
     */
    public Node getChildNode(Node node, Move move) {
        int[] new_state = new int[2];

        new_state[0] = node.state[0];
        new_state[1] = node.state[1];

        if (move != null) {
            if (move.to == "x") {
                new_state[0] = node.state[0] + move.quantity;
            }
            if (move.to == "y") {
                new_state[1] = node.state[1] + move.quantity;
            }
            if (move.from == "x") {
                new_state[0] = node.state[0] - move.quantity;
            }
            if (move.from == "y") {
                new_state[1] = node.state[1] - move.quantity;
            }
        }
        Node new_node = new Node(new_state, move, node);
        return new_node;
    }

    /**
     * Check whether a node is in frontier
     */
    public boolean inFrontier(Node node) {
        for (Node curr : this.frontier) {
            if ((curr.state[0] == node.state[0]) && (curr.state[1] == node.state[1])) {
                return true;
            }
        }
        return false;
    }

    /**
     * Check whether a state is in explored state
     */
    public boolean isAlreadyExplored(int[] state) {
        for (int i = 0; i < this.explored.size(); i++) {
            int[] curr = this.explored.get(i);

            if ((curr[0] == state[0]) && (curr[1] == state[1])) {
                return true;
            }
        }
        return false;
    }

    /**
     * Check whether given state is goal state
     */
    public boolean containsGoal(int[] state, int goal) {
        return state[0] == goal || state[1] == goal;
    }

    public int countMoves(Node solution_node) {
        ArrayList<String> steps = new ArrayList<String>();

        try {
            while (solution_node.parent != null) {
                steps.add("Fill " + solution_node.move.to + " with water from  " + solution_node.move.from + " (ie. "
                        + solution_node.move.quantity + " canister)" + " New state: " + solution_node.state[0] + ","
                        + solution_node.state[1]);

                solution_node = solution_node.parent;
            }
        } catch (NullPointerException e) {
            e.printStackTrace();
        }
        return steps.size();
    }

    public static void main(String[] args) {
        WaterProblem wp = new WaterProblem();
        int x = wp.solve(4, 8, 2, System.out);
        System.out.println("Number of actions = " + x);
    }
}

Three Canisters:

public class ThreeCanisters implements P2 {

    public ArrayList<Node> frontier;
    public ArrayList<int[]> explored;

    @Override
    public int solve(int xCapacity, int yCapacity, int zCapacity, int xInit, int yInit, int zInit, int goal,
            PrintStream out) {
        Node solution = search(xCapacity, yCapacity, zCapacity, xInit, yInit, zInit, goal);
        int steps = countMoves(solution);
        return steps;
    }

    public Node search(int xCapacity, int yCapacity, int zCapacity, int xInit, int yInit, int zInit, int goal) {

        // Initial state
        int[] initial_state = { xInit, yInit, zInit };

        // Current node
        Node curr_node = new Node(initial_state, null, null);

        // List of frontier nodes at each iteration
        this.frontier = new ArrayList<Node>();

        // List of nodes already explored
        this.explored = new ArrayList<int[]>();

        frontier.add(curr_node);

        while (true) {
            // If we have exhausted our frontier, we have no solution
            if (frontier.size() == 0) {
                return null;
            }

            // Pop new node from frontier to consider
            curr_node = frontier.remove(0);

            // Add chosen node to explored list if not already there
            if (!this.isAlreadyExplored(curr_node.state)) {
                explored.add(curr_node.state);
            }

            // List of actions that can be applied based on the state and the description of
            // the problem
            Move[] moves = this.getFeasibleMoves(curr_node.state, xCapacity, yCapacity, zCapacity);

            // Apply our transition model to generate child nodes from current node
            for (Move move : moves) {
                Node child = this.getChildNode(curr_node, move);

                if (!this.inFrontier(child) && !this.isAlreadyExplored(child.state)) {
                    if (this.containsGoal(child.state, goal)) {
                        return child;
                    }
                    frontier.add(child);
                }
            }
        }
    }

    /**
     * Get the list of actions that should be applied when given a state
     */
    public Move[] getFeasibleMoves(int[] state, int xCapacity, int yCapacity, int zCapacity) {
        int x = state[0];
        int y = state[1];
        int z = state[2];
        ArrayList<Move> movesList = new ArrayList<Move>();

        if (x == xCapacity) {
            // Empty X
            movesList.add(new Move("x", "ground", x));
        }

        if (y == yCapacity) {
            // Empty Y
            movesList.add(new Move("y", "ground", y));
        }

        if (z == zCapacity) {
            // Empty Z
            movesList.add(new Move("z", "ground", z));
        }

        // Transfer from X to Y
        if ((x > 0) && ((yCapacity - y) > 0)) {
            movesList.add(new Move("x", "y", Math.min((yCapacity - y), x)));
        }
        // Transfer from Y to Z
        if ((y > 0) && ((zCapacity - z) > 0)) {
            movesList.add(new Move("y", "z", Math.min((zCapacity - z), y)));
        }
        // Transfer from Z to X
        if ((z > 0) && ((xCapacity - x) > 0)) {
            movesList.add(new Move("z", "x", Math.min((xCapacity - x), z)));
        }

        Move[] actionsArray = new Move[movesList.size()];
        return movesList.toArray(actionsArray);
    }

    /**
     * Get a child node when given a node and action
     */
    public Node getChildNode(Node node, Move move) {
        int[] new_state = new int[3];

        new_state[0] = node.state[0];
        new_state[1] = node.state[1];
        new_state[2] = node.state[2];

        if (move != null) {
            if (move.to == "x") {
                new_state[0] = node.state[0] + move.quantity;
            }
            if (move.to == "y") {
                new_state[1] = node.state[1] + move.quantity;
            }
            if (move.to == "z") {
                new_state[2] = node.state[2] + move.quantity;
            }
            if (move.from == "x") {
                new_state[0] = node.state[0] - move.quantity;
            }
            if (move.from == "y") {
                new_state[1] = node.state[1] - move.quantity;
            }
            if (move.from == "z") {
                new_state[2] = node.state[2] - move.quantity;
            }
        }
        Node new_node = new Node(new_state, move, node);
        return new_node;
    }

    /**
     * Check whether a node is in frontier
     */
    public boolean inFrontier(Node node) {
        for (Node curr : this.frontier) {
            if ((curr.state[0] == node.state[0]) && (curr.state[1] == node.state[1])
                    && (curr.state[2] == node.state[2])) {
                return true;
            }
        }
        return false;
    }

    /**
     * Check whether a state is in explored state
     */
    public boolean isAlreadyExplored(int[] state) {
        for (int i = 0; i < this.explored.size(); i++) {
            int[] curr = this.explored.get(i);

            if ((curr[0] == state[0]) && (curr[1] == state[1]) && (curr[2] == state[2])) {
                return true;
            }
        }
        return false;
    }

    /**
     * Check whether given state is goal state
     */
    public boolean containsGoal(int[] state, int goal) {
        return state[0] == goal || state[1] == goal || state[2] == goal;
    }

    public int countMoves(Node solution_node) {
        ArrayList<String> steps = new ArrayList<String>();

        try {
            while (solution_node.parent != null) {
                steps.add("Fill " + solution_node.move.to + " with water from  " + solution_node.move.from + " (ie. "
                        + solution_node.move.quantity + " canister)" + " New state: " + solution_node.state[0] + ","
                        + solution_node.state[1] + "," + solution_node.state[2]);

                solution_node = solution_node.parent;
            }
        } catch (NullPointerException e) {
            e.printStackTrace();
        }
        return steps.size();
    }

    public static void main(String[] args) {
        ThreeCanisters tc = new ThreeCanisters();
        int x = tc.solve(7, 2, 5, 0, 1, 2, 4, System.out);
        System.out.println("Number of actions = " + x);
    }

}

 

[truesoul]

Hallo.

Hast du auch ein Stacktrace für uns?

Grüße

 

[btl1903]

was meinst du damit? :/

 

[truesoul]

Na die komplette Fehlermeldung

 

[btl1903]

java.lang.NullPointerException
    at yarat_atliay.p1.WaterProblem.countMoves(WaterProblem.java:168)
    at yarat_atliay.p1.WaterProblem.solve(WaterProblem.java:15)
    at yarat_atliay.p1.WaterProblem.main(WaterProblem.java:183)
Number of actions = 0

 

[truesoul]

Dann wird solution_node null sein.
Du gibst in search auch Null zurück und vergleichst in countMoves

while (solution_node.parent != null) {

und wenn die node null ist kann sie auch kein parent haben.

Auf den Smartphone ist so viel Code bissl schwer zu überblicken. Baue ein paar Konsolenausgaben ein. Besser wäre mit den Debugger zu prüfen.

 

[fhoffmann]

Der Fehler tritt also in Zeile 168 von WaterProblem.java auf.
Kannst du uns auch noch verraten, welche Zeile dies ist.

 

[btl1903]

while (solution_node.parent != null) {

Das ist diese Zeile in countmoves. Ich find den Fehler nicht, weil mit manche andere Werte gehts wiederrum ..

 

[fhoffmann]

Dann schreibe doch mal davor

if (solution_node == null) Sytem.err.println("Huch, solution_node == null");

Falls diese Fehlermeldung ausgegeben wird, kannst du nach der Stelle suchen, an der die Methode mit null aufgerufen wird (und dies dürfte in Zeile 15 von WaterProblem.java sein).

 

[btl1903]

ok, also hab das davor geschrieben, und diese fehlermeldung wird ausgegeben

if (solution_node == null)
                System.err.println("Huch, solution_node == null");
           
            else
                while(solution_node.parent != null) {
               
                    steps.add("Fill " + solution_node.move.to + " with water from  " + solution_node.move.from + " (ie. "
                                + solution_node.move.quantity + " canister)" + " New state: " + solution_node.state[0] + ","
                                + solution_node.state[1]);
   
                    solution_node = solution_node.parent;
            }

Ausgabe:

Huch, solution_node == null
Number of actions = 0

was muss ich in zeile 15 machen?

 

[btl1903]

heißt es jetzt dass es für diese eingabe keine lösung gibt?

 

[fhoffmann]

heißt es jetzt dass es für diese eingabe keine lösung gibt?

Probier es doch einfach aus, indem du noch ein paar weitere System.err.println(...) einfügst, z.B. hier:

if (frontier.size() == 0) {
   Sytem.err.println("frontier.size() == 0");
   return null;
}

Und dann guckst du, warum dies so ist (oder ob der "Fehler" an einer anderen Stelle auftritt).

 

[AndiE]

Das Triple 8,4->2 hat keine Lösung, würde ich sagen. Bei 9,4->6 gibt es eine Lösung, siehe anderer Post. Auf den ersten Blick sind 1,3,4,5,6,9 als Ziel bei 9 und 4 möglich. 2,7 und 8 nicht.
Das besondere bei diesem Algorithmus ist. dass Wasser nicht innerhalb der Behälter umgeschüttet wird, sondern aus einem Becken geschöpft oder dort hinein gegossen wird.