| 1 | from itertools import permutations |
| 2 | import re |
| 3 | |
| 1 | 4 | def solve(puzzle: str) -> dict[str, int] | None: |
| 2 | | pass |
| 5 | """ |
| 6 | Solve an alphametics puzzle. |
| 7 | |
| 8 | Args: |
| 9 | puzzle (str): The alphametics puzzle string in the format "A + B == C" |
| 10 | |
| 11 | Returns: |
| 12 | dict[str, int] | None: A dictionary mapping letters to digits that solves the puzzle, |
| 13 | or None if no solution exists. |
| 14 | |
| 15 | Example: |
| 16 | >>> solve("SEND + MORE == MONEY") |
| 17 | {'S': 9, 'E': 5, 'N': 6, 'D': 7, 'M': 1, 'O': 0, 'R': 8, 'Y': 2} |
| 18 | """ |
| 19 | # Edge Case: Empty or None puzzle |
| 20 | if not puzzle: |
| 21 | return None |
| 22 | |
| 23 | # Parse the puzzle into parts |
| 24 | # Remove spaces and split by '==' |
| 25 | parts = puzzle.replace(" ", "").split("==") |
| 26 | |
| 27 | # Edge Case: Invalid puzzle format (no '==' or incorrect number of parts) |
| 28 | if len(parts) != 2: |
| 29 | return None |
| 30 | |
| 31 | # Parse the left side to handle both addition and subtraction |
| 32 | left_side = parts[0] |
| 33 | |
| 34 | # Check if it's a subtraction puzzle |
| 35 | if "-" in left_side: |
| 36 | # Handle subtraction: A - B == C |
| 37 | terms = left_side.split("-") |
| 38 | if len(terms) != 2: |
| 39 | return None |
| 40 | minuend = terms[0] # A in A - B == C |
| 41 | subtrahend = terms[1] # B in A - B == C |
| 42 | result_word = parts[1] # C in A - B == C |
| 43 | |
| 44 | # Extract all unique letters |
| 45 | letters = set(re.findall(r'[A-Z]', puzzle)) |
| 46 | |
| 47 | # Edge Case: No letters in puzzle |
| 48 | if not letters: |
| 49 | return None |
| 50 | |
| 51 | # Find first letters of each word (can't be zero) |
| 52 | first_letters = {word[0] for word in [minuend, subtrahend, result_word] if word} |
| 53 | first_letters = {char for char in first_letters if char.isalpha()} |
| 54 | |
| 55 | # Get all digits (0-9) |
| 56 | digits = range(10) |
| 57 | |
| 58 | # Try all permutations of digits for the letters |
| 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.get(word[0]) == 0 for word in [minuend, subtrahend, result_word] if word): |
| 64 | continue |
| 65 | |
| 66 | # Convert words to numbers using the mapping |
| 67 | try: |
| 68 | minuend_value = int(''.join(str(mapping[char]) for char in minuend)) |
| 69 | subtrahend_value = int(''.join(str(mapping[char]) for char in subtrahend)) |
| 70 | result_value = int(''.join(str(mapping[char]) for char in result_word)) |
| 71 | |
| 72 | # Check if the subtraction is correct |
| 73 | if minuend_value - subtrahend_value == result_value: |
| 74 | return mapping |
| 75 | except (KeyError, ValueError): |
| 76 | continue |
| 77 | |
| 78 | return None |
| 79 | else: |
| 80 | # Handle addition: A + B + ... == C |
| 81 | addends = left_side.split("+") |
| 82 | result_word = parts[1] |
| 83 | |
| 84 | # Edge Case: No addends or no result |
| 85 | if not addends or not result_word: |
| 86 | return None |
| 87 | |
| 88 | # Extract all unique letters |
| 89 | letters = set(re.findall(r'[A-Z]', puzzle)) |
| 90 | |
| 91 | # Edge Case: No letters in puzzle |
| 92 | if not letters: |
| 93 | return None |
| 94 | |
| 95 | # Find first letters of each word (can't be zero) |
| 96 | first_letters = {word[0] for word in addends + [result_word] if word} |
| 97 | |
| 98 | # Edge Case: First letters include non-alphabetic characters (shouldn't happen with valid input) |
| 99 | first_letters = {char for char in first_letters if char.isalpha()} |
| 100 | |
| 101 | # Get all digits (0-9) |
| 102 | digits = range(10) |
| 103 | |
| 104 | # Try all permutations of digits for the letters |
| 105 | for perm in permutations(digits, len(letters)): |
| 106 | mapping = dict(zip(letters, perm)) |
| 107 | |
| 108 | # Edge Case: Leading zero in any word |
| 109 | if any(mapping.get(word[0]) == 0 for word in addends + [result_word] if word): |
| 110 | continue |
| 111 | |
| 112 | # Convert words to numbers using the mapping |
| 113 | try: |
| 114 | addend_values = [int(''.join(str(mapping[char]) for char in word)) for word in addends] |
| 115 | result_value = int(''.join(str(mapping[char]) for char in result_word)) |
| 116 | |
| 117 | # Check if the sum is correct |
| 118 | if sum(addend_values) == result_value: |
| 119 | return mapping |
| 120 | except (KeyError, ValueError): |
| 121 | # Edge Case: Mapping is incomplete or conversion fails |
| 122 | continue |
| 123 | |
| 124 | # Edge Case: No valid solution found |
| 125 | return None |
| 126 | |
| 127 | # Handled Edge Cases: Empty or None puzzle, Invalid puzzle format, No addends or no result, No letters in puzzle, Leading zero in any word, Mapping is incomplete or conversion fails, No valid solution found |