| 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 | right_side = parts[1] |
| 23 | left_sides = parts[0].split("+") |
| 24 | |
| 25 | # Edge Case: No terms on the left side |
| 26 | if not left_sides or not all(left_sides): |
| 27 | return None |
| 28 | |
| 29 | # Edge Case: Empty right side |
| 30 | if not right_side: |
| 31 | return None |
| 32 | |
| 33 | # Extract all unique letters |
| 34 | letters = set() |
| 35 | for part in left_sides + [right_side]: |
| 36 | letters.update(part) |
| 37 | |
| 38 | # Edge Case: No letters in puzzle |
| 39 | if not letters: |
| 40 | return None |
| 41 | |
| 42 | # Extract first letters (can't be zero) |
| 43 | first_letters = {word[0] for word in left_sides + [right_side]} |
| 44 | |
| 45 | # Edge Case: More than 10 unique letters (impossible to solve) |
| 46 | if len(letters) > 10: |
| 47 | return None |
| 48 | |
| 49 | # Convert to lists for indexing |
| 50 | letters = list(letters) |
| 51 | |
| 52 | def evaluate(assignment): |
| 53 | """Evaluate if the current assignment satisfies the puzzle""" |
| 54 | # Convert words to numbers |
| 55 | left_values = [] |
| 56 | for word in left_sides: |
| 57 | num = 0 |
| 58 | for char in word: |
| 59 | num = num * 10 + assignment[char] |
| 60 | left_values.append(num) |
| 61 | |
| 62 | right_value = 0 |
| 63 | for char in right_side: |
| 64 | right_value = right_value * 10 + assignment[char] |
| 65 | |
| 66 | return sum(left_values) == right_value |
| 67 | |
| 68 | def is_valid(assignment, letter, digit): |
| 69 | """Check if assigning digit to letter is valid""" |
| 70 | # Edge Case: Leading zero |
| 71 | if letter in first_letters and digit == 0: |
| 72 | return False |
| 73 | |
| 74 | # Edge Case: Digit already assigned to another letter |
| 75 | if digit in assignment.values(): |
| 76 | return False |
| 77 | |
| 78 | return True |
| 79 | |
| 80 | def backtrack(index, assignment): |
| 81 | """Backtracking search for a valid assignment""" |
| 82 | # Base case: all letters assigned |
| 83 | if index == len(letters): |
| 84 | if evaluate(assignment): |
| 85 | return assignment.copy() |
| 86 | return None |
| 87 | |
| 88 | letter = letters[index] |
| 89 | |
| 90 | # Try each digit |
| 91 | for digit in range(10): |
| 92 | if is_valid(assignment, letter, digit): |
| 93 | assignment[letter] = digit |
| 94 | result = backtrack(index + 1, assignment) |
| 95 | if result is not None: |
| 96 | return result |
| 97 | del assignment[letter] |
| 98 | |
| 99 | return None |
| 100 | |
| 101 | # Start backtracking |
| 102 | result = backtrack(0, {}) |
| 103 | return result |
| 104 | |
| 105 | # Handled Edge Cases: Empty or None puzzle, Invalid puzzle format, No terms on left side, Empty right side, No letters in puzzle, More than 10 unique letters, Leading zero, Digit already assigned to another letter |