ipynb/Cryptarithmetic.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div align=\"right\" style=\"text-align:right\"><i>Peter Norvig<br>2014, 2020</i></div>\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/) that quotes my friend [Bill Gosper](https://en.wikipedia.org/wiki/Bill_Gosper). (Gosper often presents more advanced puzzles in the [math-fun](http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun) mailing list.)  This puzzle was:\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",
    "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",
    "![](https://www.azquotes.com/picture-quotes/quote-when-in-doubt-use-brute-force-ken-thompson-131-46-05.jpg)\n",
    "\n",
    "My initial approach follows Ken Thompson's adage,  \"when in doubt, use brute force.\"\n",
    "\n",
    "- There are only 10 factorial or 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 one(s) that are.\n",
    "\n",
    "The basic idea is simple, but there are a few complications to worry about:\n",
    "\n",
    "- Python uses `==` for equality and `**` for exponentiation, but math notation  uses `=` and `^`.   I'll accept any of these, and translate from math to Python with `to_python`.\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 `1/0` or `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",
    "- Only uppercase letters are replaced by digits. So in `2 * B or not 2 * BE`, the `or` and `not` are Python keywords.\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, Tuple\n",
    "from itertools import permutations\n",
    "import re\n",
    "\n",
    "Formula  = str # A formula in Math notation, like \"NUM ^ BER = PLAY\"\n",
    "Pformula = str # A formula in Python 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 (ones that evaluate to true and have no number with a leading zero). Note that `solve` checks if a `to_python` version of the  formula is `valid`, and if it is, returns a substituted version of the original formula."
   ]
  },
  {
   "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",
    "    pformula = to_python(formula)\n",
    "    for digits in permutations('1234567890', len(letters)):\n",
    "        if valid(subst(digits, letters, pformula)):\n",
    "            yield subst(digits, letters, formula)\n",
    "        \n",
    "def subst(digits, letters, formula) -> Formula:\n",
    "    \"\"\"Substitute digits for letters in formula.\"\"\"\n",
    "    return formula.translate(str.maketrans(letters, cat(digits)))\n",
    "        \n",
    "def valid(pformula) -> bool:\n",
    "    \"\"\"A pformula is valid iff it has no leading zero, and evaluates to True.\"\"\"\n",
    "    try:\n",
    "        return (not leading_zero(pformula)) and (eval(pformula) is True)\n",
    "    except ArithmeticError:\n",
    "        return False\n",
    "    \n",
    "def to_python(formula: Formula) -> Pformula:\n",
    "    \"\"\"Convert ' = ' and '^' to ' == ' and '**'.\"\"\"\n",
    "    return formula.replace(' = ', ' == ').replace('^', '**') \n",
    "\n",
    "def all_letters(formula: str) -> str: \n",
    "    \"\"\"The set of letters in formula, in the form of an alphabetized string.\"\"\"\n",
    "    return cat(sorted(set(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": [
    "It would be good to have some unit tests for these functions, but I moved them to the end of this notebook, so that 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": [
       "'587 + 439 = 1026'"
      ]
     },
     "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 16.9 s, sys: 19.2 ms, total: 17 s\n",
      "Wall time: 17 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "96"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time solutions = set(solve('NUM + BER = PLAY'))\n",
    "len(solutions)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It takes 15 or 20 seconds to find 96 solutions, Here are ten of them:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['452 + 637 = 1089',\n",
       " '589 + 437 = 1026',\n",
       " '879 + 426 = 1305',\n",
       " '749 + 286 = 1035',\n",
       " '756 + 342 = 1098',\n",
       " '673 + 425 = 1098',\n",
       " '439 + 587 = 1026',\n",
       " '432 + 657 = 1089',\n",
       " '423 + 675 = 1098',\n",
       " '429 + 876 = 1305']"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(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": [
       "         3028913 function calls in 3.011 seconds\n",
       "\n",
       "   Ordered by: internal time\n",
       "\n",
       "   ncalls  tottime  percall  cumtime  percall filename:lineno(function)\n",
       "   309270    1.779    0.000    1.833    0.000 {built-in method builtins.eval}\n",
       "   453271    0.229    0.000    0.229    0.000 {method 'translate' of 'str' objects}\n",
       "   453270    0.220    0.000    0.220    0.000 {method 'search' of 're.Pattern' objects}\n",
       "        2    0.215    0.107    3.065    1.532 89248256.py:1(solve)\n",
       "   453271    0.209    0.000    0.669    0.000 89248256.py:9(subst)\n",
       "   453271    0.146    0.000    0.146    0.000 {built-in method maketrans}\n",
       "   453270    0.128    0.000    2.182    0.000 89248256.py:13(valid)\n",
       "   453272    0.084    0.000    0.084    0.000 {method 'join' of 'str' objects}\n",
       "        1    0.000    0.000    3.065    3.065 89248256.py:28(first)\n",
       "        1    0.000    0.000    3.065    3.065 {built-in method builtins.exec}\n",
       "        1    0.000    0.000    0.000    0.000 89248256.py:24(all_letters)\n",
       "        1    0.000    0.000    0.000    0.000 {method 'findall' of 're.Pattern' objects}\n",
       "        1    0.000    0.000    0.000    0.000 re.py:233(findall)\n",
       "        1    0.000    0.000    0.000    0.000 89248256.py:20(to_python)\n",
       "        1    0.000    0.000    0.000    0.000 {built-in method builtins.sorted}\n",
       "        1    0.000    0.000    0.000    0.000 re.py:289(_compile)\n",
       "        1    0.000    0.000    3.065    3.065 {built-in method builtins.next}\n",
       "        1    0.000    0.000    0.000    0.000 {built-in method builtins.isinstance}\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 'disable' of '_lsprof.Profiler' objects}\n",
       "        1    0.000    0.000    0.000    0.000 {built-in method builtins.iter}\n",
       "        1    0.000    0.000    0.000    0.000 <string>:1(<module>)\n",
       "        1    0.000    0.000    0.000    0.000 {built-in method builtins.len}"
      ]
     },
     "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, verbose=False) -> 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 A,B,E,L,M,N,P,R,U,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",
       " 'ABELMNPRUY')"
      ]
     },
     "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": [
       "'587 + 439 = 1026'"
      ]
     },
     "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 1.11 s, sys: 3.16 ms, total: 1.11 s\n",
      "Wall time: 1.11 s\n"
     ]
    }
   ],
   "source": [
    "%time solutions2 = set(faster_solve('NUM + BER = PLAY'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "About 15 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",
    "ABRA + CADABRA + 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",
    "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",
      "587 + 439 = 1026\n",
      "__________________________________________________________________________________________\n",
      "YOU = ME ^ 2\n",
      "576 = 24 ^ 2\n",
      "__________________________________________________________________________________________\n",
      "SEND + MORE = MONEY\n",
      "9567 + 1085 = 10652\n",
      "__________________________________________________________________________________________\n",
      "FOUR + SCORE + 7 = YEARS + AGO\n",
      "9071 + 26014 + 7 = 34512 + 580\n",
      "__________________________________________________________________________________________\n",
      "WRONG + WRONG = RIGHT\n",
      "37081 + 37081 = 74162\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",
      "5291 + 6748 = 12039\n",
      "__________________________________________________________________________________________\n",
      "WEAR + A + MASK + WASH = SAFER\n",
      "9617 + 1 + 3125 + 9124 = 21867\n",
      "__________________________________________________________________________________________\n",
      "PERSON + WOMAN + MAN = CAMERA\n",
      "320567 + 96817 + 817 = 418201\n",
      "__________________________________________________________________________________________\n",
      "TWO + TWENTY = TWELVE + TEN\n",
      "784 + 781279 = 781351 + 712\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",
      "108-42 = 4356^(1/2)\n",
      "__________________________________________________________________________________________\n",
      "SIN^2 + COS^2 = UNITY\n",
      "235^2 + 142^2 = 75389\n",
      "__________________________________________________________________________________________\n",
      "SPEED + LIMIT = FIFTY\n",
      "40221 + 36568 = 76789\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",
      "63985 not in {6314287}\n",
      "__________________________________________________________________________________________\n",
      "EARTH + AIR + FIRE + WATER = NATURE\n",
      "67432 + 704 + 8046 + 97364 = 173546\n",
      "__________________________________________________________________________________________\n",
      "TWO * TWO = SQUARE\n",
      "807 * 807 = 651249\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",
      "5277 - 13 + 830 = 6094\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",
      "ABRA + CADABRA + ABRA + CADABRA = HOUDINI\n",
      "7457 + 1797457 + 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",
      "166 + 46500389 is not 4762\n",
      "__________________________________________________________________________________________\n",
      "ONE < TWO and FOUR < FIVE\n",
      "351 < 703 and 2386 < 2491\n",
      "__________________________________________________________________________________________\n",
      "ONE < TWO < THREE < TWO * TWO\n",
      "431 < 674 < 62511 < 674 * 674\n",
      "__________________________________________________________________________________________\n",
      "(2 * BE or not 2 * BE) = THE + QUES-TION\n",
      "(2 * 13 or not 2 * 13) = 843 + 7239-8056\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",
      "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",
      "321 < 483 < 45711 < 91612 - 45711 < 45711 + 483 < 45711 + 45711 < 91612 < 91612 + 321 < 45711 * 45711\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 42.1 s, sys: 77.8 ms, total: 42.2 s\n",
      "Wall time: 42.2 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "79"
      ]
     },
     "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 A,B,E,L,M,N,P,R,U,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",
    "    'ABELMNPRUY')"
   ]
  }
 ],
 "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.8.15"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}