Given two containers, one of which can accommodate a liters of water and the other b liters of water, determine the number of steps required to obtain exactly target liters of water in one of the containers, or -1 if it cannot be done.

At the beginning both containers are empty. The following operations are counted as 'steps':

Empty a container

Fill a container

Pour water from one container to the other, without spilling, until one of the containers is either full or empty

To get you started, we provide you a Node and a Graph class. Your job is to implement the function Graph createGraph(int capacity_a, int capacity_b), which builds a graph that contains all the possible container states given the capacity of two containers, and int findSolution(Graph g, int target), which does the graph traversal and returns the minimum steps.

You can modify the structures if you like, or build your own solution without using the provided structures. We will only test your int waterPouring(int a, int b, int target) function.

Hint: Which algorithm gurantees a minimun number of steps to reach a target?

Testing Your Code

You are provided a main.cpp with one test case.

container A: 3L container B: 4L Minimum number of steps required to get 2L is: 4

//main.cpp

#include

using namespace std;

#include "waterPouring.cpp"

int main() {

int volumeA = 3, volumeB = 4, target = 2;

printf("container A: %dL\tcontainer B: %dL ", volumeA, volumeB);

printf("Minimum number of steps required to get %dL is: %d ",

target, waterPouring(volumeA, volumeB, target));

}

//waterPouring.cpp

#include

#include

#include

using namespace std;

#define EMPTY 0

class Node {

public:

int a;

int b;

vector neighbors;

Node () : a(EMPTY), b(EMPTY), neighbors() {}

Node (const int &a_, const int &b_) : a(a_), b(b_), neighbors() {}

Node (const int &a_, const int &b_, const vector &neighbors_) : a(a_), b(b_), neighbors(neighbors_) {}

Node (const Node &tmpNode) : a(tmpNode.a), b(tmpNode.b), neighbors() {}

bool operator==(const Node & b_node)

{

return a == b_node.a && b == b_node.b;

}

Node &operator=(const Node & b_node) {

// WARNING: This operator does not copy the vector

a = b_node.a;

b = b_node.b;

return *this;

}

};

struct Graph {

vector nodes;

};

Graph createGraph(int capacityy_a, int capacity_b) {

// TODO

Graph g;

return g;

}

int findSolution(Graph g, int target) {

// TODO: returns minimum number of steps to reach target liters of water (or -1)

return -1;

}

int waterPouring(int a, int b, int target) {

// Call createGraph

// Call findSolution

Graph stateMachineGraph = createGraph(a, b);

int steps = findSolution(stateMachineGraph, target);

for (Node *graphNode : stateMachineGraph.nodes)

{

delete graphNode;

}

return steps;

}