| 1 | | def solve(puzzle: str) -> dict[str, int] | None: |
| 2 | | pass |
| 1 | from itertools import permutations |
| 2 | from typing import Dict, Optional |
| 3 | |
| 4 | def solve(puzzle: str) -> Optional[Dict[str, int]]: |
| 5 | """ |
| 6 | Solve an alphametics puzzle. |
| 7 | |
| 8 | Args: |
| 9 | puzzle: A string representing an alphametics puzzle (e.g., "SEND + MORE == MONEY") |
| 10 | |
| 11 | Returns: |
| 12 | A dictionary mapping letters to digits that solves the puzzle, 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 | # Parse the puzzle |
| 19 | # Edge Case: Empty or None puzzle |
| 20 | if not puzzle: |
| 21 | return None |
| 22 | |
| 23 | # Remove spaces and split by '==' |
| 24 | parts = puzzle.replace(" ", "").split("==") |
| 25 | |
| 26 | # Edge Case: Invalid puzzle format (no '==' or incorrect number of parts) |
| 27 | if len(parts) != 2: |
| 28 | return None |
| 29 | |
| 30 | # Split the left side by '+' to get the addends |
| 31 | addends = parts[0].split("+") |
| 32 | result = parts[1] |
| 33 | |
| 34 | # Edge Case: No addends or empty result |
| 35 | if not addends or not result: |
| 36 | return None |
| 37 | |
| 38 | # Collect all unique letters |
| 39 | letters = set() |
| 40 | for part in addends + [result]: |
| 41 | letters.update(part) |
| 42 | |
| 43 | # Edge Case: No letters in puzzle |
| 44 | if not letters: |
| 45 | return None |
| 46 | |
| 47 | # Collect first letters (can't be zero) |
| 48 | first_letters = {word[0] for word in addends + [result]} |
| 49 | |
| 50 | # Edge Case: More than 10 unique letters (impossible to assign unique digits) |
| 51 | if len(letters) > 10: |
| 52 | return None |
| 53 | |
| 54 | # Try all digit permutations for the letters |
| 55 | digits = range(10) |
| 56 | for perm in permutations(digits, len(letters)): |
| 57 | mapping = dict(zip(letters, perm)) |
| 58 | |
| 59 | # Edge Case: Leading zero in any word |
| 60 | if any(mapping[word[0]] == 0 for word in addends + [result]): |
| 61 | continue |
| 62 | |
| 63 | # Convert words to numbers |
| 64 | try: |
| 65 | addend_values = [int(''.join(str(mapping[c]) for c in word)) for word in addends] |
| 66 | result_value = int(''.join(str(mapping[c]) for c in result)) |
| 67 | except KeyError: |
| 68 | # Edge Case: Character not in mapping (shouldn't happen with correct logic, but safe check) |
| 69 | continue |
| 70 | |
| 71 | # Check if the sum is correct |
| 72 | if sum(addend_values) == result_value: |
| 73 | return mapping |
| 74 | |
| 75 | # Edge Case: No valid solution found |
| 76 | return None |
| 77 | # Handled Edge Cases: Empty or None puzzle, Invalid puzzle format, No addends or empty result, No letters in puzzle, More than 10 unique letters, Leading zero in any word, Character not in mapping, No valid solution found |