{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Peter Norvig
2014, 2020
\n",
"\n",
"# Cryptarithmetic Problems\n",
"\n",
"On 28 April 2014 Gary Antonik had a [Numberplay column](https://web.archive.org/web/20191001030614/https://wordplay.blogs.nytimes.com/2014/04/28/num/) in which my friend [Bill Gosper](https://en.wikipedia.org/wiki/Bill_Gosper) poses this puzzle:\n",
"\n",
"
\n",
"\n",
"**For the expression N U M + B E R = P L A Y**,\n",
"- **Which distinct numerals (each different) can be substituted for letters to make a valid expression?**\n",
"- **How many solutions are there?**\n",
"
\n",
"\n",
"I [tackled](https://www.udacity.com/wiki/cs212/unit-2#rethinking-eval) this type of problem (also known as a [cryptarithmetic](http://mathworld.wolfram.com/Cryptarithmetic.html) or [alphametic](http://mathworld.wolfram.com/Alphametic.html) or [verbal arithmetic](https://en.wikipedia.org/wiki/Verbal_arithmetic) problem) in my Udacity class [CS 212](https://www.udacity.com/wiki/cs212/unit-2#cryptarithmetic). \n",
"\n",
"\n",
"\n",
"My initial approach follows Ken Thompson's adage, \"when in doubt, use brute force\":\n",
"\n",
"- There are only 10 factorial (3.6 million) permutations of 10 digits, so we can try them all.\n",
"- For each permutation, substitute the digits for the corresponding letters in the formula.\n",
"- Use Python's `eval` function to check if the resulting formula is a valid, true expression. \n",
"- Report the expressions that are.\n",
"\n",
"The basic idea is simple, but there are a few complications:\n",
"\n",
"- Python uses `==` for equality and `**` for exponentiation, but math notation uses `=` and `^`. I'll define `to_python` to handle this.\n",
"- A number with a leading zero digit (like `012`) is illegal (except that `0` by itself is ok).\n",
"- We'll have to catch divide-by-zero errors, as in `4/(3-2-1)`.\n",
"- In general, it is **unsafe** to eval a string that comes from a user, because a malicious user could inject malware. But eval-ing strings that we make ourselves is no worse than running code that we make ourselves. \n",
"- Should I define a `solve` function to find one solution (faster) or all solutions (comprehensive)? I'll handle both use cases by defining `solve` to yield solutions one at a time. You can quickly get the first one with `first` or all of them with `set`. \n",
"\n",
"# Defining `solve`\n",
"\n",
"First some imports and type definitions:"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"from typing import Iterable, Callable\n",
"from itertools import permutations\n",
"from collections import Counter\n",
"import re\n",
"\n",
"Formula = str # A formula in Math notation, like \"NUM + BER = PLAY\"\n",
"Solution = str # A formula with letters relaced by digits, like \"356 + 742 = 1098\""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Below we see that `solve` works by substituting each permutation of digits for the letters in the formula, and then reporting on the ones that are valid. "
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"def solve(formula) -> Iterable[Solution]:\n",
" \"\"\"Given a formula like 'NUM + BER == PLAY', fill in digits to solve it.\"\"\"\n",
" letters = all_letters(formula)\n",
" pyformula = to_python(formula)\n",
" for digits in permutations('1234567890', len(letters)):\n",
" if valid(subst(digits, letters, pyformula)):\n",
" yield subst(digits, letters, formula)\n",
" \n",
"def subst(digits: str, letters: str, formula: Formula) -> Formula:\n",
" \"\"\"Substitute digits for letters in formula.\"\"\"\n",
" return formula.translate(str.maketrans(letters, cat(digits)))\n",
" \n",
"def valid(pyformula: Formula) -> bool:\n",
" \"\"\"A pyformula is valid iff it has no leading zero, and evaluates to True.\"\"\"\n",
" try:\n",
" return (not leading_zero(pyformula)) and (eval(pyformula) is True)\n",
" except ArithmeticError:\n",
" return False\n",
" \n",
"def to_python(formula: Formula) -> Formula:\n",
" \"\"\"Convert ' = ' and '^' to ' == ' and '**'.\"\"\"\n",
" return formula.replace(' = ', ' == ').replace('^', '**') \n",
"\n",
"def all_letters(formula: Formula) -> str: \n",
" \"\"\"The set of letters in formula, in the order they first appear.\"\"\"\n",
" return cat(Counter(re.findall('[A-Z]', formula)))\n",
"\n",
"def first(iterable): \"First element\"; return next(iter(iterable), None)\n",
" \n",
"cat = ''.join # Function to concatenate strings\n",
" \n",
"leading_zero = re.compile(r'\\b0[0-9]').search # Function to check for illegal number"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can go right ahead and solve the problem:"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"collapsed": false,
"jupyter": {
"outputs_hidden": false
}
},
"outputs": [
{
"data": {
"text/plain": [
"'246 + 789 = 1035'"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"first(solve('NUM + BER = PLAY'))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"That's one solution; how many are there all together? And how long does it take to find them?"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"collapsed": false,
"jupyter": {
"outputs_hidden": false
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"CPU times: user 11.1 s, sys: 14 ms, total: 11.1 s\n",
"Wall time: 11.1 s\n"
]
},
{
"data": {
"text/plain": [
"96"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"%time solutions = list(solve('NUM + BER = PLAY'))\n",
"len(solutions)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"It takes about 11 seconds to find 96 solutions, Here are ten of them:"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"['246 + 789 = 1035',\n",
" '249 + 786 = 1035',\n",
" '264 + 789 = 1053',\n",
" '269 + 784 = 1053',\n",
" '284 + 769 = 1053',\n",
" '286 + 749 = 1035',\n",
" '289 + 746 = 1035',\n",
" '289 + 764 = 1053',\n",
" '324 + 765 = 1089',\n",
" '325 + 764 = 1089']"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"solutions[:10]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Defining `faster_solve`\n",
"\n",
"Can we make `solve` faster? \n",
"\n",
"To answer the question, I start by profiling to see where the time is spent, using the ipython magic function `%prun`:"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"collapsed": false,
"jupyter": {
"outputs_hidden": false
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" "
]
},
{
"data": {
"text/plain": [
" 3127170 function calls (3127152 primitive calls) in 2.079 seconds\n",
"\n",
" Ordered by: internal time\n",
"\n",
" ncalls tottime percall cumtime percall filename:lineno(function)\n",
" 355667 1.382 0.000 1.411 0.000 {built-in method builtins.eval}\n",
" 461238 0.155 0.000 0.155 0.000 {method 'translate' of 'str' objects}\n",
" 461238 0.128 0.000 0.413 0.000 1816288747.py:9(subst)\n",
" 461237 0.104 0.000 0.104 0.000 {method 'search' of 're.Pattern' objects}\n",
" 461238 0.092 0.000 0.092 0.000 {built-in method maketrans}\n",
" 461237 0.074 0.000 1.589 0.000 1816288747.py:13(valid)\n",
" 1 0.068 0.068 1.383 1.383 1816288747.py:1(solve)\n",
" 461239 0.037 0.000 0.037 0.000 {method 'join' of 'str' objects}\n",
" 9/1 0.024 0.003 1.905 1.905 {built-in method builtins.next}\n",
" 2/0 0.005 0.003 0.000 base_events.py:1954(_run_once)\n",
" 1 0.002 0.002 0.043 0.043 socket.py:700(send_multipart)\n",
" 1 0.002 0.002 0.020 0.020 history.py:92(only_when_enabled)\n",
" 354 0.001 0.000 0.002 0.000 ipkernel.py:775(_clean_thread_parent_frames)\n",
" 1 0.001 0.001 0.013 0.013 history.py:1024(writeout_cache)\n",
" 11 0.001 0.000 0.012 0.001 socket.py:623(send)\n",
" 177 0.000 0.000 0.001 0.000 threading.py:1477(enumerate)\n",
" 1416 0.000 0.000 0.000 0.000 threading.py:1110(ident)\n",
" 3 0.000 0.000 0.050 0.017 events.py:87(_run)\n",
" 708 0.000 0.000 0.000 0.000 {method 'keys' of 'dict' objects}\n",
" 3 0.000 0.000 0.000 0.000 attrsettr.py:66(_get_attr_opt)\n",
" 1 0.000 0.000 0.043 0.043 zmqstream.py:573(_handle_events)\n",
" 460/456 0.000 0.000 0.000 0.000 {built-in method builtins.isinstance}\n",
" 354 0.000 0.000 0.000 0.000 {method 'values' of 'dict' objects}\n",
" 2/0 0.000 0.000 0.000 {method 'control' of 'select.kqueue' objects}\n",
" 1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}\n",
" 179 0.000 0.000 0.000 0.000 {method '__exit__' of '_thread.RLock' objects}\n",
" 1 0.000 0.000 0.000 0.000 {method 'execute' of 'sqlite3.Connection' objects}\n",
" 11 0.000 0.000 0.000 0.000 enum.py:1594(__or__)\n",
" 2 0.000 0.000 0.000 0.000 {method '__exit__' of 'sqlite3.Connection' objects}\n",
" 48 0.000 0.000 0.000 0.000 enum.py:1587(_get_value)\n",
" 1 0.000 0.000 0.000 0.000 {built-in method time.sleep}\n",
" 20 0.000 0.000 0.000 0.000 enum.py:695(__call__)\n",
" 3 0.000 0.000 0.000 0.000 attrsettr.py:43(__getattr__)\n",
" 1 0.000 0.000 0.000 0.000 {method 'send' of '_socket.socket' objects}\n",
" 20 0.000 0.000 0.000 0.000 enum.py:1154(__new__)\n",
" 1 0.000 0.000 0.000 0.000 iostream.py:616(_flush)\n",
" 5 0.000 0.000 0.000 0.000 enum.py:1605(__and__)\n",
" 1 0.000 0.000 0.000 0.000 inspect.py:3122(_bind)\n",
" 2 0.000 0.000 0.000 0.000 base_events.py:846(_call_soon)\n",
" 1 0.000 0.000 2.019 2.019 1816288747.py:28(first)\n",
" 2 0.000 0.000 0.043 0.022 ioloop.py:742(_run_callback)\n",
" 2 0.000 0.000 0.000 0.000 zmqstream.py:653(_rebuild_io_state)\n",
" 1 0.000 0.000 0.000 0.000 socket.py:771(recv_multipart)\n",
" 3 0.000 0.000 0.043 0.014 {method 'run' of '_contextvars.Context' objects}\n",
" 2 0.000 0.000 0.000 0.000 zmqstream.py:676(_update_handler)\n",
" 2 0.000 0.000 0.000 0.000 traitlets.py:3631(set)\n",
" 2 0.000 0.000 0.000 0.000 traitlets.py:718(_validate)\n",
" 1 0.000 0.000 0.000 0.000 traitlets.py:1527(_notify_observers)\n",
" 1 0.000 0.000 0.000 0.000 asyncio.py:225(add_callback)\n",
" 2 0.000 0.000 0.000 0.000 typing.py:1665(__subclasscheck__)\n",
" 1 0.000 0.000 0.043 0.043 zmqstream.py:546(_run_callback)\n",
" 5 0.000 0.000 0.000 0.000 base_events.py:766(time)\n",
" 3 0.000 0.000 0.000 0.000 typing.py:426(inner)\n",
" 1 0.000 0.000 0.000 0.000 kernelbase.py:302(poll_control_queue)\n",
" 2/0 0.000 0.000 0.000 selectors.py:540(select)\n",
" 2 0.000 0.000 0.000 0.000 traitlets.py:3474(validate)\n",
" 1 0.000 0.000 0.000 0.000 inspect.py:3264(bind)\n",
" 1 0.000 0.000 0.000 0.000 decorator.py:200(fix)\n",
" 1 0.000 0.000 0.000 0.000 queues.py:225(get)\n",
" 2 0.000 0.000 0.000 0.000 queue.py:115(empty)\n",
" 1 0.000 0.000 0.000 0.000 _base.py:537(set_result)\n",
" 8 0.000 0.000 0.000 0.000 {built-in method builtins.hasattr}\n",
" 4 0.000 0.000 0.000 0.000 {built-in method builtins.getattr}\n",
" 4 0.000 0.000 0.000 0.000 traitlets.py:676(__get__)\n",
" 2 0.000 0.000 0.000 0.000 traitlets.py:689(set)\n",
" 1 0.000 0.000 0.043 0.043 zmqstream.py:614(_handle_recv)\n",
" 1 0.000 0.000 0.000 0.000 iostream.py:710(_flush_buffers)\n",
" 3 0.000 0.000 0.000 0.000 :1390(_handle_fromlist)\n",
" 15 0.000 0.000 0.000 0.000 {built-in method builtins.len}\n",
" 1 0.000 0.000 0.000 0.000 threading.py:315(_acquire_restore)\n",
" 1 0.000 0.000 0.000 0.000 traitlets.py:1512(_notify_trait)\n",
" 2 0.000 0.000 0.000 0.000 traitlets.py:3624(validate_elements)\n",
" 1 0.000 0.000 0.000 0.000 inspect.py:2936(apply_defaults)\n",
" 1 0.000 0.000 0.043 0.043 iostream.py:278(_really_send)\n",
" 2 0.000 0.000 0.000 0.000 typing.py:1374(__instancecheck__)\n",
" 1 0.000 0.000 0.020 0.020 decorator.py:232(fun)\n",
" 2 0.000 0.000 0.000 0.000 traitlets.py:727(_cross_validate)\n",
" 1 0.000 0.000 0.000 0.000 __init__.py:270(findall)\n",
" 2 0.000 0.000 0.000 0.000 traitlets.py:708(__set__)\n",
" 1 0.000 0.000 0.043 0.043 iostream.py:276()\n",
" 1 0.000 0.000 0.000 0.000 1816288747.py:24(all_letters)\n",
" 1 0.000 0.000 0.000 0.000 __init__.py:599(__init__)\n",
" 1 0.000 0.000 0.000 0.000 contextlib.py:108(__init__)\n",
" 2 0.000 0.000 0.000 0.000 events.py:36(__init__)\n",
" 2 0.000 0.000 0.000 0.000 {built-in method builtins.issubclass}\n",
" 1 0.000 0.000 0.000 0.000 futures.py:391(_call_set_state)\n",
" 2 0.000 0.000 0.000 0.000 {built-in method _abc._abc_subclasscheck}\n",
" 1 0.000 0.000 0.000 0.000 queues.py:256(get_nowait)\n",
" 1 0.000 0.000 0.000 0.000 traitlets.py:1523(notify_change)\n",
" 2 0.000 0.000 0.000 0.000 typing.py:1443(__hash__)\n",
" 2 0.000 0.000 0.000 0.000 traitlets.py:2304(validate)\n",
" 2 0.000 0.000 0.000 0.000 {built-in method posix.getppid}\n",
" 4 0.000 0.000 0.000 0.000 traitlets.py:629(get)\n",
" 2 0.000 0.000 0.000 0.000 :121(__subclasscheck__)\n",
" 1 0.000 0.000 0.000 0.000 __init__.py:330(_compile)\n",
" 1 0.000 0.000 0.000 0.000 base_events.py:870(call_soon_threadsafe)\n",
" 3 0.000 0.000 0.000 0.000 threading.py:306(__exit__)\n",
" 1 0.000 0.000 0.000 0.000 inspect.py:2883(args)\n",
" 3 0.000 0.000 0.000 0.000 threading.py:303(__enter__)\n",
" 1 0.000 0.000 0.000 0.000 iostream.py:718(_rotate_buffers)\n",
" 2 0.000 0.000 0.000 0.000 zmqstream.py:532(sending)\n",
" 5 0.000 0.000 0.000 0.000 {method 'append' of 'collections.deque' objects}\n",
" 1 0.000 0.000 0.000 0.000 contextlib.py:145(__exit__)\n",
" 1 0.000 0.000 0.043 0.043 zmqstream.py:684()\n",
" 1 0.000 0.000 0.000 0.000 threading.py:428(notify_all)\n",
" 1 0.000 0.000 0.000 0.000 {built-in method _heapq.heappop}\n",
" 1 0.000 0.000 0.000 0.000 history.py:1016(_writeout_output_cache)\n",
" 1 0.000 0.000 0.000 0.000 iostream.py:213(_is_master_process)\n",
" 5 0.000 0.000 0.000 0.000 {built-in method time.monotonic}\n",
" 1 0.000 0.000 0.000 0.000 selector_events.py:141(_write_to_self)\n",
" 1 0.000 0.000 0.000 0.000 contextlib.py:303(helper)\n",
" 1 0.000 0.000 0.000 0.000 history.py:1008(_writeout_input_cache)\n",
" 1 0.000 0.000 0.000 0.000 {method 'findall' of 're.Pattern' objects}\n",
" 1 0.000 0.000 0.043 0.043 iostream.py:157(_handle_event)\n",
" 1 0.000 0.000 0.000 0.000 __init__.py:673(update)\n",
" 2 0.000 0.000 0.000 0.000 queue.py:267(_qsize)\n",
" 19 0.000 0.000 0.000 0.000 typing.py:2371(cast)\n",
" 6 0.000 0.000 0.000 0.000 {method '__exit__' of '_thread.lock' objects}\n",
" 1 0.000 0.000 0.000 0.000 base_events.py:817(call_soon)\n",
" 1 0.000 0.000 0.000 0.000 _base.py:337(_invoke_callbacks)\n",
" 1 0.000 0.000 0.000 0.000 {built-in method _collections._count_elements}\n",
" 4 0.000 0.000 0.000 0.000 {method 'popleft' of 'collections.deque' objects}\n",
" 3 0.000 0.000 0.000 0.000 {method 'acquire' of '_thread.lock' objects}\n",
" 2 0.000 0.000 0.000 0.000 traitlets.py:3486(validate_elements)\n",
" 3 0.000 0.000 0.000 0.000 {built-in method builtins.max}\n",
" 3 0.000 0.000 0.000 0.000 selector_events.py:740(_process_events)\n",
" 1 0.000 0.000 0.000 0.000 threading.py:631(clear)\n",
" 1 0.000 0.000 0.000 0.000 inspect.py:2906(kwargs)\n",
" 1 0.000 0.000 0.000 0.000 threading.py:312(_release_save)\n",
" 4 0.000 0.000 0.000 0.000 {method 'get' of 'dict' objects}\n",
" 2 0.000 0.000 0.000 0.000 history.py:1065(hold)\n",
" 1 0.000 0.000 0.000 0.000 :117(__instancecheck__)\n",
" 2 0.000 0.000 0.000 0.000 {built-in method _contextvars.copy_context}\n",
" 1 0.000 0.000 0.000 0.000 threading.py:398(notify)\n",
" 1 0.000 0.000 0.000 0.000 {method 'values' of 'mappingproxy' objects}\n",
" 2 0.000 0.000 0.000 0.000 {method 'extend' of 'list' objects}\n",
" 1 0.000 0.000 0.000 0.000 contextlib.py:136(__enter__)\n",
" 10 0.000 0.000 0.000 0.000 inspect.py:2793(kind)\n",
" 3 0.000 0.000 0.000 0.000 {built-in method builtins.iter}\n",
" 1 0.000 0.000 0.000 0.000 1816288747.py:20(to_python)\n",
" 3 0.000 0.000 0.000 0.000 zmqstream.py:528(receiving)\n",
" 1 0.000 0.000 0.000 0.000 iostream.py:216(_check_mp_mode)\n",
" 4 0.000 0.000 0.000 0.000 {method 'append' of 'list' objects}\n",
" 3 0.000 0.000 0.000 0.000 {method 'upper' of 'str' objects}\n",
" 3 0.000 0.000 0.000 0.000 {method 'items' of 'mappingproxy' objects}\n",
" 1 0.000 0.000 0.000 0.000 {built-in method _abc._abc_instancecheck}\n",
" 2 0.000 0.000 0.000 0.000 {method 'replace' of 'str' objects}\n",
" 1 0.000 0.000 0.000 0.000 {method '__enter__' of '_thread.RLock' objects}\n",
" 2 0.000 0.000 0.000 0.000 {method '__enter__' of '_thread.lock' objects}\n",
" 1 0.000 0.000 0.000 0.000 queues.py:173(qsize)\n",
" 4 0.000 0.000 0.000 0.000 inspect.py:2781(name)\n",
" 2 0.000 0.000 0.000 0.000 {built-in method builtins.hash}\n",
" 2 0.000 0.000 0.000 0.000 base_events.py:548(_check_closed)\n",
" 1 0.000 0.000 0.000 0.000 threading.py:318(_is_owned)\n",
" 1 0.000 0.000 0.000 0.000 {method 'items' of 'dict' objects}\n",
" 1 0.000 0.000 0.000 0.000 queues.py:322(_consume_expired)\n",
" 3 0.000 0.000 0.000 0.000 base_events.py:2052(get_debug)\n",
" 1 0.000 0.000 0.000 0.000 {built-in method _asyncio.get_running_loop}\n",
" 4 0.000 0.000 0.000 0.000 inspect.py:3076(parameters)\n",
" 1 0.000 0.000 0.000 0.000 {built-in method posix.getpid}\n",
" 1 0.000 0.000 0.000 0.000 :1()\n",
" 1 0.000 0.000 0.000 0.000 {method 'cancelled' of '_asyncio.Future' objects}\n",
" 1 0.000 0.000 0.000 0.000 inspect.py:2875(__init__)\n",
" 1 0.000 0.000 0.000 0.000 {built-in method _thread.allocate_lock}\n",
" 1 0.000 0.000 0.000 0.000 {method 'release' of '_thread.lock' objects}\n",
" 1 0.000 0.000 0.000 0.000 {method '_is_owned' of '_thread.RLock' objects}\n",
" 1 0.000 0.000 0.000 0.000 queues.py:59(_set_timeout)\n",
" 1 0.000 0.000 0.000 0.000 base_events.py:752(is_closed)\n",
" 1 0.000 0.000 0.000 0.000 iostream.py:255(closed)"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"%prun first(solve('NUM + BER = PLAY'))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"`%prun` tells us that over half the time is spent in `eval`, which makes sense because we call `eval` once for each pemutation of the digits. But we don't need to do that. We could call `eval` just once to create a Python function which we than **call** (not **eval**) for each permutation. That will be faster, because we won't have to re-eval the formula each time (parsing it and generating bytecode each time); it will be translated once into Python bytecode.\n",
"\n",
"For `\"NUM + BER = PLAY\"`, the Python function could be:\n",
"\n",
" (lambda N,U,M,B,E,R,P,L,A,Y:\n",
" N and B and P and (100*N + 10*U + M) + (100*B + 10*E + R) == (1000*P + 100*L + 10*A + Y))\n",
" \n",
"Note that:\n",
"- The parameters of the function are the letters that appear in the formula.\n",
"- The word `NUM` in the math formula translates to `(100*N + 10*U + M)` in the Python function.\n",
"- The letters that start each word, `N, B` and `P`, cannot be zero, so we test them first. \n",
"- A function might still divide by zero; that will have to be caught elsewhere.\n",
"\n",
"Here is the code to do the translation:"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"collapsed": false,
"jupyter": {
"outputs_hidden": false
}
},
"outputs": [],
"source": [
"def translate_formula(formula: Formula) -> tuple[str, str]:\n",
" \"\"\"Translate formula into two values: (lambda function string, parameter letters).\"\"\"\n",
" letters = all_letters(formula)\n",
" assert len(letters) <= 10, f'{len(letters)} letters is too many; only 10 allowed'\n",
" firsts = re.findall(r'\\b([A-Z])[A-Z]', formula)\n",
" body = re.sub('[A-Z]+', translate_word, to_python(formula))\n",
" return f'lambda {\",\".join(letters)}: {\" and \".join([*firsts, body])}', letters\n",
"\n",
"def translate_word(matchobj: re.Match) -> str:\n",
" \"Translate the matched word 'PLAY' to '(((P*10+L)*10+A)*10+Y))', e.g.\"\n",
" word = matchobj.group()\n",
" exponents = reversed(range(len(word)))\n",
" terms = (f'{10 ** x}*{L}' if x > 0 else L \n",
" for x, L in zip(exponents, word))\n",
" return '(' + ' + '.join(terms) + ')'"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Some usage examples:"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"('lambda A,B,C,D: C and (A) + (B) == (10*C + D)', 'ABCD')"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"translate_formula(\"A + B = CD\")"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"('lambda N,U,M,B,E,R,P,L,A,Y: N and B and P and (100*N + 10*U + M) + (100*B + 10*E + R) == (1000*P + 100*L + 10*A + Y)',\n",
" 'NUMBERPLAY')"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"translate_formula(\"NUM + BER = PLAY\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now we're ready for the faster version of `solve`:"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [],
"source": [
"def faster_solve(formula: Formula) -> Iterable[Solution]:\n",
" \"\"\"Given a formula like 'NUM + BER == PLAY', fill in digits to solve it.\n",
" This version precompiles the formula.\"\"\"\n",
" python_lambda, letters = translate_formula(to_python(formula))\n",
" formula_fn = eval(python_lambda)\n",
" for digits in permutations((1,2,3,4,5,6,7,8,9,0), len(letters)):\n",
" try:\n",
" if formula_fn(*digits) is True:\n",
" yield subst(map(str, digits), letters, formula)\n",
" except ArithmeticError: \n",
" pass "
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'246 + 789 = 1035'"
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"first(faster_solve('NUM + BER = PLAY'))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"How fast is it? "
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {
"collapsed": false,
"jupyter": {
"outputs_hidden": false
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"CPU times: user 476 ms, sys: 1.66 ms, total: 478 ms\n",
"Wall time: 477 ms\n"
]
}
],
"source": [
"%time solutions2 = list(faster_solve('NUM + BER = PLAY'))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"About 20 times faster! Does it give the same solutions as `solve`?"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [],
"source": [
"assert solutions == solutions2"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Yes, it does."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# More Example Formulas\n",
"\n",
"Here are some classic examples as well as some I made up myself:"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"formulas = \"\"\"\n",
"NUM + BER = PLAY\n",
"YOU = ME ^ 2\n",
"SEND + MORE = MONEY\n",
"FOUR + SCORE + 7 = YEARS + AGO\n",
"WRONG + WRONG = RIGHT\n",
"WRIGHT + WRIGHT = TO * FLY + FLIGHT\n",
"HALF + HALF = WHOLE\n",
"HALF + FIFTH + TENTH + TENTH + TENTH = WHOLE\n",
"BASE + BALL = GAMES\n",
"YOUR + YOU = HEART\n",
"EAT + THAT = APPLE\n",
"ALPHABET + LETTERS = SCRABBLE\n",
"POTATO + TOMATO = PUMPKIN\n",
"ODD * ODD = FREAKY\n",
"DOUBLE + DOUBLE + TOIL = TROUBLE\n",
"WASH + YOUR = HANDS\n",
"WEAR + A + MASK + WASH = SAFER\n",
"PERSON + WOMAN + MAN = CAMERA\n",
"TWO + TWENTY = TWELVE + TEN\n",
"AA + BB + CC = ABC\n",
"PI * R^2 = AREA\n",
"A^2 + B^2 = C^2\n",
"A^2 + BE^2 = BY^2 \n",
"AYH^2 + BEE^2 = SEE^2\n",
"RAMN = R^3 + RM^3 = N^3 + RX^3\n",
"MON-EY = EVIL^(1/2)\n",
"SIN^2 + COS^2 = UNITY\n",
"SPEED + LIMIT = FIFTY\n",
"TERRIBLE + NUMBER = THIRTEEN\n",
"SEVEN + SEVEN + SIX = TWENTY\n",
"EIGHT + EIGHT + TWO + ONE + ONE = TWENTY\n",
"ELEVEN + NINE + FIVE + FIVE = THIRTY\n",
"NINE + SEVEN + SEVEN + SEVEN = THIRTY\n",
"FOURTEEN + TEN + TEN + SEVEN = FORTYONE\n",
"HAWAII + IDAHO + IOWA + OHIO = STATES\n",
"VIOLIN * 2 + VIOLA = TRIO + SONATA\n",
"SEND + A + TAD + MORE = MONEY\n",
"ZEROES + ONES = BINARY\n",
"DCLIZ + DLXVI = MCCXXV\n",
"COUPLE + COUPLE = QUARTET\n",
"FISH + N + CHIPS = SUPPER\n",
"SATURN + URANUS + NEPTUNE + PLUTO = PLANETS\n",
"PLUTO not in {PLANETS}\n",
"EARTH + AIR + FIRE + WATER = NATURE\n",
"TWO * TWO = SQUARE\n",
"HIP * HIP = HURRAY\n",
"NORTH / SOUTH = EAST / WEST\n",
"NAUGHT ^ 2 = ZERO ^ 3\n",
"I + THINK + IT + BE + THINE = INDEED\n",
"DO + YOU + FEEL = LUCKY\n",
"WELL - DO + YOU = PUNK\n",
"NOW + WE + KNOW + THE = TRUTH\n",
"SORRY + TO + BE + A + PARTY = POOPER\n",
"SORRY + TO + BUST + YOUR = BUBBLE\n",
"STEEL + BELTED = RADIALS\n",
"2 * (ABRA + CADABRA) = HOUDINI\n",
"I + GUESS + THE + TRUTH = HURTS\n",
"LETS + CUT + TO + THE = CHASE\n",
"THATS + THE + THEORY = ANYWAY\n",
"TWO + TWO = FOUR\n",
"X / X = X\n",
"X + X = X\n",
"A^N + B^N = C^N and N > 1\n",
"ATOM^0.5 = A + TO + M\n",
"ALL + GLITTERS is not GOLD\n",
"ONE < TWO and FOUR < FIVE\n",
"ONE < TWO < THREE < TWO * TWO\n",
"(2 * BE or not 2 * BE) = THE + QUES-TION\n",
"sum(range(AA)) = BB\n",
"sum(range(POP)) = BOBO\n",
"ODD + ODD = EVEN\n",
"ROMANS+ALSO+MORE+OR+LESS+ADDED = LETTERS\n",
"X * X * X = M\n",
"XXVI + CCCXXXI = CCCLVII\n",
"LXVII + CCCLXXX = CDXLVII\n",
"CXX * XLII = MMMMMXL\n",
"FOUR+ONE = FIVE and ONE+ONE+ONE+ONE+ONE = FIVE\n",
"TEN+SEVEN+SEVEN+SEVEN+FOUR+FOUR+ONE = FORTY\n",
"NINETEEN+THIRTEEN+THREE+2*TWO+3*ONE = FORTYTWO\n",
"IN + ARCTIC + TERRAIN + AN + ANCIENT + EERIE + ICE + TRACT + I + ENTER + A + TRANCE = FLATIANA\n",
"ONE < TWO < THREE < SEVEN - THREE < THREE + TWO < THREE + THREE < SEVEN < SEVEN + ONE < THREE * THREE\n",
"ABCDEFGHIJ/JIHGFEDCBA = AI/IG\n",
"AN + ACCELERATING + INFERENTIAL + ENGINEERING + TALE + ELITE + GRANT + FEE + ET + CETERA = ARTIFICIAL + INTELLIGENCE\n",
"\"\"\".strip().splitlines()"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {
"collapsed": false,
"jupyter": {
"outputs_hidden": false
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"NUM + BER = PLAY\n",
"246 + 789 = 1035\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"YOU = ME ^ 2\n",
"289 = 17 ^ 2\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"SEND + MORE = MONEY\n",
"9567 + 1085 = 10652\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"FOUR + SCORE + 7 = YEARS + AGO\n",
"6071 + 29014 + 7 = 34512 + 580\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"WRONG + WRONG = RIGHT\n",
"12734 + 12734 = 25468\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"WRIGHT + WRIGHT = TO * FLY + FLIGHT\n",
"413058 + 413058 = 82 * 769 + 763058\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"HALF + HALF = WHOLE\n",
"9604 + 9604 = 19208\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"HALF + FIFTH + TENTH + TENTH + TENTH = WHOLE\n",
"6701 + 14126 + 25326 + 25326 + 25326 = 96805\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"BASE + BALL = GAMES\n",
"7483 + 7455 = 14938\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"YOUR + YOU = HEART\n",
"9426 + 942 = 10368\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"EAT + THAT = APPLE\n",
"819 + 9219 = 10038\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"ALPHABET + LETTERS = SCRABBLE\n",
"17531908 + 7088062 = 24619970\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"POTATO + TOMATO = PUMPKIN\n",
"168486 + 863486 = 1031972\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"ODD * ODD = FREAKY\n",
"677 * 677 = 458329\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"DOUBLE + DOUBLE + TOIL = TROUBLE\n",
"798064 + 798064 + 1936 = 1598064\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"WASH + YOUR = HANDS\n",
"4261 + 7835 = 12096\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"WEAR + A + MASK + WASH = SAFER\n",
"2743 + 4 + 9416 + 2410 = 14573\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"PERSON + WOMAN + MAN = CAMERA\n",
"320567 + 96817 + 817 = 418201\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"TWO + TWENTY = TWELVE + TEN\n",
"123 + 124617 = 124594 + 146\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"AA + BB + CC = ABC\n",
"11 + 99 + 88 = 198\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"PI * R^2 = AREA\n",
"96 * 7^2 = 4704\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"A^2 + B^2 = C^2\n",
"3^2 + 4^2 = 5^2\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"A^2 + BE^2 = BY^2 \n",
"5^2 + 12^2 = 13^2 \n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"AYH^2 + BEE^2 = SEE^2\n",
"760^2 + 522^2 = 922^2\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"RAMN = R^3 + RM^3 = N^3 + RX^3\n",
"1729 = 1^3 + 12^3 = 9^3 + 10^3\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"MON-EY = EVIL^(1/2)\n",
"132-58 = 5476^(1/2)\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"SIN^2 + COS^2 = UNITY\n",
"235^2 + 142^2 = 75389\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"SPEED + LIMIT = FIFTY\n",
"10224 + 73635 = 83859\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"TERRIBLE + NUMBER = THIRTEEN\n",
"45881795 + 302758 = 46184553\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"SEVEN + SEVEN + SIX = TWENTY\n",
"68782 + 68782 + 650 = 138214\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"EIGHT + EIGHT + TWO + ONE + ONE = TWENTY\n",
"52371 + 52371 + 104 + 485 + 485 = 105816\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"ELEVEN + NINE + FIVE + FIVE = THIRTY\n",
"797275 + 5057 + 4027 + 4027 = 810386\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"NINE + SEVEN + SEVEN + SEVEN = THIRTY\n",
"3239 + 49793 + 49793 + 49793 = 152618\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"FOURTEEN + TEN + TEN + SEVEN = FORTYONE\n",
"19564882 + 482 + 482 + 78082 = 19643928\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"HAWAII + IDAHO + IOWA + OHIO = STATES\n",
"510199 + 98153 + 9301 + 3593 = 621246\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"VIOLIN * 2 + VIOLA = TRIO + SONATA\n",
"176478 * 2 + 17645 = 2076 + 368525\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"SEND + A + TAD + MORE = MONEY\n",
"9283 + 7 + 473 + 1062 = 10825\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"ZEROES + ONES = BINARY\n",
"698392 + 3192 = 701584\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"DCLIZ + DLXVI = MCCXXV\n",
"62049 + 60834 = 122883\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"COUPLE + COUPLE = QUARTET\n",
"653924 + 653924 = 1307848\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"FISH + N + CHIPS = SUPPER\n",
"5718 + 3 + 98741 = 104462\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"SATURN + URANUS + NEPTUNE + PLUTO = PLANETS\n",
"127503 + 502351 + 3947539 + 46578 = 4623971\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"PLUTO not in {PLANETS}\n",
"12345 not in {1267849}\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"EARTH + AIR + FIRE + WATER = NATURE\n",
"67432 + 704 + 8046 + 97364 = 173546\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"TWO * TWO = SQUARE\n",
"567 * 567 = 321489\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"HIP * HIP = HURRAY\n",
"958 * 958 = 917764\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"NORTH / SOUTH = EAST / WEST\n",
"51304 / 61904 = 7260 / 8760\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"NAUGHT ^ 2 = ZERO ^ 3\n",
"328509 ^ 2 = 4761 ^ 3\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"I + THINK + IT + BE + THINE = INDEED\n",
"1 + 64125 + 16 + 73 + 64123 = 128338\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"DO + YOU + FEEL = LUCKY\n",
"57 + 870 + 9441 = 10368\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"WELL - DO + YOU = PUNK\n",
"1399 - 65 + 750 = 2084\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"NOW + WE + KNOW + THE = TRUTH\n",
"673 + 38 + 9673 + 128 = 10512\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"SORRY + TO + BE + A + PARTY = POOPER\n",
"80556 + 20 + 34 + 9 + 19526 = 100145\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"SORRY + TO + BUST + YOUR = BUBBLE\n",
"94665 + 24 + 1092 + 5406 = 101187\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"STEEL + BELTED = RADIALS\n",
"87336 + 936732 = 1024068\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"2 * (ABRA + CADABRA) = HOUDINI\n",
"2 * (7457 + 1797457) = 3609828\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"I + GUESS + THE + TRUTH = HURTS\n",
"5 + 26811 + 478 + 49647 = 76941\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"LETS + CUT + TO + THE = CHASE\n",
"9478 + 127 + 75 + 704 = 10384\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"THATS + THE + THEORY = ANYWAY\n",
"86987 + 863 + 863241 = 951091\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"TWO + TWO = FOUR\n",
"734 + 734 = 1468\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"X / X = X\n",
"1 / 1 = 1\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"X + X = X\n",
"0 + 0 = 0\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"A^N + B^N = C^N and N > 1\n",
"3^2 + 4^2 = 5^2 and 2 > 1\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"ATOM^0.5 = A + TO + M\n",
"1296^0.5 = 1 + 29 + 6\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"ALL + GLITTERS is not GOLD\n",
"122 + 32455678 is not 3920\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"ONE < TWO and FOUR < FIVE\n",
"123 < 451 and 6178 < 6903\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"ONE < TWO < THREE < TWO * TWO\n",
"123 < 451 < 46733 < 451 * 451\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"(2 * BE or not 2 * BE) = THE + QUES-TION\n",
"(2 * 13 or not 2 * 13) = 793 + 6438-7205\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"sum(range(AA)) = BB\n",
"sum(range(11)) = 55\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"sum(range(POP)) = BOBO\n",
"sum(range(101)) = 5050\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"ODD + ODD = EVEN\n",
"655 + 655 = 1310\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"ROMANS+ALSO+MORE+OR+LESS+ADDED = LETTERS\n",
"975348+3187+5790+79+1088+36606 = 1022098\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"X * X * X = M\n",
"2 * 2 * 2 = 8\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"XXVI + CCCXXXI = CCCLVII\n",
"3370 + 1113330 = 1116700\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"LXVII + CCCLXXX = CDXLVII\n",
"20133 + 8882000 = 8902133\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"CXX * XLII = MMMMMXL\n",
"422 * 2633 = 1111126\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"FOUR+ONE = FIVE and ONE+ONE+ONE+ONE+ONE = FIVE\n",
"1380+345 = 1725 and 345+345+345+345+345 = 1725\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"TEN+SEVEN+SEVEN+SEVEN+FOUR+FOUR+ONE = FORTY\n",
"520+12820+12820+12820+4937+4937+902 = 49756\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"NINETEEN+THIRTEEN+THREE+2*TWO+3*ONE = FORTYTWO\n",
"42415114+56275114+56711+2*538+3*841 = 98750538\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"IN + ARCTIC + TERRAIN + AN + ANCIENT + EERIE + ICE + TRACT + I + ENTER + A + TRANCE = FLATIANA\n",
"42 + 379549 + 5877342 + 32 + 3294825 + 88748 + 498 + 57395 + 4 + 82587 + 3 + 573298 = 10354323\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"ONE < TWO < THREE < SEVEN - THREE < THREE + TWO < THREE + THREE < SEVEN < SEVEN + ONE < THREE * THREE\n",
"123 < 451 < 46733 < 93832 - 46733 < 46733 + 451 < 46733 + 46733 < 93832 < 93832 + 123 < 46733 * 46733\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"ABCDEFGHIJ/JIHGFEDCBA = AI/IG\n",
"1073589264/4629853701 = 16/69\n",
"——————————————————————————————————————————————————————————————————————————————————————————\n",
"AN + ACCELERATING + INFERENTIAL + ENGINEERING + TALE + ELITE + GRANT + FEE + ET + CETERA = ARTIFICIAL + INTELLIGENCE\n",
"59 + 577404251698 + 69342491650 + 49869442698 + 1504 + 40614 + 82591 + 344 + 41 + 741425 = 5216367650 + 691400684974\n",
"CPU times: user 18.2 s, sys: 47.4 ms, total: 18.2 s\n",
"Wall time: 18.2 s\n"
]
},
{
"data": {
"text/plain": [
"83"
]
},
"execution_count": 15,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def show(formulas: Iterable[Formula], sep='—'*90):\n",
" \"\"\"Solve all the formulas and show results.\"\"\"\n",
" for f in formulas:\n",
" print(f'{sep}\\n{f}\\n{first(faster_solve(f))}')\n",
" return len(formulas)\n",
" \n",
"%time show(formulas)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Tests\n",
"\n",
"Here are some unit tests for the functions defined above:"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [],
"source": [
"for solver in (solve, faster_solve):\n",
" assert \"1 + 2 = 3\" in set(solver(\"A + B = C\"))\n",
" assert not set(solver(\"A + B = CDE\"))\n",
" assert set(solver(\"A * B = CA\")) == {\n",
" '5 * 3 = 15', '5 * 7 = 35', '4 * 6 = 24', '8 * 6 = 48', '2 * 6 = 12', '5 * 9 = 45'}\n",
"\n",
"assert '359 + 847 = 1206' in set(faster_solve('NUM + BER = PLAY')) \n",
"\n",
"assert subst(\"123\", \"ABC\", \"A + B = C\") == \"1 + 2 = 3\"\n",
"\n",
"assert valid(\"1 + 2 == 3\")\n",
"assert not valid(\"1 + 2 == 4\")\n",
"assert not valid(\"1/0 == 1/0\")\n",
"\n",
"assert to_python(\"A^B = C\") == \"A**B == C\"\n",
"\n",
"assert all_letters(\"A + B = C\") == \"ABC\"\n",
"\n",
"assert first(\"ABC\") == \"A\"\n",
"\n",
"assert cat(['A', 'B', 'C']) == \"ABC\"\n",
"\n",
"assert leading_zero('012')\n",
"assert not leading_zero('123')\n",
"assert not leading_zero('0')\n",
"\n",
"assert translate_word(re.match('NUM', 'NUM')) == '(100*N + 10*U + M)'\n",
"assert translate_word(re.match('X', 'X')) == '(X)'\n",
"\n",
"assert translate_formula(\"A + B = CD\") == ('lambda A,B,C,D: C and (A) + (B) == (10*C + D)', 'ABCD')\n",
"assert translate_formula(\"NUM + BER = PLAY\") == (\n",
" 'lambda N,U,M,B,E,R,P,L,A,Y: N and B and P and (100*N + 10*U + M) + (100*B + 10*E + R) == (1000*P + 100*L + 10*A + Y)',\n",
" 'NUMBERPLAY')"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.13.3"
}
},
"nbformat": 4,
"nbformat_minor": 4
}