reset password
Author Message
rabbott
Posts: 1649
Posted 08:03 Oct 16, 2019 |

Here is some code you can use to start your SEND + MORE + MONEY with Power Propagators.

def generate_columns(term1, term2, sum) -> Tuple[List[Tuple[Tuple[str, str, str], Tuple[str, str]]], FrozenSet[str]]:
    """
    Given the words of the problem, generates columns associated with those words.
    For example, generate_columns('SEND', 'MORE', 'MONEY') produces the following list of
    tuples, one for each column. Each tuple is a tuple of variables.

    It also generates carry variables. In this case C0 - C5. C0 is the carry into the
    first column, which is always 0. C5 is the carry out of the final column, which also
    is always 0.  Each entry below is a column. For example,
    (('C3', 'S', 'M'), ('C4', 'O')) corresponds to the leftmost full column: C3 + S + M = 10*C4 + O.

    The number of entries in the first Tuple in each pair is one more than the number of summand words.

    '_' is used for an empty space, e.g., at the left of the summand words.

    [(('C4', '_', '_'), ('C5', 'M')),
     (('C3', 'S', 'M'), ('C4', 'O')),  # -> corresponds to the column: C3 + S + M = 10*C4 + O
     (('C2', 'E', 'O'), ('C3', 'N')),
     (('C1', 'N', 'R'), ('C2', 'E')),
     (('C0', 'D', 'E'), ('C1', 'Y'))]

     Also return the set of problem variables.
    """
    carry_vars: List[str] = [f'C{i}' for i in range(len(sum)+1)]  # = ['C1', 'C2', 'C3', 'C4']
    carry_in = carry_vars[:-1]
    carry_out = carry_vars[1:]
    cols = list(reversed(list(zip(zip_longest(carry_in, list(reversed(term1)), list(reversed(term2)), fillvalue='_'),
                                  zip_longest(carry_out, list(reversed(sum)), fillvalue=' ')))))
    return (cols, frozenset(term1) | frozenset(term2) | frozenset(sum))


def generate_domains(term1, term2, sum) -> (Domains, Domains, Domains):
    """
    Given a list of problem letters, generates domains for them. The domains are
    hard-wired for SEND + MORE = MONEY. All the domains are set(range(10)) - {1}.
    problem_var_domains['M'] = {1} and problem_var_domains['S'] = problem_var_domains['S'] - {0}.

    domains are also generated for the carry variables.
    :return:
    """
    (cols, problem_vars) = generate_columns(term1, term2, sum)  # -> List[Tuple[Tuple[str, str, str], Tuple[str, str]]]

    digits: FrozenSet[int] = frozenset(range(10))
    problem_var_domains: Domains = {var: digits for var in problem_vars}
    # Require that 'M' and 'S' be non-zero.
    problem_var_domains['M'] = problem_var_domains['S'] = digits - {0}

    carry_vars: List[str] = [f'C{i}' for i in range(6)]    # = ['C0', 'C1', 'C2', 'C3', 'C4', 'C5']
    carry_var_domains: Domains = {var: digits for var in carry_vars}
    # 'C0' and 'C5' are artificial carry-in and carry-out digits.
    # 'C0' carries in to the digits column. It is set to 0.
    carry_var_domains['C0'] = frozenset({0})
    # 'C5' carries out of the left-most column. (It needn't be set.)

    # Did not set 'M' or C4 to 1.

    # noinspection PyDictCreation
    combined_domains: Domains = {**problem_var_domains, **carry_var_domains}

    # '_' is an artificial anonymous variable set to 0 to fill-out 'SEND' and 'MORE' to '_SEND' and '_MORE'
    combined_domains['_'] = frozenset({0})
    return (cols, problem_var_domains, combined_domains)


def run_send_more_money(problem, all_domains, problem_vars, cols):
    # FrozenSet assignment_limit to 0 to turn off tracing. A positive number indicates
    # the number of assignment_count to allow (and to display) before quitting.
    assignment_limit = 0

    # Create the CSP object and set up the problem.
    csp: CSP[str, int] = CSP(problem_vars, set(all_domains), cols, assignment_limit)
    (solution, reduced_domains) = csp.complete_the_assignment(all_domains)
    assignment_count = csp.assignment_count if not csp.assignment_limit else \
                       min(csp.assignment_count, csp.assignment_limit)
    display_result(*problem,      #  ['SEND', 'MORE', 'MONEY']
                   solution if not solution else domains_to_assignment(reduced_domains, problem_vars),
                   reduced_domains,
                   assignment_count)


# col nbr:     4  3  2  1  0  <- col_5 is never created, but C5, it's carry-in bit is created with col_4.
#          C5 C4 C3 C2 C1 C0  <- These are carry variables. C0 and C5 are set to 0.
#              _  S  E  N  D  <- '_' is an anonymous variables, set to 0.
#              _  M  O  R  E  :: These extra variables, C0, C5, and '_' make it possible for columns
#          -----------------  :: all to have the same structure.
#              M  O  N  E  Y
#


def domains_to_assignment(domains, problem_vars) -> Dict[V, D]:
    assignment = {v: list(domains[v])[0] for v in domains if v in problem_vars and len(domains[v]) == 1}
    return assignment


if __name__ == "__main__":
    problem = ['SEND', 'MORE', 'MONEY']
    (cols, problem_var_domains, all_domains) = generate_domains(*problem)
    cols = list(reversed(cols))

    # compute problem_vars, a list of letters ordered by frequency, with ties broken alphabetically.
    all_letters = ''.join(problem)
    problem_vars = sorted(set(all_letters), key=lambda x: all_letters.count(x), reverse=True)

    combined_domains = {**{v: all_domains[v] for v in problem_vars}, **all_domains}

    print(f'\nProblem: {problem}\nProblem vars (in order of frequency): {problem_vars}\nColumns:')
    for col_nbr in range(5):
        print(f'{4-col_nbr}. {cols[4-col_nbr]}')
    print(f'\nInitial domains: {domains_by_size(all_domains)}\n')
    assignment = domains_to_assignment(all_domains, set(combined_domains))
    unassigned_variables = [v for v in all_domains if len(all_domains[v]) > 1]
    print(f'Initial state:\nassigned: {assignment};\nunassigned: {unassigned_variables}')

    run_send_more_money(problem, combined_domains, problem_vars, cols)

 

And here is some output to strive for.

 

Problem: ['SEND', 'MORE', 'MONEY']
Problem vars (in order of frequency): ['E', 'M', 'N', 'O', 'D', 'Y', 'S', 'R']
Columns:
4. (('C4', '_', '_'), ('C5', 'M'))
3. (('C3', 'S', 'M'), ('C4', 'O'))
2. (('C2', 'E', 'O'), ('C3', 'N'))
1. (('C1', 'N', 'R'), ('C2', 'E'))
0. (('C0', 'D', 'E'), ('C1', 'Y'))

Initial domains: {'C0': frozenset({0}), '_': frozenset({0}), 'M': frozenset({1, 2, 3, 4, 5, 6, 7, 8, 9}), 'S': frozenset({1, 2, 3, 4, 5, 6, 7, 8, 9}), 'D': frozenset({0, 1, 2, 3, 4, 5, 6, 7, 8, 9}), 'Y': frozenset({0, 1, 2, 3, 4, 5, 6, 7, 8, 9}), 'R': frozenset({0, 1, 2, 3, 4, 5, 6, 7, 8, 9}), 'N': frozenset({0, 1, 2, 3, 4, 5, 6, 7, 8, 9}), 'O': frozenset({0, 1, 2, 3, 4, 5, 6, 7, 8, 9}), 'E': frozenset({0, 1, 2, 3, 4, 5, 6, 7, 8, 9}), 'C1': frozenset({0, 1, 2, 3, 4, 5, 6, 7, 8, 9}), 'C2': frozenset({0, 1, 2, 3, 4, 5, 6, 7, 8, 9}), 'C3': frozenset({0, 1, 2, 3, 4, 5, 6, 7, 8, 9}), 'C4': frozenset({0, 1, 2, 3, 4, 5, 6, 7, 8, 9}), 'C5': frozenset({0, 1, 2, 3, 4, 5, 6, 7, 8, 9})}

Initial state:
assigned: {'C0': 0, '_': 0};
unassigned: ['M', 'D', 'Y', 'S', 'R', 'N', 'O', 'E', 'C1', 'C2', 'C3', 'C4', 'C5']

State after initial propagation
assigned: {'M': 1, 'O': 0, 'S': 9, 'C0': 0, 'C3': 0, 'C4': 1, 'C5': 0, '_': 0};
unassigned: ['E', 'N', 'D', 'Y', 'R', 'C1', 'C2']

Propagation after setting E = 5
assigned: {'E': 5, 'M': 1, 'N': 6, 'O': 0, 'D': 7, 'Y': 2, 'S': 9, 'R': 8, 'C0': 0, 'C1': 1, 'C2': 1, 'C3': 0, 'C4': 1, 'C5': 0, '_': 0};
unassigned: []

  SEND ->  9567
+ MORE ->  1085
------    -----
 MONEY -> 10652

{'E': 5, 'M': 1, 'N': 6, 'O': 0, 'D': 7, 'Y': 2, 'S': 9, 'R': 8}

Solution found after 4 assignments!

Process finished with exit code 0
 

Last edited by rabbott at 08:14 Oct 16, 2019.