{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# How much do you tip the staff?\n",
    "\n",
    "Each staff member has a rating, and knows the rating of adjacent members. you have to give a tip to each person, with these conditions:\n",
    "\n",
    "* each person gets at least on pound\n",
    "* if a person's neighbour has the same rating, this person gets at least as much as that neighbour\n",
    "* if a person's neighbour has a lower rating, this person gets more than that neighbour"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import random"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[7, 3, 9, 4, 9]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ratings = [random.randrange(1, 10) for _ in range(5)]\n",
    "ratings"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1, 1, 1, 1]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "payments = [1] * len(ratings)\n",
    "payments"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1, 2, 1, 2]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "for i in range(1, len(payments)):\n",
    "    if ratings[i] == ratings[i-1]:\n",
    "        payments[i] = payments[i-1]\n",
    "    elif ratings[i] > ratings[i-1]:\n",
    "        payments[i] = payments[i-1] + 1\n",
    "payments"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 2, 1, 0]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[i for i in reversed(range(len(payments)-1))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 1, 2, 1, 2]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "for i in reversed(range(len(payments) - 1)):\n",
    "    if ratings[i] == ratings[i+1]:\n",
    "        payments[i] = max(payments[i], payments[i+1])\n",
    "    elif ratings[i] > ratings[i+1]:\n",
    "        payments[i] = max(payments[i], payments[i+1] + 1)\n",
    "payments"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def payments_dp(ratings):\n",
    "    payments = [1] * len(ratings)\n",
    "    \n",
    "    for i in range(1, len(payments)):\n",
    "        if ratings[i] == ratings[i-1]:\n",
    "            payments[i] = payments[i-1]\n",
    "        elif ratings[i] > ratings[i-1]:\n",
    "            payments[i] = payments[i-1] + 1\n",
    "        \n",
    "    for i in reversed(range(len(payments) - 1)):\n",
    "        if ratings[i] == ratings[i+1]:\n",
    "            payments[i] = max(payments[i], payments[i+1])\n",
    "        elif ratings[i] > ratings[i+1]:\n",
    "            payments[i] = max(payments[i], payments[i+1] + 1)\n",
    "            \n",
    "    return payments"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 1, 2, 1, 2]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "payments_dp(ratings)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false,
    "scrolled": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([76,\n",
       "  34,\n",
       "  76,\n",
       "  40,\n",
       "  14,\n",
       "  91,\n",
       "  88,\n",
       "  96,\n",
       "  14,\n",
       "  1,\n",
       "  22,\n",
       "  97,\n",
       "  75,\n",
       "  59,\n",
       "  27,\n",
       "  24,\n",
       "  96,\n",
       "  70,\n",
       "  79,\n",
       "  3],\n",
       " [2, 1, 3, 2, 1, 2, 1, 3, 2, 1, 2, 5, 4, 3, 2, 1, 2, 1, 2, 1])"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ratings = [random.randrange(1, 100) for _ in range(20)]\n",
    "ratings, payments_dp(ratings)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5, 6, 7]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "payments_dp([1,2,3,4,5,6,7])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def is_valid(ratings, payments):\n",
    "    valid = True\n",
    "    for i in range(len(ratings)):\n",
    "        if i == 0:\n",
    "            left_r = ratings[i]\n",
    "            left_p = payments[i]\n",
    "        else:\n",
    "            left_r = ratings[i-1]\n",
    "            left_p = payments[i-1]\n",
    "        if i == len(ratings)-1:\n",
    "            right_r = ratings[i]\n",
    "            right_p = payments[i]\n",
    "        else:\n",
    "            right_r = ratings[i+1]\n",
    "            right_p = payments[i+1]\n",
    "#         print(i, ':', left_r, ratings[i], right_r, ':', left_p, payments[i], right_p)\n",
    "        if ratings[i] > left_r and payments[i] <= left_p:\n",
    "            valid = False\n",
    "        elif ratings[i] == left_r and payments[i] != left_p:\n",
    "            valid = False\n",
    "        elif ratings[i] < left_r and payments[i] >= left_p:\n",
    "            valid = False\n",
    "        if ratings[i] > right_r and payments[i] <= right_p:\n",
    "            valid = False\n",
    "        elif ratings[i] == right_r and payments[i] != right_p:\n",
    "            valid = False\n",
    "        elif ratings[i] < right_r and payments[i] >= right_p:\n",
    "            valid = False\n",
    "            \n",
    "    return valid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_valid(ratings, [1]*len(ratings))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_valid(ratings, payments_dp(ratings))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def payments_naive(ratings):\n",
    "    payments = [1] * len(ratings)\n",
    "    changes = True\n",
    "    while changes:\n",
    "        changes = False\n",
    "        for i in range(len(ratings)):\n",
    "            if i == 0:\n",
    "                left_r = ratings[i]\n",
    "                left_p = payments[i]\n",
    "            else:\n",
    "                left_r = ratings[i-1]\n",
    "                left_p = payments[i-1]\n",
    "            if i == len(ratings)-1:\n",
    "                right_r = ratings[i]\n",
    "                right_p = payments[i]\n",
    "            else:\n",
    "                right_r = ratings[i+1]\n",
    "                right_p = payments[i+1]\n",
    "                \n",
    "            if ratings[i] > left_r and payments[i] <= left_p:\n",
    "                payments[i] = left_p + 1\n",
    "                changes = True\n",
    "            elif ratings[i] == left_r and payments[i] != left_p:\n",
    "                payments[i] = left_p\n",
    "                changes = True\n",
    "            elif ratings[i] > right_r and payments[i] <= right_p:\n",
    "                payments[i] = right_p + 1\n",
    "                changes = True\n",
    "            elif ratings[i] == right_r and payments[i] != right_p:\n",
    "                payments[i] = right_p\n",
    "                changes = True\n",
    "\n",
    "    return payments"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 1, 3, 2, 1, 2, 1, 3, 2, 1, 2, 5, 4, 3, 2, 1, 2, 1, 2, 1]"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "payments_naive(ratings)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 1, 3, 2, 1, 2, 1, 3, 2, 1, 2, 5, 4, 3, 2, 1, 2, 1, 2, 1]"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "payments_dp(ratings)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[76, 34, 76, 40, 14, 91, 88, 96, 14, 1, 22, 97, 75, 59, 27, 24, 96, 70, 79, 3]"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ratings"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_valid(ratings, payments_naive(ratings))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "ratings = [random.randrange(1, 100) for _ in range(10**7)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_valid(ratings, payments_naive(ratings))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_valid(ratings, payments_dp(ratings))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 loop, best of 3: 1min 17s per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "payments_naive(ratings)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 loop, best of 3: 7.77 s per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "payments_dp(ratings)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}