| 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 | left_side, right_side = puzzle.replace(" ", "").split("==") |
| 28 | |
| 29 | # Edge Case: Invalid puzzle format (no terms on left side) |
| 30 | if not left_side or not right_side: |
| 31 | return None |
| 32 | |
| 33 | # Split the left side by '+' to get addends |
| 34 | addends = left_side.split("+") |
| 35 | |
| 36 | # Edge Case: No addends |
| 37 | if not addends: |
| 38 | return None |
| 39 | |
| 40 | # Extract all unique letters |
| 41 | letters = set() |
| 42 | for part in addends + [right_side]: |
| 43 | letters.update(part) |
| 44 | |
| 45 | # Edge Case: More than 10 unique letters (impossible to assign unique digits) |
| 46 | if len(letters) > 10: |
| 47 | return None |
| 48 | |
| 49 | # Find first letters (can't be zero) |
| 50 | first_letters = {word[0] for word in addends + [right_side]} |
| 51 | |
| 52 | # Try all digit permutations for the letters |
| 53 | for perm in permutations(range(10), len(letters)): |
| 54 | mapping = dict(zip(letters, perm)) |
| 55 | |
| 56 | # Edge Case: Leading zero in any word |
| 57 | if any(mapping[first] == 0 for first in first_letters): |
| 58 | continue |
| 59 | |
| 60 | # Convert words to numbers |
| 61 | addend_values = [] |
| 62 | for addend in addends: |
| 63 | value = 0 |
| 64 | for char in addend: |
| 65 | value = value * 10 + mapping[char] |
| 66 | addend_values.append(value) |
| 67 | |
| 68 | result_value = 0 |
| 69 | for char in right_side: |
| 70 | result_value = result_value * 10 + mapping[char] |
| 71 | |
| 72 | # Check if the equation is satisfied |
| 73 | if sum(addend_values) == result_value: |
| 74 | return mapping |
| 75 | |
| 76 | # Edge Case: No valid solution found |
| 77 | return None |
| 78 | |
| 79 | # Handled Edge Cases: Empty or None puzzle, Invalid puzzle format (no equality), Invalid puzzle format (no terms on left side), No addends, More than 10 unique letters (impossible to assign unique digits), Leading zero in any word, No valid solution found |