| 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 equality sign) |
| 24 | if "==" not in puzzle: |
| 25 | return None |
| 26 | |
| 27 | left_side, right_side = puzzle.split("==") |
| 28 | left_side = left_side.strip() |
| 29 | right_side = right_side.strip() |
| 30 | |
| 31 | # Edge Case: Empty sides after splitting |
| 32 | if not left_side or not right_side: |
| 33 | return None |
| 34 | |
| 35 | # Extract all words (addends and result) |
| 36 | addends = [word.strip() for word in left_side.split("+")] |
| 37 | result = right_side |
| 38 | |
| 39 | # Edge Case: No addends or empty result |
| 40 | if not addends or not result: |
| 41 | return None |
| 42 | |
| 43 | # Get all unique letters |
| 44 | letters = set() |
| 45 | for word in addends + [result]: |
| 46 | letters.update(word) |
| 47 | |
| 48 | # Edge Case: More than 10 unique letters (impossible to assign unique digits) |
| 49 | if len(letters) > 10: |
| 50 | return None |
| 51 | |
| 52 | # Get first letters (can't be zero) |
| 53 | first_letters = {word[0] for word in addends + [result]} |
| 54 | |
| 55 | # Convert letters to a list for indexing |
| 56 | letters_list = list(letters) |
| 57 | |
| 58 | # Try all possible digit assignments |
| 59 | from itertools import permutations |
| 60 | |
| 61 | # Edge Case: Handle puzzles with no letters |
| 62 | if not letters_list: |
| 63 | return {} |
| 64 | |
| 65 | # Try all permutations of digits for the letters |
| 66 | for perm in permutations(range(10), len(letters_list)): |
| 67 | mapping = dict(zip(letters_list, perm)) |
| 68 | |
| 69 | # Check if any first letter is assigned zero |
| 70 | # Edge Case: Leading zero in any number |
| 71 | if any(mapping[letter] == 0 for letter in first_letters): |
| 72 | continue |
| 73 | |
| 74 | # Calculate the sum of addends |
| 75 | addend_values = [] |
| 76 | for word in addends: |
| 77 | value = 0 |
| 78 | for letter in word: |
| 79 | value = value * 10 + mapping[letter] |
| 80 | addend_values.append(value) |
| 81 | |
| 82 | # Calculate the value of result |
| 83 | result_value = 0 |
| 84 | for letter in result: |
| 85 | result_value = result_value * 10 + mapping[letter] |
| 86 | |
| 87 | # Check if the equation is satisfied |
| 88 | if sum(addend_values) == result_value: |
| 89 | return mapping |
| 90 | |
| 91 | # Edge Case: No valid solution found |
| 92 | return None |
| 93 | |
| 94 | # Handled Edge Cases: Empty or None puzzle, Invalid puzzle format (no equality sign), Empty sides after splitting, No addends or empty result, More than 10 unique letters, Leading zero in any number, No valid solution found, Handle puzzles with no letters |