中提到的方法, itertools.permutations
因为 “禁止模块导入” :
import re
from typing import TypeVar
from collections.abc import Iterable
T = TypeVar('T')
# From https://docs.python.org/3/library/itertools.html#itertools.permutations.
def permutations(iterable: Iterable[T], r: int | None = None):
# permutations('ABCD', 2) → AB AC AD BA BC BD CA CB CD DA DB DC
# permutations(range(3)) → 012 021 102 120 201 210
pool = tuple(iterable)
n = len(pool)
r = n if r is None else r
if r > n:
return
indices = list(range(n))
cycles = list(range(n, n-r, -1))
yield tuple(pool[i] for i in indices[:r])
while n:
for i in reversed(range(r)):
cycles[i] -= 1
if cycles[i] == 0:
indices[i:] = indices[i+1:] + indices[i:i+1]
cycles[i] = n - i
else:
j = cycles[i]
indices[i], indices[-j] = indices[-j], indices[i]
yield tuple(pool[i] for i in indices[:r])
break
else:
return
def extract_s1_s2_s3(puzzle: str) -> tuple[str, str, str] | None:
"""Extracts S1, S2, and S3 from the alphametic puzzle string.
Args:
puzzle: A string representing the alphametic equation
(e.g., 'SEND + MORE = MONEY').
Returns:
A tuple (S1, S2, S3) if the puzzle format is valid, or None if invalid.
"""
match = re.match(r'(\w+)\s*\+\s*(\w+)\s*=\s*(\w+)', puzzle)
if not match:
return None
return match.groups()
def solve_alphametic(S1: str, S2: str, S3: str) -> tuple[int, int, int] | str:
"""Solves the alphametic problem S1 + S2 = S3.
Args:
S1: The first string operand in the equation.
S2: The second string operand in the equation.
S3: The result string in the equation.
Returns:
A tuple (N1, N2, N3) representing the solution if it exists,
or 'UNSOLVABLE' otherwise.
"""
letters = set(S1 + S2 + S3)
digits = '0123456789'
for perm in permutations(digits, len(letters)):
mapping = {letter: digit for letter, digit in zip(letters, perm)}
if mapping[S1[0]] == '0' or mapping[S2[0]] == '0' or mapping[S3[0]] == '0':
continue # Leading zeros are not allowed
N1 = int(''.join(mapping[char] for char in S1))
N2 = int(''.join(mapping[char] for char in S2))
N3 = int(''.join(mapping[char] for char in S3))
if N1 + N2 == N3:
return N1, N2, N3
return 'UNSOLVABLE'
def main() -> None:
"""Main function to execute the alphametic solver."""
puzzle = input('Enter the alphametic puzzle (e.g., "SEND + MORE = MONEY"): ')
parts = extract_s1_s2_s3(puzzle)
if parts is None:
print('Invalid puzzle format')
return
S1, S2, S3 = parts
solution = solve_alphametic(S1, S2, S3)
if solution == 'UNSOLVABLE':
print(solution)
else:
a, b, c = solution
print(f'{a} + {b} = {c}')
if __name__ == '__main__':
main()
使用示例1:
Enter the alphametic puzzle (e.g., "SEND + MORE = MONEY"): SEND + MORE = MONEY
9567 + 1085 = 10652
示例用法2:
Enter the alphametic puzzle (e.g., "SEND + MORE = MONEY"): COUPLE + COUPLE = QUARTET
653924 + 653924 = 1307848