| 1 | 1 | def solve(puzzle: str) -> dict[str, int] | None: |
| 2 | | pass |
| 2 | """ |
| 3 | Solve an alphametics puzzle. |
| 4 | |
| 5 | Args: |
| 6 | puzzle: A string representing the alphametics puzzle (e.g., "SEND + MORE == MONEY") |
| 7 | |
| 8 | Returns: |
| 9 | A dictionary mapping letters to digits that solves the puzzle, or None if no solution exists. |
| 10 | |
| 11 | Example: |
| 12 | >>> solve("SEND + MORE == MONEY") |
| 13 | {'S': 9, 'E': 5, 'N': 6, 'D': 7, 'M': 1, 'O': 0, 'R': 8, 'Y': 2} |
| 14 | """ |
| 15 | # Edge Case: Empty or None puzzle |
| 16 | if not puzzle: |
| 17 | return None |
| 18 | |
| 19 | # Parse the puzzle |
| 20 | parts = puzzle.replace("==", "=").replace(" ", "").split("=") |
| 21 | |
| 22 | # Edge Case: Invalid puzzle format (no equals sign or too many parts) |
| 23 | if len(parts) != 2: |
| 24 | return None |
| 25 | |
| 26 | right_side = parts[1] |
| 27 | left_expression = parts[0] |
| 28 | |
| 29 | # Determine the operator |
| 30 | operator = "+" # default to addition |
| 31 | if "-" in left_expression: |
| 32 | operator = "-" |
| 33 | elif "*" in left_expression: |
| 34 | operator = "*" |
| 35 | |
| 36 | # Split left side by the operator |
| 37 | if operator == "+": |
| 38 | left_parts = left_expression.replace("+", " ").split() |
| 39 | elif operator == "-": |
| 40 | left_parts = left_expression.replace("-", " ").split() |
| 41 | elif operator == "*": |
| 42 | left_parts = left_expression.replace("*", " ").split() |
| 43 | else: |
| 44 | left_parts = [left_expression] # fallback |
| 45 | |
| 46 | # Edge Case: No terms on the left side |
| 47 | if not left_parts: |
| 48 | return None |
| 49 | |
| 50 | # Extract all unique letters |
| 51 | letters = set() |
| 52 | for part in left_parts + [right_side]: |
| 53 | letters.update(part) |
| 54 | |
| 55 | # Edge Case: No letters in puzzle |
| 56 | if not letters: |
| 57 | return None |
| 58 | |
| 59 | # Extract first letters (can't be zero) |
| 60 | first_letters = {word[0] for word in left_parts + [right_side]} |
| 61 | |
| 62 | letters = list(letters) |
| 63 | |
| 64 | # Edge Case: More than 10 unique letters (impossible to assign unique digits) |
| 65 | if len(letters) > 10: |
| 66 | return None |
| 67 | |
| 68 | # Try all possible digit assignments |
| 69 | from itertools import permutations |
| 70 | |
| 71 | # Edge Case: Handle permutation generation for digit assignment |
| 72 | for perm in permutations(range(10), len(letters)): |
| 73 | mapping = dict(zip(letters, perm)) |
| 74 | |
| 75 | # Check if any first letter is assigned zero |
| 76 | # Edge Case: Leading digit cannot be zero |
| 77 | if any(mapping[letter] == 0 for letter in first_letters): |
| 78 | continue |
| 79 | |
| 80 | # Calculate left side value based on operator |
| 81 | if operator == "+": |
| 82 | left_value = 0 |
| 83 | for word in left_parts: |
| 84 | num = 0 |
| 85 | for letter in word: |
| 86 | num = num * 10 + mapping[letter] |
| 87 | left_value += num |
| 88 | elif operator == "-": |
| 89 | # For subtraction, we assume the format is "A - B == C" |
| 90 | # So we take the first term and subtract the rest |
| 91 | left_value = 0 |
| 92 | for i, word in enumerate(left_parts): |
| 93 | num = 0 |
| 94 | for letter in word: |
| 95 | num = num * 10 + mapping[letter] |
| 96 | if i == 0: |
| 97 | left_value = num |
| 98 | else: |
| 99 | left_value -= num |
| 100 | elif operator == "*": |
| 101 | left_value = 1 |
| 102 | for word in left_parts: |
| 103 | num = 0 |
| 104 | for letter in word: |
| 105 | num = num * 10 + mapping[letter] |
| 106 | left_value *= num |
| 107 | |
| 108 | # Calculate right side value |
| 109 | right_num = 0 |
| 110 | for letter in right_side: |
| 111 | right_num = right_num * 10 + mapping[letter] |
| 112 | |
| 113 | # Check if equation is satisfied |
| 114 | # Edge Case: Verify the mathematical correctness of the solution |
| 115 | if left_value == right_num: |
| 116 | return mapping |
| 117 | |
| 118 | # Edge Case: No valid solution found |
| 119 | return None |
| 120 | # Handled Edge Cases: Empty or None puzzle, Invalid puzzle format, No terms on left side, No letters in puzzle, More than 10 unique letters, Leading digit cannot be zero, Verify mathematical correctness, No valid solution found |