Card24.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Find mathematical expression which is equals a given number using a set of numbers\n",
    "===========================================\n",
    "# Problem Statement\n",
    "Goal of this exercise is to write code which accepts a set of numbers and then tries to devise an arithmetic expression that yields a requested value, using four basic arithmetic operations: addition, subtraction, multiplication and division. Each input number must be used exactly once in the expression. Division is applicable only to numbers that are divisible without remainder. All input numbers and the target number are integers greater than zero. There are no more than 5 input numbers and target number is not larger than 1000.\n",
    "Example 1: Suppose that numbers 4, 8 and 9 are given and value 18 should be constructed. One solution is: 9 * 8 / 4.\n",
    "Example 2: If numbers 6, 7 and 9 are given, number 3 requested, then solution is: 6 / (9 - 7).\n",
    "\n",
    "# References\n",
    "Python implementation of the solution posted at http://www.codinghelmet.com/?path=exercises/expression-from-numbers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from Queue import Queue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def SolveAndPrint(numbers, targetValue):\n",
    "    targetKey = (targetValue << len(numbers)) + (1 << len(numbers)) - 1\n",
    "    # (value << numbers.Length) represents expression value\n",
    "    # (1 << numbers.Length) - 1 represents mask with all bits set to 1,\n",
    "    # i.e. mask in which each input number has been used exactly once\n",
    "    # to build the expression.\n",
    "    \n",
    "    solvedKeys = set()\n",
    "    # Each number in the collection indicates that corresponding value + mask\n",
    "    # has been reached using arithmetical operations.\n",
    "    \n",
    "    keyToLeftParent  = dict()\n",
    "    # For each solved key (value + mask), there is an entry indicating\n",
    "    # result of the expression on the left side of the arithmetic\n",
    "    # operator. Missing value indicates that key represents the\n",
    "    # raw number (taken from the input list), rather than\n",
    "    # the result of a calculation.\n",
    "    \n",
    "    keyToRightParent = dict()\n",
    "    # Same as keyToLeftParent, only indicating the right parent\n",
    "    # used to build the expression.\n",
    "    \n",
    "    keyToOperator = dict()\n",
    "    # Indicates arithmetic operator used to build this node\n",
    "    # from left and right parent nodes. Missing value for a given key\n",
    "    # indicates that key is a raw value taken from input array,\n",
    "    # rather than result of an arithmetic operation.\n",
    "    \n",
    "    queue = Queue()\n",
    "    # Keys (value + mask pairs) that have not been processed yet\n",
    "\n",
    "    # First step is to initialize the structures:\n",
    "    # Add all input values into corresponding array entries and\n",
    "    # add them to the queue so that the operation can begin\n",
    "    for i in range(len(numbers)):\n",
    "        key = (numbers[i] << len(numbers)) + (1 << i)\n",
    "        solvedKeys.add(key)\n",
    "        queue.put(key)\n",
    "    \n",
    "    # Now expand entries one at the time until queue is empty,\n",
    "    # i.e. until there are no new entries populated.\n",
    "    # Additional stopping condition is that target key has been generated,\n",
    "    # which indicates that problem has been solved and there is no need to\n",
    "    # expand nodes any further.\n",
    "    while (not queue.empty() > 0 and (targetKey not in solvedKeys)):\n",
    "        curKey = queue.get()\n",
    "\n",
    "        curMask = curKey & ((1 << len(numbers)) - 1)\n",
    "        curValue = curKey >> len(numbers)\n",
    "        \n",
    "        # Now first take a snapshot of all keys that\n",
    "        # have been reached because this collection is going to\n",
    "        # change during the following operation\n",
    "        keys = solvedKeys.copy()\n",
    "\n",
    "        for keys_i in keys:\n",
    "            mask = keys_i & ((1 << len(numbers)) - 1)\n",
    "            value = keys_i >> len(numbers)\n",
    "\n",
    "            if ((mask & curMask) == 0):\n",
    "                # Masks are disjoint, i.e. two entries do not use\n",
    "                # the same input number twice.\n",
    "                # This is sufficient condition to combine the two entries\n",
    "                for op in range(6):\n",
    "                    opSign = '\\0'\n",
    "                    newValue = 0\n",
    "                    if op == 0: # Addition\n",
    "                        newValue = curValue + value\n",
    "                        opSign = '+'\n",
    "                    elif op == 1: # Subtraction - another value subtracted from current\n",
    "                        newValue = curValue - value\n",
    "                        opSign = '-'\n",
    "                    elif op == 2: # Subtraction - current value subtracted from another\n",
    "                        newValue = value - curValue\n",
    "                        opSign = '-'\n",
    "                    elif op == 3: # Multiplication\n",
    "                        newValue = curValue * value\n",
    "                        opSign = '*'\n",
    "                    elif op == 4: # Division - current divided by another\n",
    "                        newValue = -1  # Indicates failure to divide\n",
    "                        if (value != 0 and curValue % value == 0):\n",
    "                            newValue = curValue / value\n",
    "                        opSign = '/'\n",
    "                    elif op == 5: # Division - other value divided by current\n",
    "                        newValue = -1  # Indicates failure to divide\n",
    "                        if (curValue != 0 and value % curValue == 0):\n",
    "                            newValue = value / curValue\n",
    "                        opSign = '/'\n",
    "\n",
    "                    if (newValue >= 0):\n",
    "                        # Ignore negative values - they can always be created\n",
    "                        # the other way around, by subtracting them\n",
    "                        # from a larger value so that positive value is reached.\n",
    "                        newMask = (curMask | mask)\n",
    "                        # Combine the masks to indicate that all input numbers\n",
    "                        # from both operands have been used to produce\n",
    "                        # the resulting expression\n",
    "                        \n",
    "                        newKey = (newValue << len(numbers)) + newMask\n",
    "                        if (newKey not in solvedKeys):\n",
    "                            # We have reached a new entry.\n",
    "                            # This expression should now be added\n",
    "                            # to data structures and processed further\n",
    "                            # in the following steps.\n",
    "\n",
    "                            # Populate entries that describe newly created expression\n",
    "                            solvedKeys.add(newKey);\n",
    "                            if (op == 2 or op == 5):\n",
    "                                # Special cases - antireflexive operations\n",
    "                                # with interchanged operands\n",
    "                                keyToLeftParent[newKey]= keys_i\n",
    "                                keyToRightParent[newKey] =  curKey\n",
    "                            else:\n",
    "                                keyToLeftParent[newKey] = curKey\n",
    "                                keyToRightParent[newKey]= keys_i\n",
    "                            keyToOperator[newKey] = opSign\n",
    "                            # Add expression to list of reachable expressions\n",
    "                            solvedKeys.add(newKey)\n",
    "                            # Add expression to the queue for further expansion\n",
    "                            queue.put(newKey)\n",
    "    # Now print the solution if it has been found\n",
    "    if (targetKey not in solvedKeys):\n",
    "        print \"Solution has not been found.\"\n",
    "    else:\n",
    "        PrintExpression(keyToLeftParent, keyToRightParent, keyToOperator, targetKey, len(numbers))\n",
    "        print \"={0}\".format(targetValue)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def PrintExpression(keyToLeftParent, keyToRightParent, keyToOperator, key, numbersCount):\n",
    "    if (key not in keyToOperator):\n",
    "        print \"{0}\".format(key >> numbersCount),\n",
    "    else:\n",
    "        print \"(\",\n",
    "        # Recursively print the left operand\n",
    "        PrintExpression(keyToLeftParent, keyToRightParent, keyToOperator, keyToLeftParent[key], numbersCount)\n",
    "        # Then print the operation sign\n",
    "        print keyToOperator[key],\n",
    "        # Finally, print the right operand\n",
    "        PrintExpression(keyToLeftParent, keyToRightParent, keyToOperator, keyToRightParent[key], numbersCount)\n",
    "        print \")\","
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solution has not been found.\n"
     ]
    }
   ],
   "source": [
    "SolveAndPrint([2,2,22], 24)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}