hotel_stops.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Hotel Stops #\n",
    "\n",
    "### The Problem: ###\n",
    "\n",
    "You are going on a trip and start at mile post 0. There are $n$ hotels along your route, at mile posts $a_1 < a_2 < ... < a_n$. Each mile post $a_i$ is measured from mile post 0. You can choose which of the hotels you stop at, but you must stop at the final hotel (at distance $a_n$) which is your destination.\n",
    "\n",
    "You must travel in as close to 200 mile increments as possible, given the spacing of the hotels. If you travel $x$ miles during a day, the penalty for that day is calculated as $(200 - x)^2$. Find the list of optimal hotel stops that minimizes the total penalty over the entire route.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step 1: Define subproblem in words ###\n",
    "\n",
    "$P(i) =$ minimum penalty for traveling between $a_1$ and $a_i$, with a stop at $a_i$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step 2: Find the recurrence relation ###\n",
    "\n",
    "$$P(i) = \\min\\limits_{k} \\left\\{P(k) + (200 - (a_i - a_k))^2 : 0 \\le k < i - 1 \\right\\}.$$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step 3: Translate into code ###"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 115,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Hotel locations: [10, 210, 410, 610, 611]\n",
      "Minimum penalty for entire route: 101\n",
      "Optimal stops: [1, 2, 4] \n",
      "\n",
      "Hotel locations: [0, 200, 400, 600, 601]\n",
      "Minimum penalty for entire route: 1\n",
      "Optimal stops: [1, 2, 4] \n",
      "\n",
      "Hotel locations: [1]\n",
      "Minimum penalty for entire route: 39601\n",
      "Optimal stops: [0] \n",
      "\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "\n",
    "def penalty(miles):\n",
    "    \"\"\"Penalty function.\"\"\"\n",
    "    return (200 - miles)**2\n",
    "\n",
    "\n",
    "def minimum_hotel_stop_penalty(mile_post):\n",
    "    \"\"\"Return the minimum penalty for traveling from milepost 0 to hotel n, and a list of the optimal hotel stops.\n",
    "    \n",
    "    :param mile_post: list of milepost locations for hotels 1 through n\n",
    "    :return: minimum penalty and list containing optimal stops\n",
    "    \"\"\"\n",
    "    n = len(mile_post)\n",
    "    \n",
    "    assert n > 0, \"List of hotel mile posts cannot be empty.\"\n",
    "    \n",
    "    table = np.zeros((n), dtype=int)\n",
    "    prev = []\n",
    "\n",
    "    # For each hotel...\n",
    "    for i in range(n):\n",
    "        min_penalty = penalty(mile_post[i])\n",
    "        prev_stop = -1\n",
    "        # ... Iterate over all prior hotels\n",
    "        for j in range(i):\n",
    "            # Penalty for traveling from mile 0 to hotel i is: \n",
    "            #   penalty of traveling from mile 0 to hotel j + \n",
    "            #   penalty of traveling from hotel j to hotel i\n",
    "            j_penalty = table[j] + penalty(mile_post[i] - mile_post[j])\n",
    "            # We want the minimum penalty across all prior hotels\n",
    "            if j_penalty < min_penalty:\n",
    "                min_penalty = j_penalty\n",
    "                prev_stop = j\n",
    "        # Record lowest penalty for traveling from mile 0 to hotel i\n",
    "        table[i] = min_penalty\n",
    "        # Record the hotel stop prior to i\n",
    "        prev.append(prev_stop)\n",
    "    \n",
    "    # Add final hotel to list of stops\n",
    "    stops = [n - 1]\n",
    "    # Build list of optimal hotel stops (backwards)\n",
    "    while prev:\n",
    "        p = prev.pop()\n",
    "        if p != stops[-1] and p != -1:\n",
    "            stops.append(p)\n",
    "   \n",
    "    return table[-1], stops[::-1]\n",
    "\n",
    "\n",
    "def run_test_suite(test_cases):\n",
    "    \"\"\"Test suite runner.\n",
    "    \n",
    "    :param test_cases: list of dicts each containing a test case\n",
    "    :return: None\n",
    "    \"\"\"\n",
    "    for case in test_cases:\n",
    "        print(\"Hotel locations: %s\" % case[\"mile_post\"])\n",
    "        pen, stops = minimum_hotel_stop_penalty(case[\"mile_post\"])\n",
    "        print(\"Minimum penalty for entire route: %d\" % pen)\n",
    "        print(\"Optimal stops: %s \\n\" % stops)\n",
    "        assert pen == case[\"penalty\"]\n",
    "        assert stops == case[\"optimal_stops\"]\n",
    "\n",
    "\n",
    "# Example problems\n",
    "test_cases = [{\"mile_post\": [10, 210, 410, 610, 611],\n",
    "               \"penalty\": 101,\n",
    "               \"optimal_stops\": [1, 2, 4]},\n",
    "              {\"mile_post\": [0, 200, 400, 600, 601],\n",
    "               \"penalty\": 1,\n",
    "               \"optimal_stops\": [1, 2, 4]},\n",
    "              {\"mile_post\": [1],\n",
    "               \"penalty\": 199**2,\n",
    "               \"optimal_stops\": [0]}\n",
    "             ]\n",
    "\n",
    "# Run the test suite\n",
    "run_test_suite(test_cases)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step 4: Analyze runtime complexity ###\n",
    "\n",
    "There are two nested *for* loops that iterate over a maximum of n elements. \n",
    "\n",
    "Therefore, the runtime of this algorithm is:\n",
    "\n",
    "**$$O(n^2).$$**"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.6",
   "language": "python",
   "name": "python_3.6"
  },
  "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.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}