Lab #5: Cryptarithmetic with CSP

Description

This activity must be developed in the pre-assigned teams of two.

Using the updated csp (constraint-satisfaction problem) module developed and descriped in chapter 3 of [KOPEC], write a Python script called cryptarithmetic_puzzle.py that solves cryptarithmetic puzzles involving addition of two or more addends. It is highly recommended that you reread this chapter of the book to make sure you have an adequate understanding of the algorithm being used.

Cryptarithmetic

As defined in Wikipedia:

Cryptarithmetic is a type of mathematical game consisting of a mathematical equation among unknown numbers, whose digits are represented by letters of the alphabet. The goal is to identify the value of each letter. The equation is typically a basic arithmetic operation, such as addition.

Example:

       I
   L U V
+      U
―――――――――
   Y E S

A solution to the above puzzle would be:

• E = 0
• I = 2
• L = 3
• S = 6
• U = 9
• V = 5
• Y = 4

And we can verify it:

       2
   3 9 5
+      9
―――――――――
   4 0 6

Implementation Details

In your cryptarithmetic_puzzle.py script, write a function called solve_cryptarithmetic_puzzle that takes two inputs: a list of strings with the equation addends and a string with the equation answer. Use the following code as a starting point:

from csp import Constraint, CSP


def solve_cryptarithmetic_puzzle(
        addends: list[str],
        answer: str) -> Optional[dict[str, int]]:
    # The rest of the function's code goes here
    ...


# The rest of the module's code goes here
...

If the function finds a solution it should return a dictionary where the keys are the uppercase letters contained in the strings from addends and answer, while the corresponding values are the digits from 0 to 9. The function should return None if no solution was found.

So, for example, the following code:

solve_cryptarithmetic_puzzle(['i', 'luv', 'u'], 'yes'))

should return:

{'E': 0, 'I': 2, 'L': 3, 'S': 6, 'U': 9, 'V': 5, 'Y': 4}

NOTE #1: Your function will need to create an instance of the CSP class from the csp module. When doing so, you’ll need to define at some point the variables, domains, and constraints for this problem. It is importante that the variables are specified as a list of strings containing only uppercase letters sorted in ascending order. If you do not follow this indication your code might have some issues with the unit tests (it may take longer to run or some tests might fail even if a technically correct solution is produced).

NOTE #2: Contrary to what [KOPEC] indicates, your solution code should allow the first letter of answer to be zero. Take this into account, otherwise some of the unit tests will most definitely fail.

Test your code using the tests in the file test_cryptarithmetic_puzzle.py. Finally, make sure no type or PEP 8 style errors are produced by using the mypy and pycodestyle linters. You can run them at the terminal like this:

mypy cryptarithmetic_puzzle.py

pycodestyle cryptarithmetic_puzzle.py

Deliverables

Place in a comment at the top of the cryptarithmetic_puzzle.py source file the authors’ personal information (student ID and name), for example:

#----------------------------------------------------------
# Lab #5: Cryptarithmetic with CSP
# General cryptarithmetic puzzle solver.
#
# Date: 13-Oct-2023
# Authors:
#           A01770771 Kamala Khan
#           A01777771 Carol Danvers
#----------------------------------------------------------

Only one team member needs to upload the file.

Due date is Friday, October 13.