{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "fRyPU77dbVRU"
      },
      "source": [
        "```{index} disjunctive programming\n",
        "```\n",
        "\n",
        "# Extra material: Cryptarithms puzzle\n",
        "\n",
        "The July 1924 issue of the famous British magazine *The Strand* included a word puzzle by Henry E. Dudeney in his regular contribution \"Perplexities\". The puzzle is to assign a unique digit to each letter appearing in the equation\n",
        "\n",
        "        S E N D\n",
        "      + M O R E\n",
        "    = M O N E Y\n",
        "\n",
        "such that the arithmetic equation is satisfied, and the leading digit for M is non-zero. There are [many more examples](http://cryptarithms.awardspace.us/puzzles.html) of these puzzles, but this is perhaps the most well-known."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {},
      "outputs": [],
      "source": [
        "# install dependencies and select solver\n",
        "%pip install -q amplpy\n",
        "\n",
        "SOLVER = \"cbc\"\n",
        "\n",
        "from amplpy import AMPL, ampl_notebook\n",
        "\n",
        "ampl = ampl_notebook(\n",
        "    modules=[\"cbc\"],  # modules to install\n",
        "    license_uuid=\"default\",  # license to use\n",
        ")  # instantiate AMPL object and register magics"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "1P6EoEpxisaN"
      },
      "source": [
        "## Modeling and Solution\n",
        "\n",
        "There are several possible approaches to modeling this puzzle in AMPL. \n",
        "\n",
        "[One approach](https://stackoverflow.com/questions/67456379/pyomo-model-constraint-programming-for-sendmore-money-task)  would be to using a matrix of binary variables $x_{a,d}$ indexed by letter $a$ and digit $d$ such that $x_{a,d} = 1$ designates the corresponding assignment. The problem constraints can then be implemented by summing the binary variables along the two axes. The arithmetic constraint becomes a more challenging.\n",
        "\n",
        "[Another approach](https://www.gecode.org/doc/6.0.1/MPG.pdf) is to use integer variables indexed by letters, then setup an linear expression to represent the puzzle. If we use the notation $n_a$ to represent the digit assigned to letter $a$, the algebraic constraint becomes\n",
        "\n",
        "$$\n",
        "\\begin{align*}\n",
        "1000 n_s + 100 n_e + 10 n_n + n_d \\\\\n",
        "+ 1000 n_m + 100 n_o + 10 n_r + n_e \\\\ \n",
        "= 10000 n_m + 1000 n_o + 100 n_n + 10 n_e + n_y\n",
        "\\end{align*}\n",
        "$$\n",
        "\n",
        "The requirement that no two letters be assigned the same digit can be represented as a disjunction. Letting $n_a$ and $n_b$ denote the integers assigned to letters $a$ and $b$, the disjunction becomes\n",
        "\n",
        "$$\n",
        "\\begin{align*}\n",
        "\\begin{bmatrix}n_a \\lt n_b\\end{bmatrix} \n",
        "\\ \\veebar\\  &\n",
        "\\begin{bmatrix}n_b \\lt n_a\\end{bmatrix} \n",
        "& \\forall a \\lt b\n",
        "\\end{align*}$$\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 2,
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Overwriting cryptarithms.mod\n"
          ]
        }
      ],
      "source": [
        "%%writefile cryptarithms.mod\n",
        "\n",
        "set LETTERS;\n",
        "set PAIRS within {LETTERS, LETTERS};\n",
        "\n",
        "var n{LETTERS} integer >= 0, <= 9;\n",
        "\n",
        "s.t. message:\n",
        "                       1000*n['S'] + 100*n['E'] + 10*n['N'] + n['D']\n",
        "                     + 1000*n['M'] + 100*n['O'] + 10*n['R'] + n['E']\n",
        "     == 10000*n['M'] + 1000*n['O'] + 100*n['N'] + 10*n['E'] + n['Y'];\n",
        "\n",
        "# leading digit must be non-zero\n",
        "s.t. leading_digit_nonzero: n['M'] >= 1;\n",
        "    \n",
        "# assign a different number to each letter\n",
        "s.t. unique_assignment{(a, b) in PAIRS}:\n",
        "    (n[a] >= n[b] + 1\n",
        "    or\n",
        "    n[b] >= n[a] + 1)\n",
        "    and not\n",
        "    (n[a] >= n[b] + 1\n",
        "    and\n",
        "    n[b] >= n[a] + 1);"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 3,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "executionInfo": {
          "elapsed": 640,
          "status": "ok",
          "timestamp": 1647633791981,
          "user": {
            "displayName": "Jeffrey Kantor",
            "photoUrl": "https://lh3.googleusercontent.com/a-/AOh14Gg_n8V7bVINy02QRuRgOoMo11Ri7NKU3OUKdC1bkQ=s64",
            "userId": "09038942003589296665"
          },
          "user_tz": 240
        },
        "id": "krDXKLopgjr-",
        "outputId": "94c3c4da-f118-4a42-d620-3d7a71d49df9"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "cbc 2.10.7: \b\b\b\b\b\b\b\b\b\b\b\bcbc 2.10.7: optimal solution\n",
            "9 simplex iterations\n",
            "9 barrier iterations\n",
            "Objective = find a feasible point.\n",
            "     9 5 6 7\n",
            "  +  1 0 8 5\n",
            "  ----------\n",
            "=  1 0 6 5 2\n"
          ]
        }
      ],
      "source": [
        "m = AMPL()\n",
        "m.read(\"cryptarithms.mod\")\n",
        "\n",
        "LETTERS = [\"S\", \"E\", \"N\", \"D\", \"M\", \"O\", \"R\", \"Y\"]\n",
        "PAIRS = [(a, b) for a in LETTERS for b in LETTERS if a < b]\n",
        "\n",
        "m.set[\"LETTERS\"] = LETTERS\n",
        "m.set[\"PAIRS\"] = PAIRS\n",
        "\n",
        "m.solve(solver=SOLVER)\n",
        "assert m.solve_result == \"solved\", m.solve_result\n",
        "\n",
        "n = m.var[\"n\"].to_dict()\n",
        "\n",
        "\n",
        "def letters2num(s):\n",
        "    return \" \".join(map(lambda s: f\"{int(round(n[s], 0))}\", list(s)))\n",
        "\n",
        "\n",
        "print(\"    \", letters2num(\"SEND\"))\n",
        "print(\"  + \", letters2num(\"MORE\"))\n",
        "print(\"  ----------\")\n",
        "print(\"= \", letters2num(\"MONEY\"))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ka68BXoTkbjw"
      },
      "source": [
        "## Suggested exercises\n",
        "\n",
        "1. AMPL includes [Logic, Nonlinear & Constraint Programming Extensions](https://ampl.com/products/ampl/logic-and-constraint-programming-extensions/). Rewrite the model with different combinations of logical operators and compare the performance with one obtained with the constraint solver `gecode`.\n",
        "\n",
        "2. There are [many more examples](http://cryptarithms.awardspace.us/puzzles.html) of cryptarithm puzzles. Refactor this code and create a function that can be used to solve generic puzzles of this type."
      ]
    }
  ],
  "metadata": {
    "colab": {
      "authorship_tag": "ABX9TyN4MNrWBGDy5YGPH38fzjvZ",
      "collapsed_sections": [],
      "name": "cryptarithms-end-more-money.ipynb",
      "provenance": []
    },
    "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.10.6"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 4
}