# Graph Implementation Problem - Shortest Path/Dijkstra's (?)

Have this small graph problem to do for today, was wondering if anyone had any possible solutions/insight for it.

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 contain er
• 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 guarantees a minimun number of steps to reach a target?

My initial guess was Dijkstra's for the findSolution(), and attempted to translate some pseudo-code, but that didn't work out. I (think) I implemented createGraph correctly. Quite unsure as to where to go/if there's a better way to do this. Here's the code:

Thank you!

waterPouring.cpp:

 #include <unordered_map>
#include <queue>
#include <vector>

using namespace std;

#define EMPTY 0

class Node {
public:
int a;
int b;
vector<Node *> 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<Node *> &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<Node *> nodes;
};

Graph createGraph(int capacity_a, int capacity_b) {
// TODO
Graph g;
Node * capacityNode = new Node(capacity_a, capacity_b);
for (int i = 0; i < g.nodes.size(); i++) {
g.nodes.push_back(capacityNode);
}
return g;
}

int findSolution(Graph g, int target) {
// TODO: returns minimum number of steps to reach target liters of
water (or -1)
for (int& node : g) {
// not sure
}
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;
}

• Yes, Dijkstra or any other shortest path algorithm should work fine. Beyond that, your question is purely one of programming, which is off-topic, here. Programming questions belong on Stack Overflow but note that "How do I write a program to do X?" is usually off-topic, there. See their help centre for details. – David Richerby Dec 5 at 23:04
• Welcome to Computer Science! To continue David's comment, a request to debug incorrect code is off-topic everywhere in general. So how to ask questions that can be helpful for you to correct your error might not be an easy task by itself. Anyway, whenever you get an error, it is almost compulsory to show it in detail. You are expected to provide a Minimal, Complete, and Verifiable example. – Apass.Jack Dec 5 at 23:17