| 1 | from itertools import permutations |
| 2 | |
| 1 | 3 | def solve(puzzle: str) -> dict[str, int] | None: |
| 2 | | pass |
| 4 | """ |
| 5 | Solve an alphametics puzzle. |
| 6 | |
| 7 | Args: |
| 8 | puzzle (str): A string representing the alphametics puzzle (e.g., "SEND + MORE == MONEY") |
| 9 | |
| 10 | Returns: |
| 11 | dict[str, int] | None: A dictionary mapping letters to digits that solves the puzzle, |
| 12 | or None if no solution exists. |
| 13 | |
| 14 | Example: |
| 15 | >>> solve("SEND + MORE == MONEY") |
| 16 | {'S': 9, 'E': 5, 'N': 6, 'D': 7, 'M': 1, 'O': 0, 'R': 8, 'Y': 2} |
| 17 | """ |
| 18 | # Edge Case: Empty or None puzzle |
| 19 | if not puzzle: |
| 20 | return None |
| 21 | |
| 22 | # Parse the puzzle into parts |
| 23 | parts = puzzle.replace("==", "=").replace(" ", "").split("=") |
| 24 | |
| 25 | # Edge Case: Invalid puzzle format (no equals sign or too many parts) |
| 26 | if len(parts) != 2: |
| 27 | return None |
| 28 | |
| 29 | left_side, right_side = parts[0], parts[1] |
| 30 | |
| 31 | # Edge Case: Empty sides |
| 32 | if not left_side or not right_side: |
| 33 | return None |
| 34 | |
| 35 | # Split the left side by '+' to get addends |
| 36 | addends = left_side.split("+") |
| 37 | |
| 38 | # Edge Case: No addends on left side |
| 39 | if not addends or any(not addend for addend in addends): |
| 40 | return None |
| 41 | |
| 42 | # Extract all unique letters |
| 43 | letters = set(ch for ch in puzzle if ch.isalpha()) |
| 44 | |
| 45 | # Edge Case: No letters in puzzle |
| 46 | if not letters: |
| 47 | return None |
| 48 | |
| 49 | # Extract first letters of each word (cannot be zero) |
| 50 | first_letters = {word[0] for word in addends + [right_side] if word} |
| 51 | |
| 52 | # Edge Case: More than 10 unique letters (impossible to assign unique digits) |
| 53 | if len(letters) > 10: |
| 54 | return None |
| 55 | |
| 56 | # Try all digit permutations for the letters |
| 57 | digits = range(10) |
| 58 | for perm in permutations(digits, len(letters)): |
| 59 | mapping = dict(zip(letters, perm)) |
| 60 | |
| 61 | # Edge Case: Leading zero in any word |
| 62 | if any(mapping.get(word[0]) == 0 for word in addends + [right_side] if word): |
| 63 | continue |
| 64 | |
| 65 | # Convert words to numbers using the current mapping |
| 66 | try: |
| 67 | addend_values = [int(''.join(str(mapping[ch]) for ch in addend)) for addend in addends] |
| 68 | result_value = int(''.join(str(mapping[ch]) for ch in right_side)) |
| 69 | |
| 70 | # Check if the sum is correct |
| 71 | if sum(addend_values) == result_value: |
| 72 | return mapping |
| 73 | except (KeyError, ValueError): |
| 74 | # Edge Case: Mapping is incomplete or conversion fails |
| 75 | continue |
| 76 | |
| 77 | # Edge Case: No valid solution found |
| 78 | return None |
| 79 | |
| 80 | # Handled Edge Cases: Empty or None puzzle, Invalid puzzle format, Empty sides, No addends on left side, No letters in puzzle, More than 10 unique letters, Leading zero in any word, Mapping is incomplete or conversion fails, No valid solution found |