8
\$\begingroup\$

Cryptarithms

Cryptarithms, or Verbal arithmetic, are substitution puzzles where letters represent unique digits:

    S E N D
  + M O R E
  =========
  M O N E Y

The goal is to find the digit-letter mapping which will translate the puzzle into a valid mathematical computation.

My goal was to write a Python script which will find the solution(s).

Method

Using the above puzzle, the solution finder breaks the puzzle down into a series of digit-sum columns. Starting at the left (carry in & carry out from columns not shown)

  0   = M
S + M = O
E + O = N
N + R = E
D + E = Y

Starting at the 1's column (D+E=Y), the solver tries D=0 and E=1, and computes Y=1. This solution is discarded, since duplicate 1 is already used by E. After several more iterations, it eventual tries D=1, E=2 and directly computes 1+2=Y and determines Y=3 with no carry into the tens column.

With a valid ones column digit-sum, it advances to the tens column: N+R=E. Since E has already been assigned a value from the ones-column, it is "known". The first available digit for N is 4, so the column solver evaluates 4+R=2, and determines R=8 with a carry of 1 into the hundreds column.

It descends deeper into the hundreds column, and possibly deeper still to the thousands column, as it continues its exploration. When it reaches impossibilities, it unwinds the stack, and explores different branches.

Since the solution is generated using yield and yield from statements, when the first solution is found, it returns that solution, and pauses the search, until the next solution is requested.

The test code actually tries to generate all solutions, to ensure the solutions to the given puzzles are unique. Some of the example puzzles are taken from Cryptarithms.com.

Code

All feedback welcome.

import re

from collections import Counter
from time import perf_counter
from typing import Callable, Iterator, NewType

Term = NewType('Term', str)
Operator = NewType('Operator', str)

Solution = dict[str, int]
Solver = Callable[[set[int]], Iterator[Solution]]

TRACE = False

#===============================================================================

class CryptArithm:
    """
    Solver for a "word math" puzzle

        S E N D        9 5 6 7
      + M O R E      + 1 0 8 5
      =========      =========
      M O N E Y      1 0 6 5 2
    """

    SUPPORTED_OPS = {'=', '+', '-'}

    #---------------------------------------------------------------------------
    
    class Variable:
        """
        A letter-variable in the word-math puzzle.

        Holds the letter, the allowed digits for the letter, and its
        current candidate value.
        """

        __slots__ = ('_letter', '_allowed', '_value')

        def __init__(self, solver: 'CryptArithm', letter: str):
            self._letter = letter
            self._allowed = set(solver._digits)
            self._value = 0

        def exclude(self, *values):
            """
            Specified one or more verboten values for the variable.

            Used primarily to prevent terms with leading zeros.
            """
            self._allowed -= set(values)

        def solver(self, solver: Solver) -> Solver:
            """
            The solver for a variable simply tries each allowable digit,
            in turn, provided the digit is not currently used by another
            letter.

            For each valid possible digit, yield solutions from the
            next solver, passed in as an argument.
            """
            
            def solve(used: set[int]) -> Iterator[Solution]:
                """
                The solve for a variable by trying each allowable digit,
                in turn, provided the digit is not currently in use.
                Digits in use are passed as an argument

                For each valid possible digit, yield solutions from the
                next solver, passed in as an argument to the wrapper.
                """
                
                for digit in self._allowed - used:
                    self._value = digit
                    yield from solver(used | {digit})

            return solve

        def __str__(self):
            value = self._value
            if value is None:
                value = '{' + ''.join(map(str, self._allowed)) + '}'
            return f"{self._letter}={value}"

        def __repr__(self):
            return f"<{self._letter}>"
                
    #---------------------------------------------------------------------------

    class Column:
        """
        A digit-sum column in the word-puzzle.

        For example, with SEND+MORE=MONEY, the last column of digits
        expresses the digit sum D+E=Y.

        A digit-sum will include a carry-in from a "smaller" column, if
        present, and a carry-out to a "larger" column, if present.
        """

        def __init__(self, solver: 'CryptArithm', result: 'Variable'):
            self._base = solver._base
            self._addends = Counter()
            self._result = result
            self._carry_in = None
            self._carry_to = None
            self._carry = 0

        def add(self, var: 'Variable') -> None:
            """
            Add a digit addend to the digit sum.
            """
            self._addends[var] += 1

        def sub(self, var: 'Variable') -> None:
            """
            Subtract a digit subtrahend from the digit sum.
            """
            self._addends[var] -= 1

        def carry_from(self, other: 'Column') -> None:
            """
            Indicate this digit-sum has a carry-in from another column.
            """
            self._carry_in = other
            other._carry_to = self

        def __str__(self):
            exp = f"{self._result._letter}=" if self._result else "0="
            if self._carry_in:
                exp += "carry"
            for var, count in self._addends.items():
                if count == 1:
                    exp += f"+{var._letter}"
                elif count == -1:
                    exp += f"-{var._letter}"
                elif count != 0:
                    exp += f"{count:+d}{var._letter}"
            return exp

        def __repr__(self):
            return f"Col[{self}]"

        def unknowns(self, knowns: set['Variable']) -> list['Variable']:
            """
            Given a set of known variables, determine the list of
            unknown variables in this digit-sum column, ordered in
            decreasing usage.
            """
            unknowns = Counter(self._addends)
            if self._result:
                unknowns[self._result] -= 1

            unknowns = [(var, abs(count)) for var, count in unknowns.items()]
            unknowns = sorted(unknowns, key=lambda vc: vc[1], reverse=True)
            return [var for var, _ in unknowns if var not in knowns]

        def validator(self, solver: Solver) -> Solver:
            """
            When all digits are "known" in a digit-sum column, verify the
            correct result digit is obtained and compute the carry to the
            next column.  If the digit-sum is correct, and a carry out is
            allowed or the carry is determined to be zero, yield solutions
            from the next solver, passed in as an argument.
            """

            def validate(used: set[int]) -> Iterator[Solution]:
                """
                When all digits are "known" in a digit-sum column, verify the
                correct result digit is obtained and compute the carry to the
                next column.  If the digit-sum is correct, and a carry out is
                allowed or the carry is determined to be zero, yield solutions
                from the next solver, passed in as an argument to the wrapper.
                """
                result = sum(count * var._value
                             for var, count in self._addends.items())
                if self._carry_in:
                    result += self._carry_in._carry

                carry, result = result // self._base, result % self._base

                if (result == self._result._value and
                        (carry == 0 or self._carry_to)):
                    self._carry = carry
                    yield from solver(used)

            return validate

        def _solve_for_result(self, solver: Solver) -> Solver:
            """
            When all digits but the result digit are known in a digit-sum
            column, compute the result digit and carry to the next column.
            If the result digit is allowed (and not currently used by
            another variable), yield solutions from the next solver,
            passed in as an argument.
            """
            
            def solve(used: set[int]) -> Iterator[Solution]:
                """
                When all digits but the result digit are known in a digit-sum
                column, compute the result digit and carry to the next column.
                If the result digit is allowed (and not in the used set),
                yield solutions from the next solver, passed in as an argument
                to the wrapper function.
                """
                result = sum(count * var._value
                             for var, count in self._addends.items())
                if self._carry_in:
                    result += self._carry_in._carry

                carry, digit = result // self._base, result % self._base

                allowed = self._result._allowed - used
                if digit in allowed and (carry == 0 or self._carry_to):
                    self._result._value = digit
                    self._carry = carry
                    yield from solver(used | {digit})

            return solve

        def _solve_for_addend(self, addend: 'Variable'):
            """
            One unknown digit in the digit-sum column, but not the digit-sum's
            result digit.

            Use modular arithmetic to compute the unique digit that satisfies
            the digit-sum column.  If the digit is allowed (and not used),
            yield solutions from the subsequent solver.
            """
            def solver(solver: Solver) -> Solver:
                def solve(used: set[int]) -> Iterator[Solution]:
                    addend._value = 0
                    result = sum(count * var._value
                                 for var, count in self._addends.items())                    
                    if self._carry_in:
                        result += self._carry_in._carry

                    multiplier = self._addends[addend]  # +/- 1
                    digit = (self._result._value - result) * multiplier
                    digit %= self._base

                    result += digit * multiplier
                    carry = result // self._base

                    allowed = addend._allowed - used
                    if digit in allowed and (carry == 0 or self._carry_to):
                        addend._value = digit
                        self._carry = carry
                        yield from solver(used | {digit})

                return solve
            return solver

        def solver(self, unknown: 'Variable'):
            """
            Determine which specialized solver to used for a digit sum column.

            If the only unknown is the result digit,
                use the solve_for_result solver.
            If the only unknown is not a repeated digit,
                use the solve_for_addend solver.

            Returns None if no specialized solver exists.
            """
            if unknown == self._result:
                if self._addends[unknown] == 0:
                    return self._solve_for_result
            elif abs(self._addends[unknown]) == 1:
                return self._solve_for_addend(unknown)

            return None
                

    #---------------------------------------------------------------------------
    
    def __init__(self, puzzle: str, base: int = 10, leading_zeros: bool = False):
        self._puzzle = puzzle
        self._base = base
        self._leading_zeros = leading_zeros

        self._digits = range(base)
        self._variables = self._create_variables(puzzle)
        self._columns = self._create_columns(puzzle)

    def _create_variables(self, puzzle: str) -> dict[str, Variable]:
        """
        Create a variable for each unique letter in the puzzle.
        """
        
        letters = set(ch for ch in puzzle if ch.isalpha())
        if len(letters) > self._base:
            raise ValueError(f"Puzzle has too many variables for base-{base}")

        return {letter: self.Variable(self, letter) for letter in letters}

    @classmethod
    def _parse(cls, puzzle: str) -> tuple[list[Operator], list[Term]]:
        """
        Parse the puzzle into tokens.

        * Remove all spaces
        * Replace multiple equal signs with a single equals character
        * Split into word and non-word tokens
        * Validate proper term/operator sequence
        * Return operators and terms separately.
        """
        
        equation = re.sub('=+', '=', re.sub(r'\s+', '', puzzle))
        tokens = re.split(r'(\W+)', equation)
        terms = [token for token in tokens if token.isalpha()]
        operators = [token for token in tokens if not token.isalpha()]

        # Validation
        if len(tokens) < 5 or len(terms) != len(operators) + 1:
            raise ValueError("Expected 'term op term op term [op term]...'")

        if (unsupported := set(operators) - cls.SUPPORTED_OPS):
            raise NotImplementedError(f"Unsupported: {repr(unsupported)[1:-1]}")
        
        if operators.count('=') != 1:
            raise ValueError("Only one equals operator allowed")
        
        if operators[-1] != '=':
            raise ValueError("Last operator expected to be equals")

        return operators, terms

    def _create_columns(self, puzzle: str) -> list[Column]:
        """
        Parse the puzzle into a list of digit-sum columns.
        """
        operators, terms = self._parse(puzzle)

        # Leading zeros are not allowed
        if not self._leading_zeros:
            for term in terms:
                if len(term) > 1:
                    self._variables[term[0]].exclude(0)

        num_columns = max(map(len, terms))      # Maximum columns
        terms = [term[::-1] for term in terms]  # Reverse individual terms
        operators.insert(0, '+')                # First term is "added"
        result = terms.pop()                    # Extract result
        operators.pop()                         # Discard "=" operator

    
        # Extract into columns
        columns = []
        for col_num in range(num_columns):
            if col_num < len(result):
                var = self._variables[result[col_num]]
            else:
                var = None
                
            column = self.Column(self, var)
            for op, term in zip(operators, terms):
                if col_num < len(term):
                    var = self._variables[term[col_num]]
                    if op == '+':
                        column.add(var)
                    elif op == '-':
                        column.sub(var)
                    else:
                        raise RuntimeError(f"Unexpected operator: {op}")

            columns.append(column)

        for to, frm in zip(columns[1:], columns[:-1]):
            to.carry_from(frm)
        
        return columns

    def _strategize(self):
        """
        Determine a solving strategy.

        Returns a list of strategy functions.
        """

        strategies = []
        knowns = set()
        
        # For each column, starting at the ones-column...
        for column in self._columns:
            unknowns = column.unknowns(knowns)
            if TRACE:
                print(f"{column}: {unknowns}")

            # If the column has unknowns...
            if unknowns:
                # if it has more than one uknown ...
                for var in unknowns[:-1]:
                    strategies.append(var.solver)

                # For the last unknown, attempt to find a specialized solver
                last = unknowns[-1]
                solver = column.solver(last)
                if solver:
                    strategies.append(solver)
                else:
                    # Failing that, try every possible value ...
                    strategies.append(last.solver)
                    # ... and validate the column
                    strategies.append(column.validator)

                knowns |= set(unknowns)
            else:
                # No unknowns!  Just validate the column
                strategies.append(column.validator)

        return strategies

    def solutions(self) -> Iterator[Solution]:
        """
        Create a solver strategy, and then generate all possible
        solutions.
        """
        
        strategies = self._strategize()
        solver = self._emitter()
        for strategy in reversed(strategies):
            solver = strategy(solver)

        yield from solver(set())

    def solve(self) -> Solution:
        """
        Find the unique solution to the puzzle.
        """
        solutions = self.solutions()
        try:
            solution = next(solutions)
        except StopIteration:
            raise ValueError("No solution found") from None

        try:
            solution = next(solutions)
            raise ValueError("Multiple solutions!")
        except StopIteration:
            return solution
        

    def _emitter(self) -> Solver:
        def solver(used: set[int]) -> Iterator[Solution]:
            yield {var._letter: var._value for var in self._variables.values()}
        return solver

    def substitute(self, solution: dict[str, int]) -> str:
        """
        Translate the puzzle using the given solution, into a numeric
        version of the puzzle.
        """
        if self._base > 10:
            raise NotImplementedError("Not yet implemented.")

        puzzle = self._puzzle
        for key, val in solution.items():
            puzzle = puzzle.replace(key, str(val))

        return puzzle

#===============================================================================

if __name__ == '__main__':

    puzzles = [
        """\
          S E N D
        + M O R E
        =========
        M O N E Y""",
        
        """\
        F O R T Y
        +   T E N
        +   T E N
        =========
        S I X T Y""",

        """\
              T I L E S
        + P U Z Z L E S
        ===============
          P I C T U R E""",
        
        """\
          D O U B L E
        + D O U B L E
        +     T O I L
        =============
        T R O U B L E""",
        
        """\
          T H R E E
        + T H R E E
        +     T W O
        +     T W O
        +     O N E
        ===========
        E L E V E N""",

        """\
        SO+MANY+MORE+MEN+SEEM+TO+SAY+THAT+
        THEY+MAY+SOON+TRY+TO+STAY+AT+HOME+
        SO+AS+TO+SEE+OR+HEAR+THE+SAME+ONE+
        MAN+TRY+TO+MEET+THE+TEAM+ON+THE+
        MOON+AS+HE+HAS+AT+THE+OTHER+TEN
        =TESTS
        """
        ]

    for puzzle in puzzles:
        start = perf_counter()
        ca = CryptArithm(puzzle)
        solution = ca.solve()
        stop = perf_counter()

        print(f"{stop-start:.3f} sec")
        print(ca.substitute(solution))
        print()

Output

0.006 sec
          9 5 6 7
        + 1 0 8 5
        =========
        1 0 6 5 2

0.007 sec
        2 9 7 8 6
        +   8 5 0
        +   8 5 0
        =========
        3 1 4 8 6

0.003 sec
              9 1 5 4 2
        + 3 0 7 7 5 4 2
        ===============
          3 1 6 9 0 8 4

0.002 sec
          7 9 8 0 6 4
        + 7 9 8 0 6 4
        +     1 9 3 6
        =============
        1 5 9 8 0 6 4

0.007 sec
          8 4 6 1 1
        + 8 4 6 1 1
        +     8 0 3
        +     8 0 3
        +     3 9 1
        ===========
        1 7 1 2 1 9

3.398 sec
        31+2764+2180+206+3002+91+374+9579+
        9504+274+3116+984+91+3974+79+5120+
        31+73+91+300+18+5078+950+3720+160+
        276+984+91+2009+950+9072+16+950+
        2116+73+50+573+79+950+19508+906
        =90393
\$\endgroup\$

1 Answer 1

4
\$\begingroup\$

Bugs

This code will crash:

        raise ValueError(f"Puzzle has too many variables for base-{base}")

since base is not defined. You likely meant to write self._base.

Quality of life

Consider expressing your output durations in milliseconds instead of seconds and include one or two decimals for more precision; and showing the original puzzle along with its output.

Scoped main

It's not enough to have a __main__ guard - all of those symbols are still going to be in global scope and visible to the rest of your CryptArithm code unless you move the main code into a function.

Such namespace pollution can have surprising effects, so it's best to avoid it altogether and limit the scope of your main symbols.

Early constraints

I think you're doing the right thing by declaring leading_zeros as a constructor argument defaulting to False. I find it odd, however, that at one point during construction the instance is effectively in an incorrect/inconsistent state, because the leading variable's _allowed still includes zero. It's possible to prune zero from this variable on construction without requiring storage of the leading_zeros member. That said, this is somewhat chicken-and-egg, because you're setting up your variables before you parse. If you set up your variables during or after parse this inconsistency can be avoided.

Alternate algorithms

I wrote an alternate approach to this that:

  • Forms a linear discrete system of polynomial order 1
  • Attempts to solve the system with a recursive root-finding loop
  • Performs tree pruning based on the knowledge that the polynomial, when sorted in decreasing order of its coefficients, will produce a monotonically increasing sum given a lexicographically sorted permutation

This approach scales quite differently from yours. In most cases it's slower, but in others it's able to yield a result very quickly.


def by_coeff(kv):
    return kv[1]


class CryptRoots:
    __slots__ = ('puzzle_desc', 'coeffs', 'names', 'zero_pos')

    RE_WS = re.compile('\s*')
    RE_EQN = re.compile(
        r'^([^=]+?)'
        r'=+'
        r'([^=]+?)$'
    )
    RE_TERMS = re.compile(
        r'([+-])\s*([ A-Z]+)'
    )

    def __init__(self, puzzle_desc: str):
        self.puzzle_desc = puzzle_desc
        puzzle_desc = self.RE_WS.sub('', puzzle_desc)
        left, right = self.RE_EQN.search(puzzle_desc).groups()
        variables = defaultdict(int)
        terms = self.RE_TERMS.findall('+' + left)

        for op, term in terms:
            fac = 10**(len(term) - 1)
            if op == '-':
                fac = -fac

            for c in term:
                variables[c] += fac
                fac //= 10

        fac = 10**(len(right) - 1)
        for c in right:
            variables[c] -= fac
            fac //= 10

        variables = sorted(variables.items(), key=by_coeff, reverse=True)
        self.coeffs = tuple(v for name, v in variables)
        self.names = tuple(name for name, v in variables)
        self.zero_pos = next(i for i, v in enumerate(self.coeffs) if v <= 0)

    def recurse(
        self,
        remain: Tuple[int, ...],
        chosen: Tuple[int, ...],
        total: int=0,
        depth: int=0,
    ) -> Iterable[Tuple[int, ...]]:
        global node_visits
        node_visits += 1

        coeffs = self.coeffs[depth:]
        coeff = coeffs[0]
        n = len(coeffs)

        # We have a certain total that we need to reduce to zero
        # If the current total plus the potential upper and lower bounds does
        # not produce an interval that covers zero, reject this candidate
        #      t+lb  <=    0    <=    t+ub
        #      lb    <=    -t   <=    ub

        if coeff != 0:
            x_needed = -total / coeff

            if n == 1:
                x_int = int(x_needed)
                if 0 <= x_int < 10 and x_needed == x_int:
                    yield chosen + (x_int,)
                return

        remain_asc = sorted(remain)
        zero_pos = self.zero_pos - depth

        if zero_pos > 0:
            upper_x = remain_asc[-1: -zero_pos-1: -1] + remain_asc[n-zero_pos-1:: -1]
        else:
            upper_x = remain_asc[n-1::-1]

        # This is effectively np.dot, but numpy arrays are much slower in this
        # method - possibly due to the number of appends and deletes
        upper = sum(
            x*c for x, c in zip(upper_x, coeffs)
        )
        if -total > upper:
            return

        if zero_pos > 0:
            lower_x = remain_asc[:zero_pos] + remain_asc[zero_pos-n:]
        else:
            lower_x = remain_asc[-n:]

        lower = sum(
            x*c for x, c in zip(lower_x, coeffs)
        )
        if lower > -total:
            return

        # We can sort in order of increasing error from x_needed, but that ends
        # up offering no performance advantage

        for i, x in enumerate(remain):
            yield from self.recurse(
                remain[:i] + remain[i+1:],
                chosen + (x,),
                total + x*coeff,
                depth+1,
            )

    def solve(self) -> Tuple[int, ...]:
        return next(self.recurse(tuple(range(10)), ()))

    def substitute(self, solution: Tuple[int, ...]) -> str:
        res = self.puzzle_desc
        for value, name in zip(solution, self.names):
            res = res.replace(name, str(value))
        return res


def main():
    puzzles = [
        """\
        F O R T Y
        +   T E N
        +   T E N
        =========
        S I X T Y""",

        """\
          S E N D
        + M O R E
        =========
        M O N E Y""",

        """\
              T I L E S
        + P U Z Z L E S
        ===============
          P I C T U R E""",

        """\
          D O U B L E
        + D O U B L E
        +     T O I L
        =============
        T R O U B L E""",

        """\
          T H R E E
        + T H R E E
        +     T W O
        +     T W O
        +     O N E
        ===========
        E L E V E N""",

        """\
        SO+MANY+MORE+MEN+SEEM+TO+SAY+THAT+
        THEY+MAY+SOON+TRY+TO+STAY+AT+HOME+
        SO+AS+TO+SEE+OR+HEAR+THE+SAME+ONE+
        MAN+TRY+TO+MEET+THE+TEAM+ON+THE+
        MOON+AS+HE+HAS+AT+THE+OTHER+TEN
        =TESTS
        """
    ]

    for i, puzzle in enumerate(puzzles):
        for solver in (CryptArithm, CryptRoots):
            global node_visits
            node_visits = 0
            start = perf_counter()
            ca = solver(puzzle)
            solution = ca.solve()
            stop = perf_counter()

            print(f"{i}. {solver.__name__}: {1e3*(stop - start):.1f} ms, {node_visits} nodes")

        print()

On my "nothing-special" laptop this yields

0. CryptArithm: 4.4 ms, 2204 nodes
0. CryptRoots: 508.8 ms, 285762 nodes

1. CryptArithm: 3.0 ms, 356 nodes
1. CryptRoots: 18.7 ms, 12774 nodes

2. CryptArithm: 2.0 ms, 1365 nodes
2. CryptRoots: 32.4 ms, 16883 nodes

3. CryptArithm: 1.1 ms, 153 nodes
3. CryptRoots: 1091.3 ms, 659674 nodes

4. CryptArithm: 4.6 ms, 1870 nodes
4. CryptRoots: 209.4 ms, 122197 nodes

5. CryptArithm: 2719.1 ms, 832613 nodes
5. CryptRoots: 25.4 ms, 13305 nodes

Since I was focusing on performance exploration and not cleanliness, this doesn't validate the input as thoroughly as yours.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Good catch with the self._base. Fair point about the scoped main. I'll have to give some more thought to the early constraint point. Regarding quality of life's seconds & milliseconds, the 3 second case at the end would not benefit from sub-millisecond resolution, but if you've got performance ideas, it would definitely be required for comparison purposes for the other cases; I look forward to seeing them. \$\endgroup\$
    – AJNeufeld
    Dec 26, 2020 at 5:42
  • 1
    \$\begingroup\$ @AJNeufeld Alternate posted. If I figure out some Diophantine fanciness I might have another alternate coming. \$\endgroup\$
    – Reinderien
    Dec 30, 2020 at 21:49
  • 1
    \$\begingroup\$ Interesting alternative, cool! I see you're cheating by finding only the first solution, and not exhaustively checking if there are multiple solutions. If I do that (solution = next(ca.solutions())), my solution times range from 0.6ms (THREE+THREE+TWO+TWO+ONE=ELEVEN and TILES+PUZZLE=PICTURE) to 4.8ms (SEND+MORE=MONEY), with 204.9ms for the last puzzle. Still your solution is eight times faster for the last puzzle and mine is eight times faster for the second last; for a programming contest, the ideal solution would need to choose between the strategies somehow. Interesting problem. \$\endgroup\$
    – AJNeufeld
    Dec 31, 2020 at 17:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.