Two Bucket in Crystal: Complete Solution & Deep Dive Guide
The Ultimate Guide to Solving the Two Bucket Problem in Crystal
The Two Bucket problem, a classic water jug riddle, is a foundational challenge in computer science that tests your ability to model states and navigate them algorithmically. This guide provides a complete, step-by-step solution in Crystal, exploring the logic, implementation, and core computer science principles behind finding the most efficient path to the goal.
Ever found yourself watching an action movie like Die Hard and thinking, "That's a clever puzzle, but how would I solve it with code?" The scene where the heroes must measure a precise amount of water using two jugs of different sizes is a perfect real-world analogy for a classic algorithmic challenge. It’s not just about randomly pouring water; it’s about finding the most efficient sequence of actions.
This feeling of being stuck on a seemingly simple logic puzzle is common for developers. You know there's a systematic way to solve it, but translating that intuition into a robust, bug-free program can be daunting. You're not just solving a riddle; you're building a miniature search engine that explores possibilities to find the optimal answer.
In this deep-dive tutorial, we will demystify the Two Bucket problem completely. We will walk you through building a solution from scratch using the elegant and high-performance Crystal language. You will learn how to model the problem, implement a state-space search using a Breadth-First Search (BFS) algorithm, and understand why this approach guarantees the most efficient solution. By the end, you'll have a powerful new problem-solving framework in your developer toolkit.
What is the Two Bucket Problem?
At its core, the Two Bucket problem is a logic puzzle that involves state management and optimization. The premise is simple, but the solution requires careful algorithmic thinking. It's a staple in programming education and technical interviews because it effectively tests a candidate's problem-solving and modeling skills.
The Core Challenge Explained
You are given the following components:
- Bucket One: A bucket with a specific, fixed capacity (e.g., 5 liters).
- Bucket Two: Another bucket with a different fixed capacity (e.g., 3 liters).
- Goal: A target volume of water to be measured in one of the buckets (e.g., 4 liters).
- Starting Bucket: The bucket that is initially filled to its capacity.
The objective is to determine the minimum number of actions required to reach the goal state. You also need to report which bucket contains the goal amount and how much water is in the other bucket at the end.
The Rules of the Game
You can only perform a limited set of actions, one at a time. These actions represent the transitions between different states of the system.
- Fill: Fill a bucket completely from an infinite water source. This is usually the starting action.
- Empty: Pour all the water out of a bucket.
- Pour (Transfer): Pour water from one bucket into the other until one of two conditions is met:
- The source bucket becomes empty.
- The destination bucket becomes full.
You cannot partially fill a bucket from the source or partially empty a bucket onto the ground. Every action is precise and follows these constraints, which is what makes it a solvable algorithmic problem rather than a guessing game.
Why This Problem is a Cornerstone of Algorithmic Thinking
The Two Bucket problem isn't just a brain teaser; it's a simplified model for a vast category of real-world computational problems. Understanding how to solve it equips you with a mental framework applicable to complex domains like logistics, network routing, and artificial intelligence.
It Teaches State-Space Search
The most crucial concept this problem teaches is state-space search. A "state" is a snapshot of the system at a given moment—in this case, the amount of water in bucket one and bucket two (b1, b2). The "state space" is the set of all possible states you can reach.
The actions (fill, empty, pour) are the "transitions" that move you from one state to another. The problem then becomes: can you find a path of transitions from your initial state (e.g., (5, 0)) to a goal state (e.g., (4, y) or (x, 4))? More importantly, can you find the shortest path?
This is the exact foundation behind GPS navigation (finding the shortest route from A to B), solving a Rubik's Cube, or even a chess engine calculating the best sequence of moves.
Choosing the Right Algorithm: BFS vs. DFS
This problem forces you to think about which search algorithm to use. A Breadth-First Search (BFS) explores the state space layer by layer. It checks all states reachable in 1 move, then all states reachable in 2 moves, and so on. This property guarantees that the first time it finds the goal state, it has found it via the shortest possible path.
A Depth-First Search (DFS), on the other hand, explores as far as possible down one path before backtracking. While it might find a solution, it offers no guarantee that it's the most optimal one. For a problem that asks for the "minimum number of actions," BFS is the clear and correct choice.
● Initial State (e.g., 5, 0)
│
▼
┌─────────────────┐
│ Queue of States │
└────────┬────────┘
│
▼
┌─────────────────┐
│ Dequeue Current │
│ State │
└────────┬────────┘
│
▼
◆ Is it the Goal?
╱ ╲
Yes (Found!) No
│ │
▼ ▼
┌────────┐ ┌─────────────────┐
│ Return │ │ Generate All │
│ Result │ │ Possible Next │
└────────┘ │ States (Pour, │
│ Empty, etc.) │
└────────┬────────┘
│
▼
┌─────────────────┐
│ For each new │
│ state not yet │
│ visited... │
└───────┬─────────┘
│
▼
┌─────────────────┐
│ Enqueue it & │
│ Mark as Visited │
└───────│─────────┘
│
└───────────▶ (Loop back to Dequeue)
How to Implement the Two Bucket Solution in Crystal
Now, let's translate this theory into a working Crystal program. Crystal's strong static typing, clean syntax, and excellent performance make it a fantastic language for solving algorithmic problems like this. We will build a robust solution step by step.
Step 1: Project Setup
First, create a new Crystal project. Open your terminal and run the following commands:
crystal init app two_bucket_solver
cd two_bucket_solver
This creates a standard project structure. We will write our main logic in the src/two_bucket_solver.cr file.
Step 2: Modeling the Buckets and the State
Before we write the solver, we need to model our data. We need a way to represent the state of the system at any given time. A struct is a perfect choice in Crystal for this because states are simple data containers, and structs provide value semantics, which can help prevent accidental shared-state bugs.
Let's define a State struct to hold the water levels of both buckets and the number of moves taken to reach this state.
# Represents a snapshot of the system: water in each bucket and move count.
struct State
property b1 : Int32
property b2 : Int32
property moves : Int32
def initialize(@b1, @b2, @moves)
end
end
We'll also create a main class, TwoBucket, to encapsulate the entire logic. It will take the bucket capacities, the goal amount, and the starting bucket as input.
class TwoBucket
# ... properties and initialize method will go here ...
def initialize(bucket_one_cap : Int32, bucket_two_cap : Int32, goal : Int32, start_bucket : String)
# ... initialization logic ...
end
end
Step 3: The Core Solver Logic (Breadth-First Search)
The heart of our solution is the solve method. This method will implement the BFS algorithm we discussed. Here's the plan:
- Queue: We'll use a Crystal
Arrayas a queue to store the states we need to visit. We'll add the initial state to it. - Visited Set: We'll use a
Setto keep track of states we've already processed. This is crucial to prevent infinite loops (e.g., pouring back and forth between the same two states). - The Loop: We'll loop as long as the queue is not empty. In each iteration, we will:
- Dequeue the current state.
- Check if it's the goal state. If yes, we're done!
- If not, generate all valid next states from the current one.
- For each new state, if we haven't visited it before, add it to the queue and the visited set.
This process systematically explores the state space, guaranteeing we find the shortest path.
ASCII Diagram: The BFS Solver Loop
● Start `solve` method
│
├─ Initialize `queue` with initial state
├─ Initialize `visited` set with initial state
│
▼
┌──────────────────┐
│ while queue is not empty │
└─────────┬────────┘
│
▼
┌────────────────┐
│ current = queue.shift │
└─────────┬──────┘
│
▼
◆ current state == goal?
╱ ╲
Yes No
│ │
▼ ▼
┌───────────────┐ ┌─────────────────────┐
│ Return result │ │ Generate next states: │
│ (moves, goal │ │ - Pour b1 to b2 │
│ bucket, etc.) │ │ - Pour b2 to b1 │
└───────────────┘ │ - Empty b1 │
│ - Empty b2 │
│ - Fill b1 │
│ - Fill b2 │
└──────────┬────────────┘
│
▼
┌───────────────────┐
│ for each new_state │
└──────────┬──────────┘
│
▼
◆ visited.includes?(new_state)?
╱ ╲
No Yes (ignore)
│
▼
┌───────────────────┐
│ queue.push(new_state) │
│ visited.add(new_state)│
└───────────────────┘
Step 4: The Complete Crystal Solution
Here is the full, commented code for src/two_bucket_solver.cr. It combines all the concepts we've discussed into a single, cohesive class.
# Solves the classic "Two Bucket" water jug riddle.
# This implementation uses a Breadth-First Search (BFS) to find the
# shortest sequence of moves to measure a target amount of water.
class TwoBucket
property moves : Int32
property goal_bucket : String
property other_bucket : Int32
# A private struct to represent the state (water levels) of the two buckets.
# We use a struct to make it a value type, which is ideal for states.
# We override `hash` and `eql?` to allow the Set to correctly identify unique states.
private struct BucketState
property b1 : Int32
property b2 : Int32
def initialize(@b1, @b2)
end
def hash(hasher)
hasher.int(@b1).int(@b2)
end
def eql?(other : BucketState)
@b1 == other.b1 && @b2 == other.b2
end
end
# A private struct to hold the state and the number of moves to reach it.
# This is what we'll store in our BFS queue.
private struct QueueItem
property state : BucketState
property moves : Int32
def initialize(@state, @moves)
end
end
# Initializes the solver with bucket capacities, the goal, and which bucket starts full.
def initialize(bucket_one_cap : Int32, bucket_two_cap : Int32, goal : Int32, start_bucket : String)
@b1_cap = bucket_one_cap
@b2_cap = bucket_two_cap
@goal = goal
@start_bucket = start_bucket
# Edge case: if goal is larger than both buckets, it's impossible.
if @goal > @b1_cap && @goal > @b2_cap
raise "Goal cannot be reached as it's larger than both buckets"
end
solution = solve()
@moves = solution[:moves]
@goal_bucket = solution[:goal_bucket]
@other_bucket = solution[:other_bucket]
end
private def solve
# The queue for our BFS, storing items of {state, moves}.
queue = [] of QueueItem
# A set to keep track of visited states to avoid cycles and redundant work.
visited = Set(BucketState).new
# Determine the initial state based on the `start_bucket` parameter.
initial_state = if @start_bucket == "one"
BucketState.new(@b1_cap, 0)
else
BucketState.new(0, @b2_cap)
end
# Add the first state to the queue and visited set.
queue.push(QueueItem.new(initial_state, 1))
visited.add(initial_state)
while item = queue.shift?
current_state = item.state
current_moves = item.moves
# Check if the current state is a solution.
if current_state.b1 == @goal
return {moves: current_moves, goal_bucket: "one", other_bucket: current_state.b2}
elsif current_state.b2 == @goal
return {moves: current_moves, goal_bucket: "two", other_bucket: current_state.b1}
end
# Generate all possible next states from the current one.
next_states = generate_next_states(current_state)
next_states.each do |next_state|
# If we haven't seen this state before, add it to our queue and visited set.
unless visited.includes?(next_state)
visited.add(next_state)
queue.push(QueueItem.new(next_state, current_moves + 1))
end
end
end
# If the queue becomes empty and we haven't found a solution, it's impossible.
# This can happen if the goal is not achievable with the given bucket sizes (e.g., due to GCD properties).
raise "No solution found"
end
# Generates all valid subsequent states from a given state.
private def generate_next_states(state)
states = [] of BucketState
b1, b2 = state.b1, state.b2
# 1. Pour from bucket 1 to bucket 2
pour_amount_1_to_2 = Math.min(b1, @b2_cap - b2)
states << BucketState.new(b1 - pour_amount_1_to_2, b2 + pour_amount_1_to_2)
# 2. Pour from bucket 2 to bucket 1
pour_amount_2_to_1 = Math.min(b2, @b1_cap - b1)
states << BucketState.new(b1 + pour_amount_2_to_1, b2 - pour_amount_2_to_1)
# 3. Empty bucket 1
states << BucketState.new(0, b2)
# 4. Empty bucket 2
states << BucketState.new(b1, 0)
# 5. Fill bucket 1
states << BucketState.new(@b1_cap, b2)
# 6. Fill bucket 2
states << BucketState.new(b1, @b2_cap)
# Return only unique states different from the original state.
states.uniq.select { |s| s != state }
end
end
Step 5: Detailed Code Walkthrough
Let's break down the most important parts of the code to ensure every line is crystal clear.
The `BucketState` Struct:
We use a `private struct` here for a reason. `structs` in Crystal are value types, meaning they are copied when passed around. This is perfect for representing states, as we don't want to accidentally modify a state that's already in our `visited` set. We override `hash` and `eql?` so that the `Set(BucketState)` can correctly determine if two states like `BucketState.new(3, 5)` are identical.
The `initialize` Method:
This is the public entry point. It takes the problem parameters, immediately calls the private `solve` method, and then stores the results in public properties (`moves`, `goal_bucket`, `other_bucket`). This follows the "constructor does the work" pattern, common in challenges from the kodikra learning path.
The `solve` Method:
This is the BFS engine. The `queue` holds `QueueItem` objects, which bundle a `BucketState` with its corresponding move count. The `while item = queue.shift?` is an idiomatic Crystal way to loop while dequeuing items. Inside the loop, the first thing we do is check for a solution. If we find one, we return immediately. Because we are using BFS, this first found solution is guaranteed to be one with the minimum number of moves.
The `generate_next_states` Method:
This method is the "transition function" of our state machine. Given a state, it calculates all 6 possible next states: pour 1->2, pour 2->1, empty 1, empty 2, fill 1, and fill 2. The logic for pouring is the most complex part: `pour_amount = Math.min(source_amount, destination_space_available)`. This single line correctly handles both cases: the source bucket becoming empty or the destination bucket becoming full.
Alternative Approaches & Performance Considerations
While BFS is an excellent general-purpose solution, it's worth knowing about other ways to think about this problem.
Mathematical Approach (Using GCD)
This problem can also be analyzed using number theory. A solution is only possible if the goal amount is a multiple of the greatest common divisor (GCD) of the two bucket capacities. For example, if you have buckets of size 6 and 9, the GCD is 3. You can only measure volumes that are multiples of 3 (3, 6, 9, 12...). You could never measure 4 liters.
While a mathematical formula can determine if a solution exists and sometimes find a solution, it doesn't naturally provide the step-by-step actions. The BFS simulation approach is more illustrative and demonstrates a broader algorithmic skill.
Pros and Cons of BFS vs. Mathematical Solution
| Aspect | Breadth-First Search (BFS) | Mathematical (GCD) Approach |
|---|---|---|
| Guarantees Optimality | Yes, always finds the shortest path in terms of moves. | Not directly. It proves possibility but doesn't find the shortest move sequence. |
| Provides Steps | Yes, the path can be reconstructed to show every action taken. | No, it typically only confirms if a solution exists. |
| Complexity | Can be memory-intensive if the state space is very large. | Extremely fast (computationally trivial). |
| Generalizability | Very high. The same pattern applies to mazes, puzzles, routing, etc. | Very low. It's specific to problems that can be modeled as linear Diophantine equations. |
| Educational Value | Excellent for teaching core CS search algorithms. | Good for teaching number theory applications. |
Frequently Asked Questions (FAQ)
- Why use Breadth-First Search (BFS) instead of Depth-First Search (DFS)?
- BFS explores the state space level by level. This means it checks all possible 1-move solutions, then all 2-move solutions, and so on. This guarantees that the first time it finds the goal, it has done so in the minimum number of moves. DFS dives down one path and might find a non-optimal solution first.
- What happens if the goal amount is impossible to reach?
- In our BFS implementation, the `queue` will eventually become empty if all reachable states have been explored without finding the goal. In this scenario, our `solve` method would finish the `while` loop and, in a more robust implementation, would return an indication of failure or raise an error, as our current code does.
- How does Crystal's type system help in this solution?
- Crystal's static type system provides safety and clarity. By defining `BucketState` and `QueueItem` structs, we get compile-time checks that ensure we're not mixing up data. For example, the compiler ensures our `visited` set only ever contains `BucketState` objects, preventing subtle runtime bugs.
- What is the difference between a `class` and a `struct` in Crystal?
- A `class` creates reference-type objects, meaning variables hold a pointer to the object on the heap. A `struct` creates value-type objects, meaning the data itself is copied. For small, data-centric objects like a state, `structs` are often more efficient and safer as they prevent unintended side effects from shared references.
- Can this logic be applied to a problem with three or more buckets?
- Absolutely! The core BFS algorithm remains the same. You would simply expand the `BucketState` to hold more values (e.g., `property b1, b2, b3`) and the `generate_next_states` method would need to handle more pouring combinations (1->2, 1->3, 2->1, 2->3, etc.). The fundamental pattern of a queue and a visited set is perfectly scalable.
- Is recursion a good fit for this problem?
- You could implement a search using recursion (which would naturally be a DFS). However, for finding the shortest path, an iterative BFS with a queue is standard practice. A deep recursive search can also lead to a stack overflow error if the solution path is very long, a problem the queue-based approach avoids.
- How can I optimize this solution further?
- For this specific problem, the BFS is already optimal in finding the shortest path. Further micro-optimizations are unlikely to yield significant gains. However, one could implement a bi-directional BFS, searching from both the start and end states simultaneously and meeting in the middle, which can drastically reduce the search space in some problems.
Conclusion: From Puzzle to Pattern
The Two Bucket problem is far more than a simple riddle; it's a gateway to understanding fundamental algorithms that power complex software. By implementing a solution in Crystal, we've seen how to model a problem's state, use Breadth-First Search to explore possibilities efficiently, and leverage language features like structs and sets to write clean, safe, and performant code.
The pattern you've learned here—representing problems as a graph of states and using search algorithms to find a path—is one of the most powerful tools in a programmer's arsenal. You can now apply this thinking to solve other puzzles, navigate game maps, or even optimize real-world logistical challenges.
To continue your journey, try modifying the code to handle three buckets or to print the exact sequence of moves that leads to the solution. Each variation will deepen your understanding and make you a more confident problem-solver.
Disclaimer: All code snippets and solutions are based on Crystal 1.12+ and reflect modern language features and best practices as of the time of writing. The core algorithmic concepts are timeless.
Ready to tackle more challenges? Explore our complete Crystal 6 learning roadmap to continue building your skills. For a broader look at the language, check out our comprehensive Crystal programming language guide.
```