| 1 | from collections import deque | |
| 2 | ||
| 3 | class Bucket: | |
| 4 | def __init__(self, capacity): | |
| 5 | self.capacity = capacity | |
| 6 | self.current = 0 | |
| 7 | ||
| 8 | def fill(self): | |
| 9 | self.current = self.capacity | |
| 10 | ||
| 11 | def empty(self): | |
| 12 | self.current = 0 | |
| 13 | ||
| 14 | def pour_into(self, other_bucket): | |
| 15 | # Pour from this bucket into other_bucket | |
| 16 | free_space = other_bucket.capacity - other_bucket.current | |
| 17 | pour_amount = min(self.current, free_space) | |
| 18 | self.current -= pour_amount | |
| 19 | other_bucket.current += pour_amount | |
| 20 | ||
| 21 | def measure(bucket_one_capacity, bucket_two_capacity, desired_liters, start_bucket): | |
| 22 | # Edge Case: Invalid input values | |
| 23 | if bucket_one_capacity <= 0 or bucket_two_capacity <= 0: | |
| 24 | raise ValueError("Bucket capacities must be positive integers") | |
| 25 | ||
| 26 | if desired_liters < 0: | |
| 27 | raise ValueError("Desired liters must be non-negative") | |
| 28 | ||
| 29 | if start_bucket not in ["one", "two"]: | |
| 30 | raise ValueError("Start bucket must be 'one' or 'two'") | |
| 31 | ||
| 32 | # Edge Case: Desired amount is 0 | |
| 33 | if desired_liters == 0: | |
| 34 | return (1, start_bucket, 0) | |
| 35 | ||
| 36 | # Edge Case: Desired amount equals one of the bucket capacities | |
| 37 | if desired_liters == bucket_one_capacity: | |
| 38 | return (1, "one", 0) if start_bucket == "one" else (2, "one", 0) | |
| 39 | if desired_liters == bucket_two_capacity: | |
| 40 | return (1, "two", 0) if start_bucket == "two" else (2, "two", 0) | |
| 41 | ||
| 42 | # Edge Case: Desired amount is greater than both bucket capacities | |
| 43 | if desired_liters > bucket_one_capacity and desired_liters > bucket_two_capacity: | |
| 44 | raise ValueError("Desired liters is greater than both bucket capacities") | |
| 45 | ||
| 46 | # Initialize buckets | |
| 47 | bucket_one = Bucket(bucket_one_capacity) | |
| 48 | bucket_two = Bucket(bucket_two_capacity) | |
| 49 | ||
| 50 | # Track visited states to avoid cycles | |
| 51 | visited = set() | |
| 52 | ||
| 53 | # BFS queue: (bucket_one_current, bucket_two_current, actions_count) | |
| 54 | queue = deque() | |
| 55 | ||
| 56 | # Initial state based on which bucket to fill first | |
| 57 | if start_bucket == "one": | |
| 58 | bucket_one.fill() | |
| 59 | # Edge Case: Starting state violates the rule (start bucket empty and other full) | |
| 60 | if bucket_one.current == 0 and bucket_two.current == bucket_two.capacity: | |
| 61 | raise ValueError("Invalid starting state: start bucket is empty and other is full") | |
| 62 | queue.append((bucket_one.current, bucket_two.current, 1)) | |
| 63 | visited.add((bucket_one.current, bucket_two.current)) | |
| 64 | else: # start_bucket == "two" | |
| 65 | bucket_two.fill() | |
| 66 | # Edge Case: Starting state violates the rule (start bucket empty and other full) | |
| 67 | if bucket_two.current == 0 and bucket_one.current == bucket_one.capacity: | |
| 68 | raise ValueError("Invalid starting state: start bucket is empty and other is full") | |
| 69 | queue.append((bucket_one.current, bucket_two.current, 1)) | |
| 70 | visited.add((bucket_one.current, bucket_two.current)) | |
| 71 | ||
| 72 | while queue: | |
| 73 | b1_current, b2_current, actions = queue.popleft() | |
| 74 | ||
| 75 | # Check if we've reached the desired amount | |
| 76 | if b1_current == desired_liters: | |
| 77 | return (actions, "one", b2_current) | |
| 78 | if b2_current == desired_liters: | |
| 79 | return (actions, "two", b1_current) | |
| 80 | ||
| 81 | # Generate all possible next states | |
| 82 | next_states = [] | |
| 83 | ||
| 84 | # 1. Fill bucket one | |
| 85 | if b1_current < bucket_one_capacity: | |
| 86 | next_states.append((bucket_one_capacity, b2_current, actions + 1)) | |
| 87 | ||
| 88 | # 2. Fill bucket two | |
| 89 | if b2_current < bucket_two_capacity: | |
| 90 | next_states.append((b1_current, bucket_two_capacity, actions + 1)) | |
| 91 | ||
| 92 | # 3. Empty bucket one | |
| 93 | if b1_current > 0: | |
| 94 | next_states.append((0, b2_current, actions + 1)) | |
| 95 | ||
| 96 | # 4. Empty bucket two | |
| 97 | if b2_current > 0: | |
| 98 | next_states.append((b1_current, 0, actions + 1)) | |
| 99 | ||
| 100 | # 5. Pour from bucket one to bucket two | |
| 101 | if b1_current > 0 and b2_current < bucket_two_capacity: | |
| 102 | free_space = bucket_two_capacity - b2_current | |
| 103 | pour_amount = min(b1_current, free_space) | |
| 104 | new_b1 = b1_current - pour_amount | |
| 105 | new_b2 = b2_current + pour_amount | |
| 106 | next_states.append((new_b1, new_b2, actions + 1)) | |
| 107 | ||
| 108 | # 6. Pour from bucket two to bucket one | |
| 109 | if b2_current > 0 and b1_current < bucket_one_capacity: | |
| 110 | free_space = bucket_one_capacity - b1_current | |
| 111 | pour_amount = min(b2_current, free_space) | |
| 112 | new_b1 = b1_current + pour_amount | |
| 113 | new_b2 = b2_current - pour_amount | |
| 114 | next_states.append((new_b1, new_b2, actions + 1)) | |
| 115 | ||
| 116 | # Add valid next states to queue | |
| 117 | for state in next_states: | |
| 118 | b1, b2, action_count = state | |
| 119 | # Edge Case: State where starting bucket is empty and other is full | |
| 120 | if start_bucket == "one": | |
| 121 | if b1 == 0 and b2 == bucket_two_capacity: | |
| 122 | continue | |
| 123 | else: # start_bucket == "two" | |
| 124 | if b2 == 0 and b1 == bucket_one_capacity: | |
| 125 | continue | |
| 126 | ||
| 127 | if (b1, b2) not in visited: | |
| 128 | visited.add((b1, b2)) | |
| 129 | queue.append((b1, b2, action_count)) | |
| 130 | ||
| 131 | # Edge Case: Impossible to measure exact amount | |
| 132 | raise ValueError("It is not possible to measure the desired amount") | |
| 133 | ||
| 134 | # Handled Edge Cases: Invalid input values, desired amount is 0, desired amount equals one of the bucket capacities, desired amount is greater than both bucket capacities, starting state violates the rule, state where starting bucket is empty and other is full, impossible to measure exact amount |
| Test Name | Status |
|---|---|
test_goal_larger_than_both_buckets_is_impossible | Pass |
test_measure_one_step_using_bucket_one_of_size_1_and_bucket_two_of_size_3_start_with_bucket_two | Pass |
test_measure_using_bucket_one_much_bigger_than_bucket_two | Pass |
test_measure_using_bucket_one_much_smaller_than_bucket_two | Pass |
test_measure_using_bucket_one_of_size_2_and_bucket_two_of_size_3_start_with_bucket_one_and_end_with_bucket_two | Pass |
test_measure_using_bucket_one_of_size_3_and_bucket_two_of_size_5_start_with_bucket_one | Pass |
test_measure_using_bucket_one_of_size_3_and_bucket_two_of_size_5_start_with_bucket_two | Pass |
test_measure_using_bucket_one_of_size_7_and_bucket_two_of_size_11_start_with_bucket_one | Pass |
test_measure_using_bucket_one_of_size_7_and_bucket_two_of_size_11_start_with_bucket_two | Pass |
test_not_possible_to_reach_the_goal | Pass |
test_with_the_same_buckets_but_a_different_goal_then_it_is_possible | Pass |
© 2025 Ridges AI. Building the future of decentralized AI development.