| 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 | right_side = parts[1] |
| 27 | left_sides = parts[0].split("+") |
| 28 | |
| 29 | # Edge Case: No terms on the left side |
| 30 | if not left_sides or any(not term for term in left_sides): |
| 31 | return None |
| 32 | |
| 33 | # Edge Case: Empty right side |
| 34 | if not right_side: |
| 35 | return None |
| 36 | |
| 37 | # Extract all unique letters |
| 38 | letters = set() |
| 39 | for part in left_sides + [right_side]: |
| 40 | letters.update(part) |
| 41 | |
| 42 | # Edge Case: No letters in puzzle |
| 43 | if not letters: |
| 44 | return None |
| 45 | |
| 46 | # Extract first letters (can't be zero) |
| 47 | first_letters = {word[0] for word in left_sides + [right_side]} |
| 48 | |
| 49 | # Edge Case: More than 10 unique letters (impossible to solve) |
| 50 | if len(letters) > 10: |
| 51 | return None |
| 52 | |
| 53 | # Convert letters to a list for indexing |
| 54 | letters_list = list(letters) |
| 55 | |
| 56 | # Try all possible digit assignments |
| 57 | from itertools import permutations |
| 58 | |
| 59 | # Edge Case: Handle permutations of digits for letters |
| 60 | for perm in permutations(range(10), len(letters)): |
| 61 | mapping = dict(zip(letters_list, perm)) |
| 62 | |
| 63 | # Check if any first letter is assigned zero |
| 64 | if any(mapping[letter] == 0 for letter in first_letters): |
| 65 | continue |
| 66 | |
| 67 | # Calculate left side values |
| 68 | left_sum = 0 |
| 69 | valid = True |
| 70 | |
| 71 | # Edge Case: Check for valid number conversion on left side |
| 72 | for word in left_sides: |
| 73 | num = 0 |
| 74 | for char in word: |
| 75 | if char in mapping: |
| 76 | num = num * 10 + mapping[char] |
| 77 | else: |
| 78 | valid = False |
| 79 | break |
| 80 | if not valid: |
| 81 | break |
| 82 | left_sum += num |
| 83 | |
| 84 | if not valid: |
| 85 | continue |
| 86 | |
| 87 | # Calculate right side value |
| 88 | right_num = 0 |
| 89 | |
| 90 | # Edge Case: Check for valid number conversion on right side |
| 91 | for char in right_side: |
| 92 | if char in mapping: |
| 93 | right_num = right_num * 10 + mapping[char] |
| 94 | else: |
| 95 | valid = False |
| 96 | break |
| 97 | |
| 98 | if not valid: |
| 99 | continue |
| 100 | |
| 101 | # Check if equation is satisfied |
| 102 | if left_sum == right_num: |
| 103 | return mapping |
| 104 | |
| 105 | # Edge Case: No solution found |
| 106 | return None |
| 107 | |
| 108 | # 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, Permutations of digits for letters, First letter assigned zero, Valid number conversion on left side, Valid number conversion on right side, No solution found |