Exercism - Two Bucket

Preparation

Before we click on our next exercise, let’s see what concepts of DART we need to consider

So we need to use the following concepts.

Typedef

Typedef creates a type alias, giving a name to a type. It’s perfect for making complex types like records more readable and reusable.

// Define a type alias for a record
typedef Result = ({int moves, String goalBucket, int otherBucket});

void main() {
  // Use the typedef
  Result result = (moves: 3, goalBucket: "one", otherBucket: 5);
  
  // Access fields
  print(result.moves); // 3
  print(result.goalBucket); // "one"
  print(result.otherBucket); // 5
}

Records (Named Records)

Records allow you to group multiple values together with named fields. They’re perfect for returning multiple values from a function.

void main() {
  // Named record syntax: (field1: value1, field2: value2)
  var result = (moves: 3, goalBucket: "one", otherBucket: 5);
  print(result); // (moves: 3, goalBucket: one, otherBucket: 5)
  
  // Access named fields
  print(result.moves); // 3
  print(result.goalBucket); // "one"
  print(result.otherBucket); // 5
  
  // Return from function
  ({int moves, String bucket}) calculate() {
    return (moves: 3, bucket: "one");
  }
}

Classes and Constructors

Classes define blueprints for objects. Constructors initialize instances with specific values using required named parameters.

class TwoBucket {
  final int bucketOne;
  final int bucketTwo;
  final int goal;
  final String startBucket;
  
  // Constructor with required named parameters
  TwoBucket({
    required this.bucketOne,
    required this.bucketTwo,
    required this.goal,
    required this.startBucket,
  });
}

void main() {
  TwoBucket solver = TwoBucket(
    bucketOne: 3,
    bucketTwo: 5,
    goal: 1,
    startBucket: "one",
  );
}

Private Classes

Private classes (prefixed with _) are only accessible within the same library. They’re perfect for internal helper classes that shouldn’t be exposed.

class TwoBucket {
  // Public class
  int measure() {
    // Can use private class
    _State state = _State(3, 5, 1);
    return state.moves;
  }
}

// Private class - only accessible in same file
class _State {
  final int b1;
  final int b2;
  final int moves;
  
  _State(this.b1, this.b2, this.moves);
}

Breadth-First Search (BFS)

Breadth-First Search explores all nodes at the current depth before moving to the next level. It’s perfect for finding the shortest path in unweighted graphs or state spaces.

void main() {
  // BFS algorithm:
  // 1. Start with initial state in queue
  // 2. While queue not empty:
  //    a. Remove first state
  //    b. If goal reached, return
  //    c. Generate all next states
  //    d. Add unvisited states to queue
  // 3. If queue empty, no solution
  
  List<_State> queue = [];
  Set<String> visited = {};
  
  // Add initial state
  queue.add(_State(0, 0, 0));
  
  while (queue.isNotEmpty) {
    final state = queue.removeAt(0);
    final key = '${state.b1},${state.b2}';
    
    if (visited.contains(key)) continue;
    visited.add(key);
    
    // Check goal
    if (state.b1 == goal) return state;
    
    // Add next states
    queue.addAll(getNextStates(state));
  }
}

Using List as Queue

Lists can be used as queues by adding to the end (add) and removing from the front (removeAt(0)). This implements FIFO (First-In-First-Out) behavior.

void main() {
  // Use List as queue
  List<_State> queue = [];
  
  // Add to end (enqueue)
  queue.add(_State(3, 0, 1));
  queue.add(_State(0, 5, 1));
  
  // Remove from front (dequeue)
  _State first = queue.removeAt(0); // Gets _State(3, 0, 1)
  
  // Check if empty
  if (queue.isNotEmpty) {
    _State next = queue.removeAt(0); // Gets _State(0, 5, 1)
  }
  
  // Add multiple at once
  queue.addAll([
    _State(3, 2, 2),
    _State(1, 5, 2),
  ]);
}

Sets

Sets are unordered collections of unique elements. They’re perfect for tracking visited states in BFS to avoid revisiting the same state.

void main() {
  // Create set for visited states
  Set<String> visited = {};
  
  // Add states (using string keys)
  visited.add('3,0');
  visited.add('0,5');
  
  // Check if visited
  if (visited.contains('3,0')) {
    print('Already visited');
  }
  
  // Add returns true if new, false if already exists
  bool isNew = visited.add('3,0'); // false (already exists)
  bool isNew2 = visited.add('1,2'); // true (new state)
  
  // Use to filter unvisited states
  List<String> states = ['3,0', '0,5', '1,2'];
  List<String> unvisited = states.where((s) => !visited.contains(s)).toList();
}

String Interpolation

String interpolation allows you to embed expressions in strings using ${expression} or $variable. It’s perfect for creating state keys.

void main() {
  int b1 = 3;
  int b2 = 5;
  
  // String interpolation
  String key = '${b1},${b2}';
  print(key); // "3,5"
  
  // Simple variable interpolation
  String message = 'Bucket one: $b1, Bucket two: $b2';
  print(message); // "Bucket one: 3, Bucket two: 5"
  
  // Use in state tracking
  Set<String> visited = {};
  visited.add('${b1},${b2}');
}

List Methods

List methods like add(), addAll(), removeAt(), where(), and toList() are essential for queue operations and filtering.

void main() {
  List<_State> queue = [];
  
  // Add single element
  queue.add(_State(3, 0, 1));
  
  // Add multiple elements
  queue.addAll([
    _State(0, 5, 1),
    _State(3, 2, 2),
  ]);
  
  // Remove at index
  _State first = queue.removeAt(0);
  
  // Filter with where
  List<_State> valid = queue.where((s) => s.b1 > 0).toList();
  
  // Check if empty
  if (queue.isNotEmpty) {
    // Process queue
  }
}

Conditional Logic

Conditional logic (if, else if, else) is used to check conditions and apply different actions. It’s essential for state validation and goal checking.

void main() {
  int b1 = 3;
  int goal = 1;
  
  // Check if goal reached
  if (b1 == goal) {
    print('Goal reached in bucket one');
  } else if (b2 == goal) {
    print('Goal reached in bucket two');
  }
  
  // Check conditions before actions
  if (b1 < bucketOne) {
    // Can fill bucket one
  }
  
  if (b1 > 0) {
    // Can empty bucket one
  }
}

Arithmetic Operations

Arithmetic operations like addition (+), subtraction (-), and comparison (>, <) are used to calculate pour amounts and check constraints.

void main() {
  int b1 = 3;
  int b2 = 5;
  int bucketTwo = 11;
  
  // Calculate pour amount
  int amount = (b1 + b2 > bucketTwo) 
      ? bucketTwo - b2  // Fill bucket two to capacity
      : b1;              // Pour all from bucket one
  
  // Update buckets after pour
  int newB1 = b1 - amount;
  int newB2 = b2 + amount;
  
  // Check constraints
  if (b1 + b2 > bucketTwo) {
    // Will overflow, pour only what fits
  }
}

ArgumentError

ArgumentError is thrown when invalid arguments are provided. It’s used to signal impossible goals or unreachable states.

void main() {
  int goal = 20;
  int bucketOne = 3;
  int bucketTwo = 5;
  
  // Validate goal
  if (goal > bucketOne && goal > bucketTwo) {
    throw ArgumentError('Goal is impossible to reach');
  }
  
  // After BFS completes without finding solution
  if (queue.isEmpty) {
    throw ArgumentError('Goal is impossible to reach');
  }
}

Introduction

Given two buckets of different size and which bucket to fill first, determine how many actions are required to measure an exact number of liters by strategically transferring fluid between the buckets.

Instructions

There are some rules that your solution must follow:

You can only do one action at a time.
There are only 3 possible actions:
- Pouring one bucket into the other bucket until either: a) the first bucket is empty b) the second bucket is full
- Emptying a bucket and doing nothing to the other.
- Filling a bucket and doing nothing to the other.
After an action, you may not arrive at a state where the initial starting bucket is empty and the other bucket is full.

Your program will take as input:

the size of bucket one
the size of bucket two
the desired number of liters to reach
which bucket to fill first, either bucket one or bucket two

Your program should determine:

the total number of actions it should take to reach the desired number of liters, including the first fill of the starting bucket
which bucket should end up with the desired number of liters - either bucket one or bucket two
how many liters are left in the other bucket

Note: any time a change is made to either or both buckets counts as one (1) action.

Example

Bucket one can hold up to 7 liters, and bucket two can hold up to 11 liters. Let’s say at a given step, bucket one is holding 7 liters and bucket two is holding 8 liters (7,8). If you empty bucket one and make no change to bucket two, leaving you with 0 liters and 8 liters respectively (0,8), that counts as one action. Instead, if you had poured from bucket one into bucket two until bucket two was full, resulting in 4 liters in bucket one and 11 liters in bucket two (4,11), that would also only count as one action.

Another Example: Bucket one can hold 3 liters, and bucket two can hold up to 5 liters. You are told you must start with bucket one. So your first action is to fill bucket one. You choose to empty bucket one for your second action. For your third action, you may not fill bucket two, because this violates the third rule — you may not end up in a state after any action where the starting bucket is empty and the other bucket is full.

How do we solve the two bucket problem?

To solve the two bucket problem using BFS:

Initialize: Start with the starting bucket filled (first action)
BFS Search: Use breadth-first search to explore all possible states
State Representation: Each state is (bucketOne, bucketTwo, moves)
Generate Next States: For each state, generate all possible next states:
- Fill bucket one (if not full)
- Fill bucket two (if not full)
- Empty bucket one (if not empty)
- Empty bucket two (if not empty)
- Pour from bucket one to bucket two
- Pour from bucket two to bucket one
Filter States: Remove forbidden states (starting bucket empty and other full)
Track Visited: Use a set to avoid revisiting states
Check Goal: If either bucket reaches the goal, return the result
Return Result: Return moves count, goal bucket, and other bucket amount

The BFS algorithm guarantees we find the shortest path (minimum moves) to the goal state.

Solution

typedef Result = ({int moves, String goalBucket, int otherBucket});

class TwoBucket {
  final int bucketOne;
  final int bucketTwo;
  final int goal;
  final String startBucket;

  TwoBucket({
    required this.bucketOne,
    required this.bucketTwo,
    required this.goal,
    required this.startBucket,
  });

  Result measure() {
    // Check if goal is possible
    if (goal > bucketOne && goal > bucketTwo) {
      throw ArgumentError('Goal is impossible to reach');
    }

    // Use BFS to find the shortest path
    final queue = <_State>[];
    final visited = <String>{};

    // Start by filling the starting bucket
    if (startBucket == "one") {
      queue.add(_State(bucketOne, 0, 1));
    } else {
      queue.add(_State(0, bucketTwo, 1));
    }

    while (queue.isNotEmpty) {
      final state = queue.removeAt(0);
      final key = '${state.b1},${state.b2}';

      // Skip if already visited
      if (visited.contains(key)) continue;
      visited.add(key);

      // Check if we reached the goal
      if (state.b1 == goal) {
        return (moves: state.moves, goalBucket: "one", otherBucket: state.b2);
      }
      if (state.b2 == goal) {
        return (moves: state.moves, goalBucket: "two", otherBucket: state.b1);
      }

      // Generate all possible next states
      final nextStates = _getNextStates(state);
      queue.addAll(nextStates);
    }

    throw ArgumentError('Goal is impossible to reach');
  }

  List<_State> _getNextStates(_State state) {
    final states = <_State>[];
    final moves = state.moves + 1;

    // Action 1: Fill bucket one
    if (state.b1 < bucketOne) {
      states.add(_State(bucketOne, state.b2, moves));
    }

    // Action 2: Fill bucket two
    if (state.b2 < bucketTwo) {
      states.add(_State(state.b1, bucketTwo, moves));
    }

    // Action 3: Empty bucket one
    if (state.b1 > 0) {
      states.add(_State(0, state.b2, moves));
    }

    // Action 4: Empty bucket two
    if (state.b2 > 0) {
      states.add(_State(state.b1, 0, moves));
    }

    // Action 5: Pour from bucket one to bucket two
    if (state.b1 > 0 && state.b2 < bucketTwo) {
      final amount = (state.b1 + state.b2 > bucketTwo) 
          ? bucketTwo - state.b2 
          : state.b1;
      states.add(_State(state.b1 - amount, state.b2 + amount, moves));
    }

    // Action 6: Pour from bucket two to bucket one
    if (state.b2 > 0 && state.b1 < bucketOne) {
      final amount = (state.b1 + state.b2 > bucketOne) 
          ? bucketOne - state.b1 
          : state.b2;
      states.add(_State(state.b1 + amount, state.b2 - amount, moves));
    }

    // Filter out the forbidden state: starting bucket empty and other full
    return states.where((s) {
      if (startBucket == "one") {
        return !(s.b1 == 0 && s.b2 == bucketTwo);
      } else {
        return !(s.b2 == 0 && s.b1 == bucketOne);
      }
    }).toList();
  }
}

class _State {
  final int b1; // bucket one amount
  final int b2; // bucket two amount
  final int moves;

  _State(this.b1, this.b2, this.moves);
}

Let’s break down the solution:

typedef Result = ({int moves, String goalBucket, int otherBucket}) - Type alias:
- Creates a type alias for the result record
- Makes the return type more readable
- Represents the solution: moves count, goal bucket, and other bucket amount
class TwoBucket - Main class:
- Encapsulates the two bucket problem solver
- Stores bucket capacities, goal, and starting bucket
final int bucketOne, bucketTwo, goal, startBucket - Problem parameters:
- bucketOne, bucketTwo: Maximum capacities of each bucket
- goal: Target amount to measure
- startBucket: Which bucket to fill first (“one” or “two”)
TwoBucket({required ...}) - Constructor:
- Takes all parameters as required named parameters
- Initializes the problem configuration
Result measure() - Main method:
- Solves the two bucket problem using BFS
- Returns the result with moves, goal bucket, and other bucket amount
if (goal > bucketOne && goal > bucketTwo) throw ArgumentError(...) - Validation:
- Checks if goal is impossible (larger than both buckets)
- Throws error if goal cannot be reached
final queue = <_State>[] and final visited = <String>{} - BFS data structures:
- queue: List used as FIFO queue for BFS
- visited: Set to track visited states (using string keys)
if (startBucket == "one") queue.add(_State(bucketOne, 0, 1)) - Initial state:
- Starts by filling the starting bucket (first action = 1 move)
- If starting with bucket one: (bucketOne, 0, 1)
- If starting with bucket two: (0, bucketTwo, 1)
while (queue.isNotEmpty) - BFS loop:
- Continues until queue is empty (no solution) or goal is found
- Processes states in breadth-first order (shortest path first)
final state = queue.removeAt(0) - Dequeue:
- Removes first element from queue (FIFO)
- Gets the next state to process
final key = '${state.b1},${state.b2}' - State key:
- Creates string representation of state for visited tracking
- Example: “3,5” for bucket one=3, bucket two=5
if (visited.contains(key)) continue - Skip visited:
- Avoids processing the same state twice
- Prevents infinite loops and redundant work
visited.add(key) - Mark visited:
- Adds current state to visited set
- Ensures we don’t revisit this state
if (state.b1 == goal) return (moves: ..., goalBucket: "one", ...) - Goal check:
- Checks if bucket one reached the goal
- Returns result immediately (shortest path found)
if (state.b2 == goal) return (moves: ..., goalBucket: "two", ...) - Goal check:
- Checks if bucket two reached the goal
- Returns result with appropriate goal bucket
final nextStates = _getNextStates(state) - Generate next states:
- Gets all possible next states from current state
- Applies all 6 possible actions
queue.addAll(nextStates) - Enqueue next states:
- Adds all valid next states to queue
- They will be processed in breadth-first order
throw ArgumentError('Goal is impossible to reach') - No solution:
- Thrown if BFS completes without finding goal
- Means goal is unreachable from initial state
List<_State> _getNextStates(_State state) - State generator:
- Generates all possible next states from current state
- Applies all 6 actions: fill one, fill two, empty one, empty two, pour 1→2, pour 2→1
final moves = state.moves + 1 - Increment moves:
- Each action increments move count
- Tracks total actions taken
if (state.b1 < bucketOne) states.add(_State(bucketOne, state.b2, moves)) - Fill bucket one:
- Action: Fill bucket one to capacity
- Only if bucket one is not already full
if (state.b2 < bucketTwo) states.add(_State(state.b1, bucketTwo, moves)) - Fill bucket two:
- Action: Fill bucket two to capacity
- Only if bucket two is not already full
if (state.b1 > 0) states.add(_State(0, state.b2, moves)) - Empty bucket one:
- Action: Empty bucket one completely
- Only if bucket one is not already empty
if (state.b2 > 0) states.add(_State(state.b1, 0, moves)) - Empty bucket two:
- Action: Empty bucket two completely
- Only if bucket two is not already empty
if (state.b1 > 0 && state.b2 < bucketTwo) - Pour 1→2 condition:
- Can pour from bucket one to bucket two
- Requires bucket one not empty and bucket two not full
final amount = (state.b1 + state.b2 > bucketTwo) ? bucketTwo - state.b2 : state.b1 - Calculate pour amount:
- If total would overflow: pour only what fits (bucketTwo - state.b2)
- Otherwise: pour all from bucket one (state.b1)
states.add(_State(state.b1 - amount, state.b2 + amount, moves)) - Pour 1→2:
- Updates buckets after pouring
- Subtracts from bucket one, adds to bucket two
if (state.b2 > 0 && state.b1 < bucketOne) - Pour 2→1 condition:
- Can pour from bucket two to bucket one
- Requires bucket two not empty and bucket one not full
final amount = (state.b1 + state.b2 > bucketOne) ? bucketOne - state.b1 : state.b2 - Calculate pour amount:
- If total would overflow: pour only what fits (bucketOne - state.b1)
- Otherwise: pour all from bucket two (state.b2)
states.add(_State(state.b1 + amount, state.b2 - amount, moves)) - Pour 2→1:
- Updates buckets after pouring
- Adds to bucket one, subtracts from bucket two
return states.where((s) { ... }).toList() - Filter forbidden states:
- Removes states where starting bucket is empty and other is full
- This violates rule 3
if (startBucket == "one") return !(s.b1 == 0 && s.b2 == bucketTwo) - Filter for start=“one”:
- Forbids state (0, bucketTwo) when starting with bucket one
- Allows all other states
else return !(s.b2 == 0 && s.b1 == bucketOne) - Filter for start=“two”:
- Forbids state (bucketOne, 0) when starting with bucket two
- Allows all other states
class _State - Private state class:
- Represents a state: (bucket one amount, bucket two amount, moves)
- Private (prefixed with _) - only accessible in same file
final int b1, b2, moves - State fields:
- b1: Current amount in bucket one
- b2: Current amount in bucket two
- moves: Number of actions taken to reach this state
_State(this.b1, this.b2, this.moves) - State constructor:
- Initializes state with bucket amounts and move count
- Used to create new states

The solution efficiently finds the shortest path to the goal using BFS. The algorithm explores all possible states level by level, ensuring the first solution found uses the minimum number of moves. The visited set prevents revisiting states, and the forbidden state filter ensures rule 3 is always satisfied.

A video tutorial for this exercise is coming soon! In the meantime, check out my YouTube channel for more Dart and Flutter tutorials. 😉

Visit My YouTube Channel