| 1 | 1 | def solve(puzzle: str) -> dict[str, int] | None: |
| 2 | | pass |
| 2 | """ |
| 3 | Solve an alphametics puzzle. |
| 4 | |
| 5 | Args: |
| 6 | puzzle: A string representing the puzzle (e.g., "SEND + MORE == MONEY") |
| 7 | |
| 8 | Returns: |
| 9 | A dictionary mapping letters to digits, or None if no solution exists |
| 10 | """ |
| 11 | # Edge Case: Empty or None puzzle |
| 12 | if not puzzle: |
| 13 | return None |
| 14 | |
| 15 | # Parse the puzzle |
| 16 | parts = puzzle.replace("==", "=").replace(" ", "").split("=") |
| 17 | |
| 18 | # Edge Case: Invalid puzzle format (no equals sign or too many parts) |
| 19 | if len(parts) != 2: |
| 20 | return None |
| 21 | |
| 22 | left_side, right_side = parts[0], parts[1] |
| 23 | |
| 24 | # Split the left side by '+' to get addends |
| 25 | addends = left_side.split("+") |
| 26 | |
| 27 | # Edge Case: No addends on the left side |
| 28 | if not addends or not all(addends): |
| 29 | return None |
| 30 | |
| 31 | # Edge Case: Empty right side |
| 32 | if not right_side: |
| 33 | return None |
| 34 | |
| 35 | # Extract all unique letters |
| 36 | letters = set() |
| 37 | for part in addends + [right_side]: |
| 38 | letters.update(part) |
| 39 | |
| 40 | # Edge Case: More than 10 unique letters (impossible to assign unique digits) |
| 41 | if len(letters) > 10: |
| 42 | return None |
| 43 | |
| 44 | # Identify first letters (can't be zero) |
| 45 | first_letters = {word[0] for word in addends + [right_side]} |
| 46 | |
| 47 | # Convert words to lists of characters for easier processing |
| 48 | addend_chars = [list(word) for word in addends] |
| 49 | result_chars = list(right_side) |
| 50 | |
| 51 | # Prepare a list of all letters |
| 52 | letters_list = list(letters) |
| 53 | |
| 54 | def to_number(word_chars, mapping): |
| 55 | """Convert a list of characters to a number using the given mapping""" |
| 56 | return int(''.join(str(mapping[char]) for char in word_chars)) |
| 57 | |
| 58 | def is_valid_solution(mapping): |
| 59 | """Check if the current mapping satisfies the puzzle equation""" |
| 60 | # Check if any first letter is mapped to 0 |
| 61 | for letter in first_letters: |
| 62 | if mapping[letter] == 0: |
| 63 | return False |
| 64 | |
| 65 | # Calculate the sum of addends |
| 66 | total = 0 |
| 67 | for addend in addend_chars: |
| 68 | total += to_number(addend, mapping) |
| 69 | |
| 70 | # Check if it equals the result |
| 71 | return total == to_number(result_chars, mapping) |
| 72 | |
| 73 | def backtrack(index, mapping, used_digits): |
| 74 | """Recursive backtracking function to find a valid digit assignment""" |
| 75 | # Base case: all letters have been assigned |
| 76 | if index == len(letters_list): |
| 77 | if is_valid_solution(mapping): |
| 78 | return mapping.copy() |
| 79 | return None |
| 80 | |
| 81 | letter = letters_list[index] |
| 82 | |
| 83 | # Try each digit from 0-9 |
| 84 | for digit in range(10): |
| 85 | # Skip if digit is already used |
| 86 | if digit in used_digits: |
| 87 | continue |
| 88 | |
| 89 | # Skip if this is a first letter and digit is 0 |
| 90 | if letter in first_letters and digit == 0: |
| 91 | continue |
| 92 | |
| 93 | # Assign the digit to the letter |
| 94 | mapping[letter] = digit |
| 95 | used_digits.add(digit) |
| 96 | |
| 97 | # Recurse to the next letter |
| 98 | result = backtrack(index + 1, mapping, used_digits) |
| 99 | if result is not None: |
| 100 | return result |
| 101 | |
| 102 | # Backtrack: remove the assignment |
| 103 | del mapping[letter] |
| 104 | used_digits.remove(digit) |
| 105 | |
| 106 | # No valid assignment found for this letter |
| 107 | return None |
| 108 | |
| 109 | # Start the backtracking search |
| 110 | solution = backtrack(0, {}, set()) |
| 111 | return solution |
| 112 | |
| 113 | # Handled Edge Cases: Empty or None puzzle, Invalid puzzle format (no equals sign or too many parts), No addends on the left side, Empty right side, More than 10 unique letters (impossible to assign unique digits) |