Water Pouring Problem - Graph Modelling

We have three containers whose sizes are 10 litres,7 litres, and 4 litres,respectively. The 7-litre and 4-litre containers start out full of water, but the 10-litre container is initially empty. We are allowed one type of operation: pouring the contents of one container into another,stopping only when the source container is empty or the destination container is full.We want to know if there is a sequence of pourings that leaves exactly 2litres in the 7 or 4-litre container. Model this as a graph problem and solve.

Problem Summary:

We have three containers:

  • A → 10 liters (capacity)

  • B → 7 liters (capacity)

  • C → 4 liters (capacity)

Initially:

  • A = 0 liters (empty)

  • B = 7 liters (full)

  • C = 4 liters (full)

Operation allowed:

👉 Pour water from one container to another until either the source container is empty or the destination is full.

Goal:

👉 Reach a situation where either B or C has exactly 2 liters.

How to model this as a graph problem?

  1. Each state is a node in the graph.
    A state is represented as a triplet (A, B, C).

  2. An edge between two states represents a pouring operation (pour from one container to another).

  3. Start node: (0, 7, 4)

  4. Goal node: any node where B==2 or C==2.

  5. Graph traversal: use BFS (Breadth-First Search) to find the shortest sequence of pourings to reach the goal.

Graph Search Algorithm:

1. Define State:


State: (A, B, C)

2. Valid operations (edges):

For every state, you can try:

  • Pour A → B

  • Pour A → C

  • Pour B → A

  • Pour B → C

  • Pour C → A

  • Pour C → B

Apply the pouring operation according to container limits.

3. BFS Steps:

  • Start from initial state (0,7,4)

  • At each step, generate all possible next states

  • Push them into the queue

  • Keep track of visited states to avoid cycles

  • If you reach a state with 2 liters in B or C, STOP — print the path.

Pseudocode:

Initialize queue with start state (0,7,4)
Mark start as visited

while queue not empty:
    current = dequeue()
    
    if (current.B == 2 or current.C == 2):
        print path
        exit
    
    for each valid pouring (from -> to):
        generate new_state
        
        if new_state not visited:
            enqueue new_state
            mark new_state visited

Full Explanation:

Imagine each state as a node:


(0,7,4) → pour B → A → (7,0,4)
(7,0,4) → pour A → C → (7- (4-4), 0, 4) = (7,0,4) (no change) ❌
...

  • Each pouring moves to a new node.

  • BFS ensures you find the shortest sequence (minimum number of pourings).

  • Visited table (3D array) is important: visited[A][B][C] = 1 means already explored


C Program — Water Puring Problem
#include <stdio.h>
#include <stdlib.h>

#define MAX 11 // Since maximum water is 10 liters

typedef struct State {
    int a, b, c; // Amounts in 10L, 7L, and 4L
    struct State* parent; // To track the path
} State;

typedef struct QueueNode {
    State *state;
    struct QueueNode *next;
} QueueNode;

typedef struct Queue {
    QueueNode *front, *rear;
} Queue;

// Create a new state
State* createState(int a, int b, int c, State *parent) {
    State* newState = (State*)malloc(sizeof(State));
    newState->a = a;
    newState->b = b;
    newState->c = c;
    newState->parent = parent;
    return newState;
}

// Queue operations
void initQueue(Queue *q) {
    q->front = q->rear = NULL;
}

int isEmpty(Queue *q) {
    return q->front == NULL;
}

void enqueue(Queue *q, State *state) {
    QueueNode *temp = (QueueNode*)malloc(sizeof(QueueNode));
    temp->state = state;
    temp->next = NULL;
    if (q->rear == NULL) {
        q->front = q->rear = temp;
        return;
    }
    q->rear->next = temp;
    q->rear = temp;
}

State* dequeue(Queue *q) {
    if (q->front == NULL)
        return NULL;
    QueueNode *temp = q->front;
    State *state = temp->state;
    q->front = q->front->next;
    if (q->front == NULL)
        q->rear = NULL;
    free(temp);
    return state;
}

// To print the path by tracing parents
void printPath(State *state) {
    if (state == NULL)
        return;
    printPath(state->parent);
    printf("(%d, %d, %d)\n", state->a, state->b, state->c);
}

// Function to perform pouring
void pour(State *curr, Queue *q, int visited[MAX][MAX][MAX]) {
    int A = curr->a, B = curr->b, C = curr->c;
    int maxA = 10, maxB = 7, maxC = 4;

    // All possible pourings:

    // A->B
    int pourAmt = (B + A > maxB) ? maxB - B : A;
    if (pourAmt > 0) {
        int na = A - pourAmt, nb = B + pourAmt, nc = C;
        if (!visited[na][nb][nc]) {
            visited[na][nb][nc] = 1;
            enqueue(q, createState(na, nb, nc, curr));
        }
    }

    // A->C
    pourAmt = (C + A > maxC) ? maxC - C : A;
    if (pourAmt > 0) {
        int na = A - pourAmt, nb = B, nc = C + pourAmt;
        if (!visited[na][nb][nc]) {
            visited[na][nb][nc] = 1;
            enqueue(q, createState(na, nb, nc, curr));
        }
    }

    // B->A
    pourAmt = (A + B > maxA) ? maxA - A : B;
    if (pourAmt > 0) {
        int na = A + pourAmt, nb = B - pourAmt, nc = C;
        if (!visited[na][nb][nc]) {
            visited[na][nb][nc] = 1;
            enqueue(q, createState(na, nb, nc, curr));
        }
    }

    // B->C
    pourAmt = (C + B > maxC) ? maxC - C : B;
    if (pourAmt > 0) {
        int na = A, nb = B - pourAmt, nc = C + pourAmt;
        if (!visited[na][nb][nc]) {
            visited[na][nb][nc] = 1;
            enqueue(q, createState(na, nb, nc, curr));
        }
    }

    // C->A
    pourAmt = (A + C > maxA) ? maxA - A : C;
    if (pourAmt > 0) {
        int na = A + pourAmt, nb = B, nc = C - pourAmt;
        if (!visited[na][nb][nc]) {
            visited[na][nb][nc] = 1;
            enqueue(q, createState(na, nb, nc, curr));
        }
    }

    // C->B
    pourAmt = (B + C > maxB) ? maxB - B : C;
    if (pourAmt > 0) {
        int na = A, nb = B + pourAmt, nc = C - pourAmt;
        if (!visited[na][nb][nc]) {
            visited[na][nb][nc] = 1;
            enqueue(q, createState(na, nb, nc, curr));
        }
    }
}

int main() {
    Queue q;
    initQueue(&q);

    int visited[MAX][MAX][MAX] = {0};

    State *start = createState(0, 7, 4, NULL);
    enqueue(&q, start);
    visited[0][7][4] = 1;

    while (!isEmpty(&q)) {
        State *curr = dequeue(&q);

        if (curr->b == 2 || curr->c == 2) {
            printf("\nSolution path:\n");
            printPath(curr);
            return 0;
        }

        pour(curr, &q, visited);
    }

    printf("No solution found.\n");
    return 0;
}

Comments

Post a Comment

Popular posts from this blog

Data Structures Lab PCCSL307 KTU 2024 Scheme - Dr Binu V P

About Me    Learn the theory Data Structures and Algorithms PCCST303 Scheme and Assessments Experiment List and References Lab Assignments Format of the Lab Record Lab Cycle ( Mandatory Programs) 1.Polynomial Addition Using Arrays 2.Sparse Matrix- Transpose and Addition 3.Stack    Implement  stack using array    Infix to Postfix Conversion and Evaluation 4.Queue    Queue using array     Circular Queue using array     Double ended Queue using array 5.Singly Linked List      Singly  Linked list and operations     Stack using linked list     Queue using linked list    Polynomial addition using linked list    Polynomial multiplication using linked list     Priority Queue-Post office customers simulation     Circular Queue using Linked List 6. Doubly Linked List      Doubly Linked List- Operations     Double Ended Queue ...
Read more

Sparse Matrix - Transpose and Addition

Image
  A sparse matrix is a special type of matrix in which most of the elements are zero or have some default value. In contrast, a dense matrix is one in which most of the elements are non-zero. Sparse matrices are used in various fields, including computer science, numerical analysis, and scientific computing, when dealing with large datasets or systems where efficiency and memory usage are crucial.   As a rule of thumb, if 2/3 of the total elements in a matrix are zeros, it can be called a sparse matrix . Using a sparse matrix representation — where only the non-zero values are stored — the space used for representing data and the time for scanning the matrix are reduced significantly. In many real-world problems — like graphs, networks, or scientific simulations — the majority of elements in the matrix are zero . Such a matrix is called a Sparse Matrix . Formally: A matrix in which the number of zero elements is significantly greater than the number of non-zero elements. ...
Read more

Polynomial Addition using Arrays

Polynomial  Addition We can represent a polynomial as a collection of terms and every term is having a coefficient and exponent. So, we can represent this as a list of terms having coefficients and exponents.  Each term of a polynomial (like 3 x 2 3x^2 , 5 x 1 5x^1 , − 7 x 0 -7x^0 ) can be stored in a structure having two parts: coefficient (like 3, 5, -7) exponent (like 2, 1, 0) An array of such structures represents the whole polynomial. Structure Definition (Example in C) struct Term { int coeff; // Coefficient of the term int expo; // Exponent of the term }; And then you can declare: struct Term poly1 [10], poly2 [10], polyResult [20]; to represent polynomials. Algorithm to Add Two Polynomials Assumption : Both polynomials are sorted in decreasing order of exponents . Steps : Initialize three pointers (indexes): i = 0 for first polynomial (poly1), j = 0 for second polynomial (poly2), k = 0 for result polynomial (polyR...
Read more