diff --git a/main.py b/main.py index 9d19282..8b59bdf 100644 --- a/main.py +++ b/main.py @@ -1,3 +1,209 @@ +from collections import deque + +from collections import deque + def measure(bucket_one: int, bucket_two: int, goal: int, start_bucket: str) -> tuple[int, str, int]: - # Returns (total_moves, goal_bucket, other_bucket_liters) where goal_bucket is "one" or "two" - pass + """ + Determine the minimum number of actions to measure an exact number of liters using two buckets. + + Args: + bucket_one: Size of the first bucket + bucket_two: Size of the second bucket + goal: Desired number of liters + start_bucket: Which bucket to fill first ("one" or "two") + + Returns: + Tuple of (total_moves, goal_bucket, other_bucket_liters) + + Raises: + ValueError: If the goal cannot be reached or inputs are invalid + """ + # Validate inputs + if bucket_one <= 0 or bucket_two <= 0: + raise ValueError("Bucket sizes must be positive integers") + + if goal < 0: + raise ValueError("Goal must be non-negative") + + if goal > max(bucket_one, bucket_two): + raise ValueError("Goal cannot exceed the capacity of the larger bucket") + + if start_bucket not in ("one", "two"): + raise ValueError("Start bucket must be 'one' or 'two'") + + # Determine forbidden state based on starting bucket + if start_bucket == "one": + forbidden_state = (0, bucket_two) + else: # start_bucket == "two" + forbidden_state = (bucket_one, 0) + + # Initialize BFS + queue = deque() + visited = set() + + # Initial state: (bucket_one_content, bucket_two_content, moves) + if start_bucket == "one": + initial_state = (bucket_one, 0, 1) + else: # start_bucket == "two" + initial_state = (0, bucket_two, 1) + + queue.append(initial_state) + visited.add((initial_state[0], initial_state[1])) + + # BFS to find minimum moves + while queue: + b1, b2, moves = queue.popleft() + + # Check if we've reached the goal + if b1 == goal: + return (moves, "one", b2) + if b2 == goal: + return (moves, "two", b1) + + # Generate all possible next states + next_states = [] + + # Fill bucket one + if b1 < bucket_one: + next_states.append((bucket_one, b2)) + + # Fill bucket two + if b2 < bucket_two: + next_states.append((b1, bucket_two)) + + # Empty bucket one + if b1 > 0: + next_states.append((0, b2)) + + # Empty bucket two + if b2 > 0: + next_states.append((b1, 0)) + + # Pour from bucket one to bucket two + if b1 > 0 and b2 < bucket_two: + pour_amount = min(b1, bucket_two - b2) + next_states.append((b1 - pour_amount, b2 + pour_amount)) + + # Pour from bucket two to bucket one + if b2 > 0 and b1 < bucket_one: + pour_amount = min(b2, bucket_one - b1) + next_states.append((b1 + pour_amount, b2 - pour_amount)) + + # Process next states + for next_b1, next_b2 in next_states: + # Skip forbidden state + if (next_b1, next_b2) == forbidden_state: + continue + + # Skip already visited states + if (next_b1, next_b2) in visited: + continue + + # Add to queue for further exploration + visited.add((next_b1, next_b2)) + queue.append((next_b1, next_b2, moves + 1)) + + # If we get here, the goal is impossible to reach + raise ValueError("Goal amount cannot be reached with given bucket sizes") + """ + Determine the minimum number of actions to measure an exact number of liters using two buckets. + + Args: + bucket_one: Size of the first bucket + bucket_two: Size of the second bucket + goal: Desired number of liters + start_bucket: Which bucket to fill first ("one" or "two") + + Returns: + Tuple of (total_moves, goal_bucket, other_bucket_liters) + + Raises: + ValueError: If the goal cannot be reached or inputs are invalid + """ + # Validate inputs + if bucket_one <= 0 or bucket_two <= 0: + raise ValueError("Bucket sizes must be positive integers") + + if goal < 0: + raise ValueError("Goal must be non-negative") + + if goal > max(bucket_one, bucket_two): + raise ValueError("Goal cannot exceed the capacity of the larger bucket") + + if start_bucket not in ("one", "two"): + raise ValueError("Start bucket must be 'one' or 'two'") + + # Determine forbidden state based on starting bucket + if start_bucket == "one": + forbidden_state = (0, bucket_two) + else: # start_bucket == "two" + forbidden_state = (bucket_one, 0) + + # Initialize BFS + queue = deque() + visited = set() + + # Initial state: (bucket_one_content, bucket_two_content, moves) + if start_bucket == "one": + initial_state = (bucket_one, 0, 1) + else: # start_bucket == "two" + initial_state = (0, bucket_two, 1) + + queue.append(initial_state) + visited.add((initial_state[0], initial_state[1])) + + # BFS to find minimum moves + while queue: + b1, b2, moves = queue.popleft() + + # Check if we've reached the goal + if b1 == goal: + return (moves, "one", b2) + if b2 == goal: + return (moves, "two", b1) + + # Generate all possible next states + next_states = [] + + # Fill bucket one + if b1 < bucket_one: + next_states.append((bucket_one, b2)) + + # Fill bucket two + if b2 < bucket_two: + next_states.append((b1, bucket_two)) + + # Empty bucket one + if b1 > 0: + next_states.append((0, b2)) + + # Empty bucket two + if b2 > 0: + next_states.append((b1, 0)) + + # Pour from bucket one to bucket two + if b1 > 0 and b2 < bucket_two: + pour_amount = min(b1, bucket_two - b2) + next_states.append((b1 - pour_amount, b2 + pour_amount)) + + # Pour from bucket two to bucket one + if b2 > 0 and b1 < bucket_one: + pour_amount = min(b2, bucket_one - b1) + next_states.append((b1 + pour_amount, b2 - pour_amount)) + + # Process next states + for next_b1, next_b2 in next_states: + # Skip forbidden state + if (next_b1, next_b2) == forbidden_state: + continue + + # Skip already visited states + if (next_b1, next_b2) in visited: + continue + + # Add to queue for further exploration + visited.add((next_b1, next_b2)) + queue.append((next_b1, next_b2, moves + 1)) + + # If we get here, the goal is impossible to reach + raise ValueError("Goal amount cannot be reached with given bucket sizes")

Problem Name -	Status	Runtime -
django__django-13344	Failed	21m 04s
django__django-15629	Failed	18m 34s
simple-linked-list-js	Failed	04m 27s
simple-linked-list-py	Failed	03m 55s
twelve-days-js	Failed	07m 08s
nucleotide-count-js	Failed	10m 22s
pytest-dev__pytest-10356	Failed	12m 03s
astropy__astropy-13398

Opentensor