Previously, I posted an experiment in solving cryptarithms with Python and MiniZinc. I've just put an improved version on GitHub, since I figured out how to generalize the problem somewhat--Python now just converts your problem into a dictionary and feeds that to an existing script that doesn't have to change. This new model still has some rough edges--artifacts of the learning process--but it works well enough.
Cryptarithms with MiniZinc, Python, and pymzn
A couple of entries in the AMS Page a Day Calendar so far have been cryptarithms. I most recently encountered these in the Coursera course on ("Basic Modeling for Discrete Optimization")](https://www.coursera.org/learn/basic-modeling), which uses them as an early example to teach MiniZinc. It's fairly easy to adapt existing code to solve this problem:
ZEROES + ONES = BINARY:
%From the AMS page-a-day calendar
var 0..9: Z;
var 0..9: E;
var 0..9: R;
var 0..9: O;
var 0..9: S;
var 0..9: N;
var 0..9: B;
var 0..9: I;
var 0..9: A;
var 0..9: Y;
constraint Z != 0;
constraint O != 0;
constraint B != 0;
constraint
100000 * Z + 10000 * E + 1000 * R + 100 * O + 10 * E + S
+ 1000 * O + 100 * N + 10 * E + S
= 100000 * B + 10000 * I + 1000 * N + 100 * A + 10 * R + Y;
include "alldifferent.mzn";
constraint alldifferent([Z,E,R,O,S,N,B,I,A,Y]);
%solve maximize (10000 * V + 1000 * E + 100 * R + 10 * S + E);
It's probably fairly easy to make a MiniZinc script that reads the problem from a data file instead of having it hardcoded, but I'm not that good with MiniZinc (I haven't finished the course). But this does seem like a good excuse to tinker with pymzn
, a Python interface to MiniZinc. Here's my Python script to build a MiniZinc cryptarithm-solver script, run it, and return the results:
import io
import json
import re
import pymzn
def cryptarithm(problem):
mznscript = io.StringIO('')
prob = problem.replace(' ', '')
(facs, solution) = prob.split('=')
facs = facs.split('+')
#Set of all unique letters in the problem
letters = set(re.sub('[+=\s]', '', prob))
#All letters at the beginning of a "number"
initials = set([fac[0] for fac in facs]+[solution[0]])
#declare all variables.
#First letters != 0.
print(*[f'var 1..9: {l};' for l in initials], sep="\n", file=mznscript)
print(*[f'var 0..9: {l};' for l in letters.difference(initials)], sep="\n", end="\n\n", file=mznscript)
#Each letter stands for a different number.
print('include "alldifferent.mzn";', file=mznscript)
print(f'constraint alldifferent([{",".join(letters)}]);', file=mznscript)
#Add the main constraint.
print('\nconstraint', file=mznscript)
#This is ugly. Don't do this in actually-useful code.
print(' '+'\n + '.join([' + '.join(f'{10**n} * {l}' for n,l in enumerate(reversed(tuple(fac)))) for fac in facs]), file=mznscript)
print(' = '+' + '.join([f'{10**n} * {l}' for n,l in enumerate(reversed(tuple(solution)))])+';', end="\n\n", file=mznscript)
print('solve satisfy;', file=mznscript)
mznscript.seek(0)
script = mznscript.read()
return (script, [dict(sorted(json.loads(sol).items(), key=lambda x: problem.index(x[0])))
for sol
in pymzn.minizinc(script, output_mode='json')])
And some use examples:
>>> script, solutions = cryptarithm('ZEROES + ONES = BINARY')
>>> print(solutions)
[{'Z': 6, 'E': 9, 'R': 8, 'O': 3, 'S': 2, 'N': 1, 'B': 7, 'I': 0, 'A': 5, 'Y': 4}]
>>> script, solutions = cryptarithm('SEND+MORE=MONEY')
>>> print(solutions)
[{'S': 9, 'E': 5, 'N': 6, 'D': 7, 'M': 1, 'O': 0, 'R': 8, 'Y': 2}]
>>> script, solutions = cryptarithm('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')
>>> print(solutions)
[{'T': 9, 'A': 7, 'O': 1, 'M': 2, 'H': 5, 'S': 3, 'E': 0, 'N': 6, 'Y': 4, 'R': 8}]
>>> script, solution = cryptarithm('TWO + TWO = FOUR')
>>> print(solution)
[{'F': 1, 'T': 7, 'W': 3, 'R': 8, 'U': 6, 'O': 4}]
About Me
Developer at Brown University Library specializing in instructional design and technology, Python-based data science, and XML-driven web development.
Tags
- #100daystooffload (7)
- Gemini (1)
- PowerShell (1)
- adtech (3)
- advertising (3)
- advertising_industry (3)
- aerospace (1)
- agriculture (5)
- airlines (1)
- american_football (1)
- animals (4)
- art (6)
- artificial_intelligence (18)
- augmented_reality (1)
- automotive (2)
- aviation_ (3)
- beverage_industry (1)
- big_data (2)
- biopharma_industry (20)
- blockchain (3)
- books (2)
- business (27)
- cannabis (3)
- chemistry (11)
- cinema (6)
- climate (12)
- cloud_computing (1)
- code (0)
- commodities (1)
- consumer_insights (7)
- crime (11)
- cryptarithms (1)
- crypto (1)
- cryptography (4)
- cxo_mentions (1)
- cyber_fraud (1)
- cyber_security (4)
- cycling (1)
- data_breach (1)
- data_science (18)
- deep_learning (6)
- devops (1)
- digital_transformation (1)
- diversity (16)
- diversity_inclusion (1)
- ecommerce (3)
- economy (28)
- education (57)
- electronics (6)
- energy (4)
- energy_industry (2)
- entertainment (1)
- entrepreneurship (1)
- executive_mentions (3)
- finance (2)
- finance_industry (3)
- fintech (2)
- foreign_policy (22)
- future_of_work (1)
- games (11)
- gaming_industry (1)
- gardening (2)
- geography (1)
- geopolitics (9)
- global_health (7)
- gopher (1)
- government_oppression (1)
- guns (3)
- hacking (5)
- health (11)
- healthcare_it (3)
- immigration (2)
- insurance (7)
- insurtech (1)
- interviews (1)
- investing (12)
- law (18)
- legal_industry (2)
- legal_tech (4)
- libraries (2)
- lifestyle (2)
- links (91)
- listicles (2)
- machine_learning (7)
- maps (1)
- market_reports (1)
- market_research (1)
- mathematics (3)
- media_entertainment_industry (4)
- medical_devices_industry (2)
- military (11)
- minizinc (2)
- mobile_security (1)
- music (3)
- natural_language_processing (1)
- navy (3)
- neuroscience (13)
- nlp (4)
- parenting (4)
- personal_finance (4)
- pharma (15)
- political_science (37)
- politics (34)
- privacy (1)
- product_review (1)
- programming (4)
- python (8)
- quotes (1)
- real_estate (5)
- real_estate_industry (1)
- reality (1)
- recreational_drugs (3)
- retail (4)
- retail_industry (2)
- robotics (1)
- semiconductor (1)
- sleep (1)
- smart_cities (1)
- soccer (2)
- space (2)
- sport (1)
- stocks (3)
- supply_chain (1)
- supply_chain_industry (1)
- sustainability (2)
- sustainable_development (3)
- systems (4)
- tech (26)
- tech_scientific_innovation (1)
- technology (1)
- telecom_industry (1)
- video_games (3)
- visualization (2)
- weather (5)