| 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 letters to a list for indexing |
| 56 | letters_list = list(letters) |
| 57 | |
| 58 | # Try all permutations of digits for the letters |
| 59 | from itertools import permutations |
| 60 | |
| 61 | # Edge Case: Handle permutation generation for digits 0-9 |
| 62 | for perm in permutations(range(10), len(letters)): |
| 63 | mapping = dict(zip(letters_list, perm)) |
| 64 | |
| 65 | # Check if any first letter is assigned zero |
| 66 | if any(mapping[letter] == 0 for letter in first_letters): |
| 67 | continue |
| 68 | |
| 69 | # Calculate the values of the addends |
| 70 | addend_values = [] |
| 71 | for addend in addends: |
| 72 | value = 0 |
| 73 | for letter in addend: |
| 74 | value = value * 10 + mapping[letter] |
| 75 | addend_values.append(value) |
| 76 | |
| 77 | # Calculate the value of the result |
| 78 | result_value = 0 |
| 79 | for letter in right_side: |
| 80 | result_value = result_value * 10 + mapping[letter] |
| 81 | |
| 82 | # Check if the sum of addends equals the result |
| 83 | if sum(addend_values) == result_value: |
| 84 | return mapping |
| 85 | |
| 86 | # Edge Case: No valid solution found |
| 87 | return None |
| 88 | |
| 89 | # Handled Edge Cases: Empty or None puzzle, Invalid puzzle format, No addends on left side, Empty right side, No letters in puzzle, More than 10 unique letters, Leading zeros in numbers, No valid solution found |