Home
6
Coding Tutorial

Two Bucket in Common-lisp: Complete Solution & Deep Dive Guide

turned on MacBook Air on desk

The Complete Guide to Solving the Two Bucket Problem in Common Lisp

The Two Bucket problem is a classic computer science puzzle that tests your ability to think algorithmically. It involves finding the minimum number of steps to measure a specific volume of liquid using two buckets of different capacities. This guide provides a comprehensive solution in Common Lisp, breaking down the logic from state-space search theory to a fully implemented Breadth-First Search algorithm.

The Challenge on the Silver Screen and In Your Code Editor

You've likely seen it in a movie: the hero, against a ticking clock, must measure exactly four gallons of water using only a three-gallon jug and a five-gallon jug. It's a tense, dramatic moment that hinges on pure logic. This isn't just Hollywood fiction; it's the core of the "Two Bucket" problem, a puzzle that has stumped and intrigued thinkers for ages.

For developers, this puzzle represents a common and frustrating challenge: how do you translate a real-world, physical process into a clean, efficient algorithm? You might find yourself scribbling diagrams, getting lost in endless loops, or wondering if a solution is even possible. The frustration is real, but the solution is elegant.

This article promises to demystify the Two Bucket problem entirely. We will not only provide a robust solution in Common Lisp but also dive deep into the underlying theory of state-space search and graph traversal. By the end, you'll understand not just *how* the code works, but *why* it's the optimal way to solve this classic challenge, turning a head-scratcher into a powerful tool in your algorithmic arsenal.

What Exactly Is the Two Bucket Problem?

The Two Bucket problem is a type of measurement puzzle. The setup is simple: you are given two buckets, each with a known, fixed capacity. You are also given a target volume of liquid to measure. The goal is to determine the sequence of actions that will result in one of the buckets containing the exact target amount, and to find the solution that requires the fewest possible actions.

To solve it, you can only perform a limited set of actions:

  • Fill: You can completely fill either bucket from an infinite source of water.
  • Empty: You can completely empty the contents of either bucket.
  • Pour: You can pour water from one bucket into the other. The pouring stops when either the source bucket becomes empty or the destination bucket becomes full, whichever happens first.

The state of the system at any given moment can be defined by the amount of water in each bucket. The problem is essentially asking us to find the shortest path from an initial state (both buckets empty) to a goal state (one bucket contains the target volume). This structure makes it a perfect candidate for graph traversal algorithms.

Why Is It a Foundational Computer Science Puzzle?

This problem isn't just a brain teaser; it's a fundamental exercise in computer science for several key reasons. It serves as an excellent, tangible introduction to the concept of state-space search. A "state" is a snapshot of the system—in our case, the volumes (bucket-one, bucket-two). Each action (fill, empty, pour) is a "transition" that moves us from one state to another.

The collection of all possible states and the transitions between them forms an abstract graph. The problem then becomes finding the shortest path from the starting node (0, 0) to any node where one of the bucket levels matches the goal. This is where algorithms like Breadth-First Search (BFS) and Depth-First Search (DFS) come into play.

BFS is particularly well-suited for this problem because it explores the graph layer by layer. It checks all possible states reachable in one move, then all states reachable in two moves, and so on. This guarantees that the first time we find a solution, it will be one with the minimum number of moves, which is exactly what the problem asks for.

How to Model and Solve the Problem in Common Lisp

To solve this algorithmically, we need to translate the physical actions into a data structure and a search process. We will use a Breadth-First Search (BFS) algorithm, which requires two main data structures: a queue to manage which states to visit next, and a way to track states we've already visited to avoid infinite loops.

Defining the State

A "state" in our problem needs to capture all the necessary information to proceed. This includes:

  • The current volume in the first bucket.
  • The current volume in the second bucket.
  • The number of moves taken to reach this state.

In Common Lisp, a simple list is a perfectly idiomatic way to represent this. For example, a state could be represented as (list moves (list bucket-one-level bucket-two-level)).

The BFS Algorithm Flow

The BFS algorithm provides a systematic way to explore the state space. It ensures we find the shortest path by exploring level by level.

    ● Start
    │
    ▼
  ┌───────────────────────────┐
  │ Initialize Queue & Visited│
  │  - Add start state (0,0)  │
  └────────────┬──────────────┘
               │
               ▼
  ┌───────────────────────────┐
  │ Loop while Queue not empty│
  └────────────┬──────────────┘
               │
      ╭────────▼────────╮
      │ Dequeue current │
      │ state           │
      ╰────────┬────────╯
               │
               ▼
        ◆ Is it Goal? ◆
       ╱               ╲
     Yes                No
      │                  │
      ▼                  ▼
  ┌─────────┐      ┌─────────────────────┐
  │ Return  │      │ Generate next states│
  │ Result  │      │ (Fill, Empty, Pour) │
  └─────────┘      └──────────┬──────────┘
                              │
                              ▼
                       ┌──────────────────────┐
                       │ For each new state:  │
                       │ If not visited,      │
                       │ add to Visited &     │
                       │ enqueue it.          │
                       └──────────────────────┘
                              │
                              └─────────────────┐
                                                │
                                                ▼ (Loop back)

Let's break down this flow:

  1. Initialization: We start with a queue containing only the initial state: 0 moves, and both buckets empty (0, 0). We also initialize a set or hash table to keep track of visited states, adding (0, 0) to it.
  2. Loop: We enter a loop that continues as long as there are states in the queue to explore.
  3. Dequeue: Inside the loop, we remove the first state from the queue. This is the current state we are examining.
  4. Goal Check: We check if the current state is a solution. Does one of the buckets contain the target volume? If yes, we have found the shortest path and can return the result.
  5. Generate Next States: If it's not the goal, we generate all possible valid states that can be reached from the current state in one move. This involves applying all six possible actions (fill b1, fill b2, empty b1, empty b2, pour b1->b2, pour b2->b1).
  6. Enqueue Valid States: For each newly generated state, we check if we have visited it before. If not, we add it to our set of visited states and add it to the back of the queue. This "visit check" is crucial to prevent getting stuck in cycles (e.g., filling a bucket and immediately emptying it, over and over).
  7. Termination: If the queue becomes empty and we haven't found a solution, it means the target volume is unreachable.

Where the Logic Lives: The Complete Common Lisp Solution

Now, let's translate the BFS strategy into a working Common Lisp implementation. This solution is designed for clarity and follows the logic discussed. We will use a simple list as our queue and a hash-table for efficient tracking of visited states.

This code is part of the exclusive Common Lisp learning path on kodikra.com, designed to build strong algorithmic thinking.


(defpackage :two-bucket
  (:use :cl)
  (:export :measure))

(in-package :two-bucket)

;;; Main function to solve the two-bucket problem.
;;; It uses a Breadth-First Search (BFS) algorithm.
(defun measure (bucket-one-size bucket-two-size goal start-bucket)
  "Solves the two-bucket problem to find the minimum number of moves to reach a goal volume."
  
  ;; A hash table is used for O(1) average time complexity for lookups of visited states.
  (let ((visited (make-hash-table :test 'equal))
        ;; A queue to hold states to visit: '( (moves (b1-level b2-level)) ... )
        (queue (list)))

    ;; Determine the starting state based on which bucket is filled first.
    (let* ((start-state (if (eq start-bucket :one)
                            (list bucket-one-size 0)
                            (list 0 bucket-two-size)))
           (initial-queue-item (list 1 start-state))) ; Start with 1 move (the first fill)
      
      (setf (gethash start-state visited) t)
      (setf queue (append queue (list initial-queue-item))))

    ;; --- The BFS Main Loop ---
    (loop while queue
          do (let* ((current-item (pop queue))
                    (moves (first current-item))
                    (levels (second current-item))
                    (b1 (first levels))
                    (b2 (second levels)))

               ;; --- Goal Check ---
               ;; If the goal is found, construct and return the result.
               (when (= b1 goal)
                 (return-from measure (list moves :one b2)))
               (when (= b2 goal)
                 (return-from measure (list moves :two b1)))

               ;; --- Generate Next States ---
               ;; Explore all possible moves from the current state.
               (let ((next-states (generate-next-states b1 b2 bucket-one-size bucket-two-size)))
                 (dolist (next-level next-states)
                   ;; If a state has not been visited, add it to the visited table and the queue.
                   (unless (gethash next-level visited)
                     (setf (gethash next-level visited) t)
                     (setf queue (append queue (list (list (1+ moves) next-level)))))))))))

;;; Helper function to generate all possible next states from a given state.
(defun generate-next-states (b1 b2 size1 size2)
  "Generates a list of all reachable states in one move."
  (let ((states '()))
    ;; 1. Empty bucket one
    (push (list 0 b2) states)
    ;; 2. Empty bucket two
    (push (list b1 0) states)
    ;; 3. Fill bucket one
    (push (list size1 b2) states)
    ;; 4. Fill bucket two
    (push (list b1 size2) states)
    
    ;; 5. Pour from bucket one to bucket two
    (let* ((pour-amount (min b1 (- size2 b2)))
           (new-b1 (- b1 pour-amount))
           (new-b2 (+ b2 pour-amount)))
      (push (list new-b1 new-b2) states))
      
    ;; 6. Pour from bucket two to bucket one
    (let* ((pour-amount (min b2 (- size1 b1)))
           (new-b1 (+ b1 pour-amount))
           (new-b2 (- b2 pour-amount)))
      (push (list new-b1 new-b2) states))
      
    ;; Return a list of unique next states.
    (remove-duplicates states :test 'equal)))

A Deep Dive: Step-by-Step Code Walkthrough

Understanding the code line by line is crucial for mastering the concept. Let's dissect the solution to see how each part contributes to solving the puzzle.

The Main measure Function

This is the entry point of our solution. It orchestrates the entire BFS process.


(defun measure (bucket-one-size bucket-two-size goal start-bucket)
  ...
)

It takes the sizes of the two buckets, the target goal volume, and which bucket to fill first (:one or :two) as input.

Initialization Phase


(let ((visited (make-hash-table :test 'equal))
      (queue (list)))
  • visited: We initialize a hash-table. This is a critical optimization. Checking for an element in a list takes linear time (O(n)), but looking up a key in a hash table takes, on average, constant time (O(1)). Since we will be checking for visited states frequently, a hash table is far more efficient. We use :test 'equal because our keys are lists representing states, like (3 5), and we need to compare them by value.
  • queue: We initialize an empty list to serve as our queue. In Common Lisp, we can use a simple list and append to the end (enqueue) and pop from the front (dequeue).

Setting Up the Starting State


(let* ((start-state (if (eq start-bucket :one)
                        (list bucket-one-size 0)
                        (list 0 bucket-two-size)))
       (initial-queue-item (list 1 start-state)))
  
  (setf (gethash start-state visited) t)
  (setf queue (append queue (list initial-queue-item))))

The problem specifies that the first action is to fill one of the buckets. We determine the initial state based on the start-bucket parameter. If it's :one, the state after the first move is (bucket-one-size, 0). This first action counts as move number 1. We then add this initial item (list 1 start-state) to the queue and mark the state as visited.

The BFS Core Loop


(loop while queue
      do (let* ((current-item (pop queue))
                (moves (first current-item))
                (levels (second current-item))
                (b1 (first levels))
                (b2 (second levels)))
           ...
))

This is the heart of the algorithm. The loop continues as long as the queue is not empty. In each iteration:

  1. We pop the first item off the queue. This gives us the state that has been waiting the longest, which is the core principle of BFS.
  2. We destructure the item to get the current number of moves and the water levels b1 and b2.

The Goal Check


(when (= b1 goal)
  (return-from measure (list moves :one b2)))
(when (= b2 goal)
  (return-from measure (list moves :two b1)))

Inside the loop, the first thing we do is check if we've reached our goal. If the amount in bucket one (b1) equals the goal, we've succeeded. We use return-from measure to exit the entire function immediately and return the required result format: the total number of moves, which bucket contains the goal amount, and the amount in the other bucket.

Generating and Enqueuing Next States


(let ((next-states (generate-next-states b1 b2 bucket-one-size bucket-two-size)))
  (dolist (next-level next-states)
    (unless (gethash next-level visited)
      (setf (gethash next-level visited) t)
      (setf queue (append queue (list (list (1+ moves) next-level)))))))

If the current state is not the goal, we must explore its neighbors.

  1. We call our helper function, generate-next-states, which returns a list of all possible states reachable in one move.
  2. We iterate through each next-level using dolist.
  3. The crucial check: (unless (gethash next-level visited) ...). We only process the new state if it has not been visited before. This prevents infinite loops and redundant computations.
  4. If the state is new, we mark it as visited in our hash table and then enqueue it. The new item added to the queue has its move count incremented by one: (1+ moves).

The generate-next-states Helper Function

This function is responsible for modeling the physical actions of pouring, filling, and emptying.

    State (b1, b2)
    │
    ├─ Fill B1 ──────────→ (size1, b2)
    │
    ├─ Fill B2 ──────────→ (b1, size2)
    │
    ├─ Empty B1 ─────────→ (0, b2)
    │
    ├─ Empty B2 ─────────→ (b1, 0)
    │
    ├─ Pour B1 to B2 ────→ (b1 - p, b2 + p) where p = min(b1, size2 - b2)
    │
    └─ Pour B2 to B1 ────→ (b1 + p, b2 - p) where p = min(b2, size1 - b1)

The logic for pouring is the most complex part. For pouring from bucket one to bucket two, the amount to pour (pour-amount) is the smaller of two values: the amount of water currently in bucket one (b1), or the remaining space in bucket two (size2 - b2). This correctly models the constraint that pouring stops when the source is empty or the destination is full.

Finally, (remove-duplicates states :test 'equal) cleans up the list, as some actions might result in the same state (e.g., trying to empty an already empty bucket results in no change).

Evaluating the Approach: Pros, Cons, and Risks

While Breadth-First Search is the ideal algorithm for this problem, it's important to understand its trade-offs and potential risks, especially in different contexts.

Aspect Pros of BFS (Our Approach) Cons & Risks
Optimality Guaranteed to find the solution with the minimum number of moves. Because it explores level by level, the first solution it encounters is, by definition, the shortest. Not applicable for this problem, as optimality is the primary goal. For other problems, "shortest" might not mean "best" if moves have different costs.
Completeness If a solution exists, BFS is guaranteed to find it. If the state space is infinite and no solution exists, BFS will run forever. (This is not an issue here as our state space is finite).
Memory Usage The logic is relatively straightforward to implement. BFS can be very memory-intensive. It needs to store all nodes at the current depth frontier in the queue. For problems with a very large branching factor, this can lead to high memory consumption.
Time Complexity The time complexity is O(V + E), where V is the number of states (vertices) and E is the number of transitions (edges). In our case, V is at most (size1 + 1) * (size2 + 1). For very large bucket sizes, the number of states can grow quadratically, making the search slow. For instance, buckets of size 1000x1000 have over a million possible states.
Alternative (DFS) Superior to Depth-First Search (DFS) for this problem because DFS is not guaranteed to find the shortest path first. DFS might dive deep down a very long, suboptimal path. DFS would use less memory (O(depth)), but at the cost of optimality, making it unsuitable for the stated goal.

Frequently Asked Questions (FAQ)

1. What happens if the goal is impossible to reach?

If the goal is unreachable, the BFS algorithm will explore all possible states. Eventually, the queue will become empty. In our current implementation, the loop will terminate, and the function will implicitly return NIL, which is the standard Common Lisp way of indicating failure or no result. A solution is provably impossible if the goal amount is not a multiple of the greatest common divisor (GCD) of the two bucket sizes.

2. Why use a hash table for `visited` states instead of a list?

Performance. Checking if an item exists in a list (using member or find) requires scanning the list, an operation with O(n) time complexity, where n is the number of visited states. A hash table provides an average lookup time of O(1). As the number of states grows, the hash table is significantly faster and is the standard choice for implementing BFS efficiently.

3. Can this problem be solved with recursion?

Yes, but it's less natural for a shortest-path problem. A recursive solution would more naturally implement a Depth-First Search (DFS). While you could implement BFS recursively, it's more complex and less intuitive than the iterative queue-based approach. A naive recursive DFS would also likely exceed the maximum stack depth for non-trivial problems and wouldn't guarantee the shortest path.

4. How does the Greatest Common Divisor (GCD) relate to this problem's solvability?

This is a key insight from number theory (related to Bézout's identity). Any amount of water that can be measured using two buckets of size M and N must be a multiple of gcd(M, N). Therefore, a solution exists if and only if the goal is a multiple of the GCD of the two bucket sizes. You could add a check at the beginning of the function, (unless (= 0 (mod goal (gcd bucket-one-size bucket-two-size))) (return-from measure nil)), to fail early on impossible goals.

5. What are some real-world applications of state-space search?

State-space search is a cornerstone of AI and robotics. Applications include: route planning in GPS systems (finding the shortest path between two points), solving puzzles like Rubik's Cubes, game AI (e.g., finding the best move in chess by exploring future game states), and robotic motion planning (finding a path for a robot arm to move without collisions).

6. Is Common Lisp a good language for this type of algorithmic problem?

Absolutely. Common Lisp is excellent for symbolic computation and algorithmic problems. Its powerful list manipulation capabilities, flexible data structures (like hash tables and lists), and interactive development environment (REPL) make it a joy to use for prototyping and solving complex logic puzzles like this one.

7. How can I optimize this solution further?

For very large inputs, you could optimize queue management. Using a more efficient queue data structure than a standard list (where append can be slow) might provide a marginal speedup. However, the current implementation with a hash table for the visited set is already quite efficient and idiomatic for Common Lisp. The biggest optimization would be the GCD check mentioned earlier to handle impossible cases instantly.

Conclusion: From Puzzles to Practical Algorithms

The Two Bucket problem, while simple on the surface, provides a rich ground for understanding fundamental computer science concepts. We've journeyed from a high-level puzzle to a concrete, efficient implementation in Common Lisp. The key takeaway is the power of modeling problems as a state-space graph and systematically exploring that graph with an algorithm like Breadth-First Search.

By using a queue to manage exploration and a hash table to track visited states, we built a solution that is not only correct but also optimal, always finding the path with the minimum number of steps. This pattern of thinking—defining states, transitions, and applying a search algorithm—is a powerful technique that you can apply to a wide range of algorithmic challenges.

This module from the kodikra.com curriculum is designed to build exactly this kind of foundational problem-solving skill. Ready for your next challenge? Explore the complete Common Lisp 6 learning path to continue honing your skills. To dive deeper into the language itself, check out our comprehensive Common Lisp resources.

Disclaimer: The code in this article is written for a modern Common Lisp environment (e.g., SBCL 2.4.0+). The logic is universal, but specific function names and package definitions may vary across different Lisp implementations.

Published by Kodikra — Your trusted Common-lisp learning resource.

Post a Comment