| 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 |
| 23 | if len(parts) != 2: |
| 24 | return None |
| 25 | |
| 26 | right_side = parts[1] |
| 27 | left_parts = parts[0].replace("+", " ").split() |
| 28 | |
| 29 | # Edge Case: No terms on the left side |
| 30 | if not left_parts: |
| 31 | return None |
| 32 | |
| 33 | # Extract all unique letters |
| 34 | letters = set() |
| 35 | for part in left_parts + [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_parts + [right_side]} |
| 44 | |
| 45 | # Convert to sorted list for consistent ordering |
| 46 | letters = list(letters) |
| 47 | |
| 48 | # Edge Case: More than 10 unique letters (impossible to solve) |
| 49 | if len(letters) > 10: |
| 50 | return None |
| 51 | |
| 52 | def evaluate(assignment): |
| 53 | """Evaluate if the current assignment satisfies the puzzle.""" |
| 54 | # Convert words to numbers using the assignment |
| 55 | left_values = [] |
| 56 | for word in left_parts: |
| 57 | num = 0 |
| 58 | for char in word: |
| 59 | # Edge Case: Letter not in assignment |
| 60 | if char not in assignment: |
| 61 | return False |
| 62 | num = num * 10 + assignment[char] |
| 63 | left_values.append(num) |
| 64 | |
| 65 | right_value = 0 |
| 66 | for char in right_side: |
| 67 | # Edge Case: Letter not in assignment |
| 68 | if char not in assignment: |
| 69 | return False |
| 70 | right_value = right_value * 10 + assignment[char] |
| 71 | |
| 72 | return sum(left_values) == right_value |
| 73 | |
| 74 | def is_valid(assignment): |
| 75 | """Check if assignment is valid (no leading zeros).""" |
| 76 | for letter in first_letters: |
| 77 | # Edge Case: First letter assigned zero |
| 78 | if assignment.get(letter) == 0: |
| 79 | return False |
| 80 | return True |
| 81 | |
| 82 | def backtrack(index, assignment, used_digits): |
| 83 | """Backtracking search for a solution.""" |
| 84 | # Base case: all letters assigned |
| 85 | if index == len(letters): |
| 86 | if is_valid(assignment) and evaluate(assignment): |
| 87 | return assignment.copy() |
| 88 | return None |
| 89 | |
| 90 | letter = letters[index] |
| 91 | |
| 92 | # Try each digit for this letter |
| 93 | for digit in range(10): |
| 94 | # Edge Case: Digit already used |
| 95 | if digit in used_digits: |
| 96 | continue |
| 97 | |
| 98 | assignment[letter] = digit |
| 99 | used_digits.add(digit) |
| 100 | |
| 101 | # Optimization: Check partial constraints |
| 102 | if is_valid(assignment): |
| 103 | result = backtrack(index + 1, assignment, used_digits) |
| 104 | if result is not None: |
| 105 | return result |
| 106 | |
| 107 | # Backtrack |
| 108 | used_digits.remove(digit) |
| 109 | del assignment[letter] |
| 110 | |
| 111 | return None |
| 112 | |
| 113 | # Start backtracking |
| 114 | result = backtrack(0, {}, set()) |
| 115 | return result |
| 116 | |
| 117 | # Handled Edge Cases: Empty or None puzzle, Invalid puzzle format, No terms on the left side, No letters in puzzle, More than 10 unique letters, Letter not in assignment, First letter assigned zero, Digit already used |