| 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 puzzle (e.g., "SEND + MORE == MONEY") |
| 7 | |
| 8 | Returns: |
| 9 | A dictionary mapping letters to digits, or None if no solution exists |
| 10 | """ |
| 11 | # Edge Case: Empty or None puzzle |
| 12 | if not puzzle: |
| 13 | return None |
| 14 | |
| 15 | # Parse the puzzle |
| 16 | parts = puzzle.replace("==", "=").replace(" ", "").split("=") |
| 17 | |
| 18 | # Edge Case: Invalid puzzle format (no equals sign or too many parts) |
| 19 | if len(parts) != 2: |
| 20 | return None |
| 21 | |
| 22 | left_side, right_side = parts[0], parts[1] |
| 23 | |
| 24 | # Split the left side by '+' to get addends |
| 25 | addends = left_side.split("+") |
| 26 | |
| 27 | # Edge Case: No addends on the left side |
| 28 | if not addends or not all(addends): |
| 29 | return None |
| 30 | |
| 31 | # Edge Case: Empty right side |
| 32 | if not right_side: |
| 33 | return None |
| 34 | |
| 35 | # Extract all unique letters |
| 36 | letters = set() |
| 37 | for part in addends + [right_side]: |
| 38 | letters.update(part) |
| 39 | |
| 40 | # Edge Case: More than 10 unique letters (impossible to assign unique digits) |
| 41 | if len(letters) > 10: |
| 42 | return None |
| 43 | |
| 44 | # Identify first letters (can't be zero) |
| 45 | first_letters = {word[0] for word in addends + [right_side]} |
| 46 | |
| 47 | # Convert to list for consistent ordering |
| 48 | letters = list(letters) |
| 49 | |
| 50 | # Try all possible digit assignments using backtracking |
| 51 | def backtrack(index, used_digits, assignment): |
| 52 | # Base case: all letters assigned |
| 53 | if index == len(letters): |
| 54 | # Check if the equation is satisfied |
| 55 | left_value = 0 |
| 56 | for addend in addends: |
| 57 | num = 0 |
| 58 | for char in addend: |
| 59 | num = num * 10 + assignment[char] |
| 60 | left_value += num |
| 61 | |
| 62 | right_value = 0 |
| 63 | for char in right_side: |
| 64 | right_value = right_value * 10 + assignment[char] |
| 65 | |
| 66 | if left_value == right_value: |
| 67 | return assignment.copy() |
| 68 | return None |
| 69 | |
| 70 | # Try assigning each unused digit to the current letter |
| 71 | letter = letters[index] |
| 72 | for digit in range(10): |
| 73 | # Skip if digit already used |
| 74 | if digit in used_digits: |
| 75 | continue |
| 76 | |
| 77 | # Skip if this is a first letter and digit is 0 |
| 78 | if letter in first_letters and digit == 0: |
| 79 | continue |
| 80 | |
| 81 | # Make assignment |
| 82 | assignment[letter] = digit |
| 83 | used_digits.add(digit) |
| 84 | |
| 85 | # Recurse |
| 86 | result = backtrack(index + 1, used_digits, assignment) |
| 87 | if result is not None: |
| 88 | return result |
| 89 | |
| 90 | # Backtrack |
| 91 | used_digits.remove(digit) |
| 92 | del assignment[letter] |
| 93 | |
| 94 | return None |
| 95 | |
| 96 | # Start backtracking |
| 97 | result = backtrack(0, set(), {}) |
| 98 | return result |
| 99 | |
| 100 | # Handled Edge Cases: Empty or None puzzle, Invalid puzzle format (no equals sign or too many parts), No addends on the left side, Empty right side, More than 10 unique letters (impossible to assign unique digits) |