| 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("==", "=").split("=") |
| 21 | |
| 22 | # Edge Case: Invalid puzzle format |
| 23 | if len(parts) != 2: |
| 24 | return None |
| 25 | |
| 26 | right_side = parts[1].strip() |
| 27 | left_parts = [part.strip() for part in parts[0].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 (only from alphabetic characters) |
| 34 | letters = set() |
| 35 | for part in left_parts: |
| 36 | letters.update(part) |
| 37 | letters.update([char for char in right_side if char.isalpha()]) |
| 38 | |
| 39 | # Edge Case: No letters in puzzle |
| 40 | if not letters: |
| 41 | return None |
| 42 | |
| 43 | # Extract first letters (can't be zero for multi-digit numbers) |
| 44 | first_letters = {word[0] for word in left_parts if len(word) > 1} |
| 45 | # Add first letter of right side if it's alphabetic and multi-digit |
| 46 | if right_side and right_side[0].isalpha() and len(right_side) > 1: |
| 47 | first_letters.add(right_side[0]) |
| 48 | |
| 49 | # Convert letters to a sorted list for consistent ordering |
| 50 | sorted_letters = sorted(letters) |
| 51 | |
| 52 | # Edge Case: More than 10 unique letters (impossible to solve) |
| 53 | if len(sorted_letters) > 10: |
| 54 | return None |
| 55 | |
| 56 | # Generate all possible digit assignments |
| 57 | from itertools import permutations |
| 58 | |
| 59 | # Determine the range of permutations based on number of unique letters |
| 60 | if len(sorted_letters) <= 10: |
| 61 | # Try all permutations of digits for the letters |
| 62 | for perm in permutations(range(10), len(sorted_letters)): |
| 63 | mapping = dict(zip(sorted_letters, perm)) |
| 64 | |
| 65 | # Edge Case: Leading zero in any number |
| 66 | if any(mapping[first_letter] == 0 for first_letter in first_letters): |
| 67 | continue |
| 68 | |
| 69 | # Calculate the values of the left side terms |
| 70 | left_values = [] |
| 71 | for word in left_parts: |
| 72 | value = 0 |
| 73 | for char in word: |
| 74 | value = value * 10 + mapping[char] |
| 75 | left_values.append(value) |
| 76 | |
| 77 | # Calculate the value of the right side |
| 78 | if right_side.isalpha(): |
| 79 | # Right side contains only letters to be mapped |
| 80 | right_value = 0 |
| 81 | for char in right_side: |
| 82 | right_value = right_value * 10 + mapping[char] |
| 83 | else: |
| 84 | # Right side is a numeric value |
| 85 | try: |
| 86 | right_value = int(right_side) |
| 87 | except ValueError: |
| 88 | # If right side contains a mix of letters and numbers, this is an invalid puzzle |
| 89 | continue |
| 90 | |
| 91 | # Check if the equation is satisfied |
| 92 | if sum(left_values) == right_value: |
| 93 | return mapping |
| 94 | |
| 95 | # Edge Case: No valid solution found |
| 96 | return None |
| 97 | |
| 98 | # Edge Case: No valid solution found |
| 99 | return None |
| 100 | |
| 101 | # 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, Leading zero in any number, No valid solution found |