{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#[The Puzzle From Vietnam](http://www.theguardian.com/science/alexs-adventures-in-numberland/2015/may/20/can-you-do-the-maths-puzzle-for-vietnamese-eight-year-olds-that-has-stumped-parents-and-teachers?CMP=share_btn_link)\n",
    "\n",
    "Replace the blanks with the digits $1-9$:\n",
    "\n",
    "\\begin{equation}\n",
    "\\_\\_+ 13 * \\frac{\\ \\ \\ \\_\\_\\ \\ \\ }{\\_\\_} + \\_\\_ + 12 * \\_\\_ - 11 + \\_\\_ * \\frac{\\ \\ \\ \\_\\_\\ \\ \\ }{\\_\\_} - 10 = 66\n",
    "\\end{equation}\n",
    "\n",
    "Now, this is already a rewriting of the original puzzle. It can be rewritten further for clarity.\n",
    "\n",
    "\\begin{equation}\n",
    "  a + 13 * \\frac{b}{c} + d + 12 * e - f - 11 + g* \\frac{h}{i} - 10 = 66\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "  a + 13 * \\frac{b}{c} + d + 12 * e - f + g * \\frac{h}{i} = 87\n",
    "\\end{equation}\n",
    "\n",
    "It's not much different, but already it makes more sense (I hope).\n",
    "\n",
    "There might be a simple way to solve it, but it hasn't revealed itself to me, so I'm going to leverage the power of a computer. There are $9$ different variables in the equation, each corresponding to a different digit from $1$ to $9$. Therefore, there are $9! = 9\\times8\\times7\\times6\\times5\\times4\\times3\\times2\\times1$ permutations for the assignments, as the first digit could be any of the nine numbers, the second digit could be any of the numbers save the first, hence 8, and so on."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "There are 362880 combinations of values for the blanks.\n"
     ]
    }
   ],
   "source": [
    "import math\n",
    "print(\"There are {} combinations of values for the blanks.\".format(math.factorial(9)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The brute force/naïve method is to simply try each combination and find (all of) the solutions. Therefore, first of all we will try $a=1, b=2, c=3,...$ etc, then another combination, then another until all 362880 combinations have been tested. I got a bit of help from [Stack Overflow](http://stackoverflow.com/a/104436/4244912) with the generator..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import time    # For timing the search\n",
    "\n",
    "# This is the equation from above, with blank spaces ready for quick evaluation.\n",
    "func = lambda a,b,c,d,e,f,g,h,i: a+13*b/c+d+12*e-f+g*h/i\n",
    "\n",
    "# This generates the permutations of a list of elements\n",
    "def permutations(elements):\n",
    "    \"\"\"\n",
    "    Generator object for getting the permuations of an array\n",
    "    \"\"\"\n",
    "    if len(elements) <=1:\n",
    "        yield elements\n",
    "    else:\n",
    "        for perm in permutations(elements[1:]):\n",
    "            for i in range(len(elements)):\n",
    "                yield perm[:i] + elements[0:1] + perm[i:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "ans = 87    #Our target\n",
    "\n",
    "solns = []    #A holder for the solutions we find.\n",
    "\n",
    "\n",
    "# This finds solutions by exhaustive trial and error!\n",
    "start = time.time()\n",
    "\n",
    "for perm in permutations([1,2,3,4,5,6,7,8,9]):\n",
    "    a,b,c,d,e,f,g,h,i = perm\n",
    "    if func(a,b,c,d,e,f,g,h,i) == ans:\n",
    "        solns.append(perm)\n",
    "\n",
    "end = time.time()\n",
    "\n",
    "dur = end-start"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Time taken to find answers: 1.8035364151000977 seconds\n",
      "There are 128 solutions. They are:\n",
      " a, b, c, d, e, f, g, h, i\n",
      "[4, 2, 6, 1, 7, 8, 3, 5, 9]      [4, 2, 6, 1, 7, 8, 3, 5, 9]\n",
      "[4, 2, 6, 1, 7, 8, 5, 3, 9]      [9, 2, 8, 7, 6, 5, 3, 1, 4]\n",
      "[1, 2, 6, 4, 7, 8, 3, 5, 9]      [9, 2, 8, 7, 6, 5, 1, 3, 4]\n",
      "[1, 2, 6, 4, 7, 8, 5, 3, 9]      [3, 9, 2, 8, 1, 5, 7, 6, 4]\n",
      "[5, 3, 1, 7, 2, 6, 8, 9, 4]      [9, 5, 3, 1, 4, 2, 8, 7, 6]\n",
      "[7, 3, 1, 5, 2, 6, 8, 9, 4]      [1, 5, 3, 9, 4, 2, 8, 7, 6]\n",
      "[7, 6, 4, 8, 5, 9, 1, 3, 2]      [9, 8, 6, 2, 4, 1, 7, 5, 3]\n",
      "[7, 6, 4, 8, 5, 9, 3, 1, 2]      [9, 8, 6, 2, 4, 1, 5, 7, 3]\n",
      "[3, 2, 1, 5, 4, 7, 8, 9, 6]      [3, 9, 2, 8, 1, 5, 6, 7, 4]\n",
      "[5, 2, 1, 3, 4, 7, 8, 9, 6]      [9, 4, 8, 5, 6, 7, 3, 1, 2]\n",
      "[5, 7, 2, 8, 3, 9, 1, 6, 4]      [9, 4, 8, 5, 6, 7, 1, 3, 2]\n",
      "[5, 7, 2, 8, 3, 9, 6, 1, 4]      [9, 3, 1, 6, 2, 5, 8, 7, 4]\n",
      "[7, 5, 2, 8, 4, 9, 1, 3, 6]      [1, 9, 6, 4, 5, 8, 7, 3, 2]\n",
      "[7, 5, 2, 8, 4, 9, 3, 1, 6]      [1, 9, 6, 4, 5, 8, 3, 7, 2]\n",
      "[7, 3, 2, 8, 5, 9, 1, 6, 4]      [9, 6, 4, 3, 5, 8, 7, 1, 2]\n",
      "[7, 3, 2, 8, 5, 9, 6, 1, 4]      [9, 6, 4, 3, 5, 8, 1, 7, 2]\n",
      "[7, 2, 8, 9, 6, 5, 1, 3, 4]      [4, 9, 6, 1, 5, 8, 7, 3, 2]\n",
      "[7, 2, 8, 9, 6, 5, 3, 1, 4]      [4, 9, 6, 1, 5, 8, 3, 7, 2]\n",
      "[6, 2, 8, 3, 5, 1, 7, 9, 4]      [5, 9, 3, 6, 2, 1, 8, 7, 4]\n",
      "[3, 2, 8, 6, 5, 1, 7, 9, 4]      [6, 9, 3, 5, 2, 1, 8, 7, 4]\n",
      "[8, 6, 4, 7, 5, 9, 1, 3, 2]      [6, 3, 1, 9, 2, 5, 8, 7, 4]\n",
      "[8, 6, 4, 7, 5, 9, 3, 1, 2]      [3, 6, 4, 9, 5, 8, 7, 1, 2]\n",
      "[1, 3, 2, 4, 5, 8, 7, 9, 6]      [3, 6, 4, 9, 5, 8, 1, 7, 2]\n",
      "[4, 3, 2, 1, 5, 8, 7, 9, 6]      [1, 3, 9, 4, 7, 8, 5, 2, 6]\n",
      "[3, 5, 2, 1, 4, 8, 7, 9, 6]      [1, 3, 9, 4, 7, 8, 2, 5, 6]\n",
      "[1, 5, 2, 3, 4, 8, 7, 9, 6]      [4, 3, 9, 1, 7, 8, 5, 2, 6]\n",
      "[1, 5, 2, 8, 4, 7, 3, 9, 6]      [4, 3, 9, 1, 7, 8, 2, 5, 6]\n",
      "[1, 5, 2, 8, 4, 7, 9, 3, 6]      [9, 5, 3, 1, 4, 2, 7, 8, 6]\n",
      "[3, 2, 4, 8, 5, 1, 7, 9, 6]      [9, 4, 1, 5, 2, 7, 8, 3, 6]\n",
      "[8, 2, 4, 3, 5, 1, 7, 9, 6]      [9, 4, 1, 5, 2, 7, 3, 8, 6]\n",
      "[8, 5, 2, 1, 4, 7, 3, 9, 6]      [1, 5, 3, 9, 4, 2, 7, 8, 6]\n",
      "[8, 5, 2, 1, 4, 7, 9, 3, 6]      [5, 4, 1, 9, 2, 7, 8, 3, 6]\n",
      "[8, 5, 2, 7, 4, 9, 1, 3, 6]      [5, 4, 1, 9, 2, 7, 3, 8, 6]\n",
      "[8, 5, 2, 7, 4, 9, 3, 1, 6]      [9, 1, 4, 7, 6, 5, 3, 2, 8]\n",
      "[8, 3, 2, 7, 5, 9, 1, 6, 4]      [9, 1, 4, 7, 6, 5, 2, 3, 8]\n",
      "[8, 3, 2, 7, 5, 9, 6, 1, 4]      [1, 9, 6, 7, 5, 2, 4, 3, 8]\n",
      "[8, 7, 2, 5, 3, 9, 1, 6, 4]      [1, 9, 6, 7, 5, 2, 3, 4, 8]\n",
      "[8, 7, 2, 5, 3, 9, 6, 1, 4]      [9, 3, 1, 6, 2, 5, 7, 8, 4]\n",
      "[2, 4, 8, 1, 7, 9, 3, 5, 6]      [2, 9, 6, 3, 5, 1, 7, 4, 8]\n",
      "[1, 4, 8, 2, 7, 9, 3, 5, 6]      [3, 9, 6, 2, 5, 1, 7, 4, 8]\n",
      "[2, 4, 8, 1, 7, 9, 5, 3, 6]      [2, 9, 6, 3, 5, 1, 4, 7, 8]\n",
      "[1, 4, 8, 2, 7, 9, 5, 3, 6]      [3, 9, 6, 2, 5, 1, 4, 7, 8]\n",
      "[6, 2, 8, 3, 5, 1, 9, 7, 4]      [9, 1, 2, 5, 6, 7, 4, 3, 8]\n",
      "[3, 2, 8, 6, 5, 1, 9, 7, 4]      [9, 1, 2, 5, 6, 7, 3, 4, 8]\n",
      "[2, 8, 6, 9, 4, 1, 5, 7, 3]      [9, 3, 2, 1, 5, 6, 7, 4, 8]\n",
      "[2, 8, 6, 9, 4, 1, 7, 5, 3]      [1, 3, 2, 9, 5, 6, 7, 4, 8]\n",
      "[5, 4, 8, 9, 6, 7, 1, 3, 2]      [9, 3, 2, 1, 5, 6, 4, 7, 8]\n",
      "[5, 4, 8, 9, 6, 7, 3, 1, 2]      [1, 3, 2, 9, 5, 6, 4, 7, 8]\n",
      "[8, 9, 2, 3, 1, 5, 6, 7, 4]      [5, 9, 3, 6, 2, 1, 7, 8, 4]\n",
      "[1, 3, 2, 4, 5, 8, 9, 7, 6]      [5, 1, 2, 9, 6, 7, 4, 3, 8]\n",
      "[4, 3, 2, 1, 5, 8, 9, 7, 6]      [5, 1, 2, 9, 6, 7, 3, 4, 8]\n",
      "[3, 5, 2, 1, 4, 8, 9, 7, 6]      [6, 9, 3, 5, 2, 1, 7, 8, 4]\n",
      "[1, 5, 2, 3, 4, 8, 9, 7, 6]      [6, 3, 1, 9, 2, 5, 7, 8, 4]\n",
      "[3, 2, 4, 8, 5, 1, 9, 7, 6]      [5, 2, 1, 3, 4, 7, 9, 8, 6]\n",
      "[8, 2, 4, 3, 5, 1, 9, 7, 6]      [3, 2, 1, 5, 4, 7, 9, 8, 6]\n",
      "[8, 9, 2, 3, 1, 5, 7, 6, 4]      [7, 9, 6, 1, 5, 2, 4, 3, 8]\n",
      "[2, 3, 6, 1, 7, 9, 4, 5, 8]      [7, 9, 6, 1, 5, 2, 3, 4, 8]\n",
      "[1, 3, 6, 2, 7, 9, 4, 5, 8]      [7, 1, 4, 9, 6, 5, 3, 2, 8]\n",
      "[2, 3, 6, 1, 7, 9, 5, 4, 8]      [7, 1, 4, 9, 6, 5, 2, 3, 8]\n",
      "[1, 3, 6, 2, 7, 9, 5, 4, 8]      [2, 1, 4, 3, 7, 9, 6, 5, 8]\n",
      "[5, 3, 1, 7, 2, 6, 9, 8, 4]      [3, 1, 4, 2, 7, 9, 6, 5, 8]\n",
      "[7, 3, 1, 5, 2, 6, 9, 8, 4]      [2, 1, 4, 3, 7, 9, 5, 6, 8]\n",
      "[1, 3, 4, 7, 6, 5, 2, 9, 8]      [3, 1, 4, 2, 7, 9, 5, 6, 8]\n",
      "[1, 3, 4, 7, 6, 5, 9, 2, 8]      [7, 3, 4, 1, 6, 5, 9, 2, 8]\n"
     ]
    }
   ],
   "source": [
    "print(\"Time taken to find answers: {} seconds\".format(dur))\n",
    "print(\"There are {} solutions. They are:\".format(len(solns)))\n",
    "print(\" a, b, c, d, e, f, g, h, i\")\n",
    "for i in range(len(solns)//2):\n",
    "    print(solns[i], \"    \",solns[-1*i])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(Actually this took all day!)\n",
    "\n",
    "\\- Ogaday"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Apparently, according to some sleuths, there are 136 solutions. The programs seem pretty gross, but someone posted a list of all of them. I'm going to compare them to my own solutions.\n",
    "\n",
    "First of all, data extraction:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "#Preprocessing: Extract the solutions from the format in which they were originally posted.\n",
    "\n",
    "f = open(\"puzzlesols.txt\", \"r\")\n",
    "\n",
    "temp_sols = []\n",
    "\n",
    "for line in f:\n",
    "    line = line.split(\":\")[-1].strip()\n",
    "    line = line.split(\", \")\n",
    "    line = [int(d) for d in line]\n",
    "    temp_sols.append(line)\n",
    "f.close()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "There are 136 solutions\n",
      "There are 136 unique sols\n"
     ]
    }
   ],
   "source": [
    "print(\"There are {} solutions\".format(len(temp_sols)))\n",
    "temp_sols_2 = set([tuple(temp) for temp in temp_sols])\n",
    "print(\"There are {} unique sols\".format(len(temp_sols_2)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "128 in intersect\n",
      "8 in temp but not solns\n",
      "[1, 8, 3, 7, 4, 5, 2, 6, 9]\n",
      "[1, 8, 3, 7, 4, 5, 6, 2, 9]\n",
      "[2, 6, 9, 8, 5, 1, 4, 7, 3]\n",
      "[2, 6, 9, 8, 5, 1, 7, 4, 3]\n",
      "[7, 8, 3, 1, 4, 5, 2, 6, 9]\n",
      "[7, 8, 3, 1, 4, 5, 6, 2, 9]\n",
      "[8, 6, 9, 2, 5, 1, 4, 7, 3]\n",
      "[8, 6, 9, 2, 5, 1, 7, 4, 3]\n"
     ]
    }
   ],
   "source": [
    "# See what the overlap is and what additonal answers have been found.\n",
    "\n",
    "intersect = []\n",
    "temp_butnot_solns = []\n",
    "for sol in temp_sols:\n",
    "    if sol in solns:\n",
    "        intersect.append(sol)\n",
    "    else:\n",
    "        temp_butnot_solns.append(sol)\n",
    "\n",
    "print(\"{} in intersect\".format(len(intersect)))\n",
    "print(\"{} in temp but not solns\".format(len(temp_butnot_solns)))\n",
    "for temp in temp_butnot_solns: print(temp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# It appears that the additional answers are all well formed, I though that perhaps they had repeated digits.\n",
    "# My second hypothesis is that my func is different:\n",
    "\n",
    "for temp in temp_butnot_solns:\n",
    "    a,b,c,d,e,f,g,h,i = temp\n",
    "    if func(a,b,c,d,e,f,g,h,i) == 87:\n",
    "        print(True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "86.99999999999999\n",
      "86.99999999999999\n",
      "86.99999999999999\n",
      "86.99999999999999\n",
      "86.99999999999999\n",
      "86.99999999999999\n",
      "86.99999999999999\n",
      "86.99999999999999\n"
     ]
    }
   ],
   "source": [
    "# It appears that our foundational assumptions are different then: we are interpreting the mathematical\n",
    "# symbols differently. I will look into this.\n",
    "\n",
    "diff = temp_butnot_solns\n",
    "\n",
    "# First step is to simply see what I get when I evaluate the permutations.\n",
    "for sol in diff:\n",
    "    a,b,c,d,e,f,g,h,i = sol\n",
    "    print(func(a,b,c,d,e,f,g,h,i))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# As we can see, it appears to be a rounding error."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.4.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}