stock sales.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false,
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "New max:  25 -> [(0, 7)] (bound: 200)\n",
      "New max:  27 -> [(0, 9)] (bound: 216)\n",
      "New max:  66 -> [(1, 7)] (bound: 528)\n",
      "New max:  68 -> [(1, 9)] (bound: 544)\n",
      "New max:  75 -> [(2, 7)] (bound: 600)\n",
      "New max:  77 -> [(2, 9)] (bound: 616)\n",
      "New max:  102 -> [(2, 9), (0, 7)] (bound: 408)\n",
      "New max:  143 -> [(2, 9), (1, 7)] (bound: 572)\n",
      "New max:  152 -> [(2, 9), (4, 7)] (bound: 608)\n",
      "New max:  168 -> [(2, 9), (4, 7), (0, 8)] (bound: 448)\n",
      "New max:  209 -> [(2, 9), (4, 7), (1, 8)] (bound: 557)\n",
      "New max:  213 -> [(2, 9), (4, 7), (6, 8)] (bound: 568)\n",
      "New max:  214 -> [(2, 9), (4, 7), (14, 16)] (bound: 570)\n",
      "New max:  230 -> [(2, 9), (4, 7), (14, 16), (0, 8)] (bound: 460)\n",
      "New max:  271 -> [(2, 9), (4, 7), (14, 16), (1, 8)] (bound: 542)\n",
      "New max:  275 -> [(2, 9), (4, 7), (14, 16), (6, 8)] (bound: 550)\n",
      "New max:  276 -> [(2, 9), (4, 7), (14, 16), (20, 21)] (bound: 552)\n",
      "New max:  292 -> [(2, 9), (4, 7), (14, 16), (20, 21), (0, 8)] (bound: 467)\n",
      "New max:  333 -> [(2, 9), (4, 7), (14, 16), (20, 21), (1, 8)] (bound: 532)\n",
      "New max:  337 -> [(2, 9), (4, 7), (14, 16), (20, 21), (6, 8)] (bound: 539)\n",
      "New max:  351 -> [(2, 9), (4, 7), (14, 16), (20, 21), (6, 8), (0, 10)] (bound: 468)\n",
      "New max:  392 -> [(2, 9), (4, 7), (14, 16), (20, 21), (6, 8), (1, 10)] (bound: 522)\n",
      "New max:  397 -> [(2, 9), (4, 7), (14, 16), (20, 21), (6, 8), (1, 10), (0, 17)] (bound: 453)\n",
      "New max:  398 -> [(2, 9), (4, 7), (14, 16), (20, 21), (6, 8), (1, 10), (0, 18)] (bound: 454)\n",
      "New max:  406 -> [(2, 9), (4, 7), (14, 16), (20, 21), (6, 8), (1, 10), (0, 22)] (bound: 464)\n",
      "New max:  425 -> [(2, 9), (4, 7), (14, 16), (20, 21), (6, 8), (1, 10), (3, 11)] (bound: 485)\n",
      "New max:  438 -> [(2, 9), (4, 7), (14, 16), (20, 21), (6, 8), (1, 10), (3, 17)] (bound: 500)\n",
      "New max:  439 -> [(2, 9), (4, 7), (14, 16), (20, 21), (6, 8), (1, 10), (3, 18)] (bound: 501)\n",
      "New max:  447 -> [(2, 9), (4, 7), (14, 16), (20, 21), (6, 8), (1, 10), (3, 22)] (bound: 510)\n",
      "New max:  452 -> [(2, 9), (4, 7), (14, 16), (20, 21), (6, 8), (1, 10), (3, 22), (0, 17)] (bound: 452)\n",
      "New max:  453 -> [(2, 9), (4, 7), (14, 16), (20, 21), (6, 8), (1, 10), (3, 22), (0, 18)] (bound: 453)\n",
      "New max:  480 -> [(2, 9), (4, 7), (14, 16), (20, 21), (6, 8), (1, 10), (3, 22), (5, 11)] (bound: 480)\n",
      "New max:  493 -> [(2, 9), (4, 7), (14, 16), (20, 21), (6, 8), (1, 10), (3, 22), (5, 17)] (bound: 493)\n",
      "New max:  494 -> [(2, 9), (4, 7), (14, 16), (20, 21), (6, 8), (1, 10), (3, 22), (5, 18)] (bound: 494)\n"
     ]
    }
   ],
   "source": [
    "from heapq import heappush, heappop\n",
    "import itertools\n",
    "\n",
    "MAX_SALES = 8\n",
    "STOCK_PRICES = [51, 10, 1, 10, 1, 10, 6, 76, 67, 78, 65, 43, 23, 22, 3, 43, 65, 56,\n",
    "                57, 32, 3, 65, 65, 22, 2, 29]\n",
    "\n",
    "partialSolutions = []\n",
    "\n",
    "class PartialSolution():\n",
    "    def __init__(self, known_sales, next_sale=None):\n",
    "        self.known_sales = known_sales[::]\n",
    "        if next_sale:\n",
    "            self.known_sales.append(next_sale)\n",
    "        self.value = self._calc_value()\n",
    "        self.upper_limit = self._calc_upper_limit()\n",
    "        \n",
    "    def enumerate_children(self):\n",
    "        used_dates = set(itertools.chain.from_iterable(self.known_sales))\n",
    "        \n",
    "        free_dates = set(range(len(STOCK_PRICES))) - used_dates\n",
    "        free_dates = sorted(list(free_dates))\n",
    "        \n",
    "        \n",
    "        for buy_date in free_dates[:-1]:\n",
    "            for sell_date in free_dates:\n",
    "                if sell_date > buy_date:\n",
    "                    yield (buy_date, sell_date)\n",
    "    \n",
    "    def _calc_value(self):\n",
    "        value = 0\n",
    "        for buy_date, sell_date in self.known_sales:\n",
    "            value += STOCK_PRICES[sell_date] - STOCK_PRICES[buy_date]\n",
    "        return value\n",
    "    \n",
    "    def _calc_upper_limit(self):\n",
    "        \"\"\"\n",
    "        This upper limit works if we make the following assumptions:\n",
    "         - When num_sales is zero, we are the only element in the queue\n",
    "         - The same solution can be achieved through multiple paths (that is,\n",
    "           the same set of sales can be achieved in different order).  We only\n",
    "           explore the branches that have the highest value sales first\n",
    "        \"\"\"\n",
    "        try:\n",
    "            return self.value * float(MAX_SALES ) / float(self.num_sales())\n",
    "        except ZeroDivisionError:\n",
    "            return 0\n",
    "    \n",
    "    def num_sales(self):\n",
    "        return len(self.known_sales)\n",
    "    \n",
    "    def __repr__(self):\n",
    "        return \"{} -> {} (bound: {})\".format(str(self.value), str(self.known_sales), int(self.upper_limit))\n",
    "    \n",
    "    def __lt__(self, other):\n",
    "        return self.value > other.value\n",
    "\n",
    "value_maximum = 0\n",
    "value_maximizer = PartialSolution([])\n",
    "\n",
    "partialSolutions.append(value_maximizer)\n",
    "\n",
    "from pprint import pprint\n",
    "\n",
    "while partialSolutions:\n",
    "    #pprint(partialSolutions)\n",
    "    sol = heappop(partialSolutions)\n",
    "    if sol.upper_limit < value_maximum:\n",
    "        break\n",
    "    if sol.num_sales() >= MAX_SALES:\n",
    "        continue\n",
    "    \n",
    "    for next_sale in sol.enumerate_children():\n",
    "        next_child = PartialSolution(sol.known_sales, next_sale)\n",
    "        if next_child.value > value_maximum:\n",
    "            print(\"New max: \", next_child)\n",
    "            value_maximum = next_child.value\n",
    "            value_maximizer = next_child\n",
    "        heappush(partialSolutions, next_child)"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [conda env:anaconda3]",
   "language": "python",
   "name": "conda-env-anaconda3-py"
  },
  "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}