| 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 | The function handles the following edge cases: |
| 12 | - Invalid puzzle format |
| 13 | - Puzzles with no solution |
| 14 | - Puzzles with multiple solutions (returns the first found) |
| 15 | - Leading zeros in numbers |
| 16 | - Repeated letters |
| 17 | """ |
| 18 | # Edge Case: Empty or None puzzle |
| 19 | if not puzzle: |
| 20 | return None |
| 21 | |
| 22 | # Parse the puzzle |
| 23 | # Edge Case: Invalid puzzle format (no '==' found) |
| 24 | if '==' not in puzzle: |
| 25 | return None |
| 26 | |
| 27 | try: |
| 28 | left_side, right_side = puzzle.replace(' ', '').split('==') |
| 29 | addends = left_side.split('+') |
| 30 | except ValueError: |
| 31 | # Edge Case: Malformed puzzle |
| 32 | return None |
| 33 | |
| 34 | # Edge Case: No addends or no result |
| 35 | if not addends or not right_side: |
| 36 | return None |
| 37 | |
| 38 | # Extract all unique letters |
| 39 | letters = set() |
| 40 | for part in addends + [right_side]: |
| 41 | letters.update(part) |
| 42 | |
| 43 | # Edge Case: More than 10 unique letters (impossible to solve) |
| 44 | if len(letters) > 10: |
| 45 | return None |
| 46 | |
| 47 | # Identify first letters (can't be zero) |
| 48 | first_letters = {word[0] for word in addends + [right_side]} |
| 49 | |
| 50 | # Convert to list for indexing |
| 51 | letters = list(letters) |
| 52 | |
| 53 | # Try all possible digit assignments |
| 54 | from itertools import permutations |
| 55 | |
| 56 | # Edge Case: Handle puzzles with no letters |
| 57 | if not letters: |
| 58 | return {} |
| 59 | |
| 60 | for perm in permutations(range(10), len(letters)): |
| 61 | mapping = dict(zip(letters, perm)) |
| 62 | |
| 63 | # Check if any first letter is assigned zero |
| 64 | # Edge Case: Leading zeros in numbers |
| 65 | if any(mapping[letter] == 0 for letter in first_letters): |
| 66 | continue |
| 67 | |
| 68 | # Convert words to numbers |
| 69 | try: |
| 70 | addend_values = [] |
| 71 | for word in addends: |
| 72 | value = 0 |
| 73 | for letter in word: |
| 74 | value = value * 10 + mapping[letter] |
| 75 | addend_values.append(value) |
| 76 | |
| 77 | result_value = 0 |
| 78 | for letter in right_side: |
| 79 | result_value = result_value * 10 + mapping[letter] |
| 80 | |
| 81 | # Check if the equation is satisfied |
| 82 | if sum(addend_values) == result_value: |
| 83 | return mapping |
| 84 | except KeyError: |
| 85 | # Edge Case: Incomplete mapping (shouldn't happen with permutations but just in case) |
| 86 | continue |
| 87 | |
| 88 | # Edge Case: No solution found |
| 89 | return None |
| 90 | |
| 91 | # Handled Edge Cases: Empty or None puzzle, Invalid puzzle format, Malformed puzzle, No addends or no result, More than 10 unique letters, Leading zeros in numbers, Handle puzzles with no letters, Incomplete mapping, No solution found |