| 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 | left_side, right_side = parts[0], parts[1] |
| 27 | |
| 28 | # Split the left side by '+' to get addends |
| 29 | addends = left_side.split("+") |
| 30 | |
| 31 | # Edge Case: No addends on the left side |
| 32 | if not addends or not all(addends): |
| 33 | return None |
| 34 | |
| 35 | # Edge Case: Empty right side |
| 36 | if not right_side: |
| 37 | return None |
| 38 | |
| 39 | # Extract all unique letters |
| 40 | letters = set() |
| 41 | for part in addends + [right_side]: |
| 42 | letters.update(part) |
| 43 | |
| 44 | # Edge Case: No letters in puzzle |
| 45 | if not letters: |
| 46 | return None |
| 47 | |
| 48 | # Extract first letters (can't be zero) |
| 49 | first_letters = {word[0] for word in addends + [right_side]} |
| 50 | |
| 51 | # Edge Case: More than 10 unique letters (impossible to assign unique digits) |
| 52 | if len(letters) > 10: |
| 53 | return None |
| 54 | |
| 55 | # Convert to lists for indexing |
| 56 | letters_list = list(letters) |
| 57 | |
| 58 | def is_valid_solution(mapping): |
| 59 | """Check if the current mapping is a valid solution.""" |
| 60 | # Check if any first letter is mapped to 0 |
| 61 | # Edge Case: Leading zero in any word |
| 62 | for letter in first_letters: |
| 63 | if mapping[letter] == 0: |
| 64 | return False |
| 65 | |
| 66 | # Convert words to numbers |
| 67 | try: |
| 68 | addend_values = [] |
| 69 | for word in addends: |
| 70 | value = 0 |
| 71 | for letter in word: |
| 72 | value = value * 10 + mapping[letter] |
| 73 | addend_values.append(value) |
| 74 | |
| 75 | right_value = 0 |
| 76 | for letter in right_side: |
| 77 | right_value = right_value * 10 + mapping[letter] |
| 78 | |
| 79 | # Check if the sum is correct |
| 80 | return sum(addend_values) == right_value |
| 81 | except KeyError: |
| 82 | # Edge Case: Not all letters have been assigned yet |
| 83 | return False |
| 84 | |
| 85 | def backtrack(index, mapping, used_digits): |
| 86 | """Backtracking function to find a valid digit assignment.""" |
| 87 | # Base case: all letters have been assigned |
| 88 | if index == len(letters_list): |
| 89 | if is_valid_solution(mapping): |
| 90 | return mapping.copy() |
| 91 | return None |
| 92 | |
| 93 | letter = letters_list[index] |
| 94 | |
| 95 | # Try each available digit |
| 96 | for digit in range(10): |
| 97 | # Edge Case: Digit already used |
| 98 | if digit in used_digits: |
| 99 | continue |
| 100 | |
| 101 | # Edge Case: Assigning 0 to a first letter |
| 102 | if digit == 0 and letter in first_letters: |
| 103 | continue |
| 104 | |
| 105 | # Make assignment |
| 106 | mapping[letter] = digit |
| 107 | used_digits.add(digit) |
| 108 | |
| 109 | # Recurse |
| 110 | result = backtrack(index + 1, mapping, used_digits) |
| 111 | if result is not None: |
| 112 | return result |
| 113 | |
| 114 | # Backtrack |
| 115 | del mapping[letter] |
| 116 | used_digits.remove(digit) |
| 117 | |
| 118 | return None |
| 119 | |
| 120 | # Start backtracking |
| 121 | solution = backtrack(0, {}, set()) |
| 122 | return solution |
| 123 | |
| 124 | # Handled Edge Cases: Empty or None puzzle, Invalid puzzle format, No addends, Empty right side, No letters, More than 10 unique letters, Leading zero in any word, Not all letters assigned, Digit already used, Assigning 0 to first letter |