| 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 | # Edge Case: Invalid puzzle format (no equality) |
| 24 | if "==" not in puzzle: |
| 25 | return None |
| 26 | |
| 27 | # Split into left and right sides |
| 28 | left_side, right_side = puzzle.replace(" ", "").split("==") |
| 29 | |
| 30 | # Edge Case: Invalid puzzle format (empty sides) |
| 31 | if not left_side or not right_side: |
| 32 | return None |
| 33 | |
| 34 | # Split left side by '+' to get addends |
| 35 | addends = left_side.split("+") |
| 36 | |
| 37 | # Edge Case: No addends on left side |
| 38 | if not addends: |
| 39 | return None |
| 40 | |
| 41 | # Collect all unique letters |
| 42 | letters = set() |
| 43 | for part in addends + [right_side]: |
| 44 | letters.update(part) |
| 45 | |
| 46 | # Edge Case: No letters in puzzle |
| 47 | if not letters: |
| 48 | return None |
| 49 | |
| 50 | # Identify first letters (can't be zero) |
| 51 | first_letters = {word[0] for word in addends + [right_side]} |
| 52 | |
| 53 | # Edge Case: More than 10 unique letters (impossible to solve) |
| 54 | if len(letters) > 10: |
| 55 | return None |
| 56 | |
| 57 | # Try all digit permutations for the letters |
| 58 | digits = range(10) |
| 59 | for perm in permutations(digits, len(letters)): |
| 60 | mapping = dict(zip(letters, perm)) |
| 61 | |
| 62 | # Edge Case: Leading zero in any word |
| 63 | if any(mapping[word[0]] == 0 for word in addends + [right_side]): |
| 64 | continue |
| 65 | |
| 66 | # Convert words to numbers |
| 67 | try: |
| 68 | addend_values = [int(''.join(str(mapping[c]) for c in word)) for word in addends] |
| 69 | result_value = int(''.join(str(mapping[c]) for c in right_side)) |
| 70 | except KeyError: |
| 71 | # Edge Case: Mapping is incomplete (shouldn't happen with correct permutation logic) |
| 72 | continue |
| 73 | |
| 74 | # Check if the sum matches |
| 75 | if sum(addend_values) == result_value: |
| 76 | return mapping |
| 77 | |
| 78 | # Edge Case: No valid solution found |
| 79 | return None |
| 80 | |
| 81 | # Handled Edge Cases: Empty or None puzzle, Invalid puzzle format (no equality), Invalid puzzle format (empty sides), No addends on left side, No letters in puzzle, More than 10 unique letters (impossible to solve), Leading zero in any word, Mapping is incomplete, No valid solution found |