09-resolving-the-bill/tipping-solution.ipynb

   1 {
   2  "cells": [
   3   {
   4    "cell_type": "markdown",
   5    "metadata": {},
   6    "source": [
   7     "# How much do you tip the staff?\n",
   8     "\n",
   9     "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",
  10     "\n",
  11     "* each person gets at least on pound\n",
  12     "* if a person's neighbour has the same rating, this person gets at least as much as that neighbour\n",
  13     "* if a person's neighbour has a lower rating, this person gets more than that neighbour"
  14    ]
  15   },
  16   {
  17    "cell_type": "code",
  18    "execution_count": 1,
  19    "metadata": {
  20     "collapsed": true
  21    },
  22    "outputs": [],
  23    "source": [
  24     "import random"
  25    ]
  26   },
  27   {
  28    "cell_type": "code",
  29    "execution_count": 2,
  30    "metadata": {
  31     "collapsed": false
  32    },
  33    "outputs": [
  34     {
  35      "data": {
  36       "text/plain": [
  37        "[7, 3, 9, 4, 9]"
  38       ]
  39      },
  40      "execution_count": 2,
  41      "metadata": {},
  42      "output_type": "execute_result"
  43     }
  44    ],
  45    "source": [
  46     "ratings = [random.randrange(1, 10) for _ in range(5)]\n",
  47     "ratings"
  48    ]
  49   },
  50   {
  51    "cell_type": "code",
  52    "execution_count": 3,
  53    "metadata": {
  54     "collapsed": false
  55    },
  56    "outputs": [
  57     {
  58      "data": {
  59       "text/plain": [
  60        "[1, 1, 1, 1, 1]"
  61       ]
  62      },
  63      "execution_count": 3,
  64      "metadata": {},
  65      "output_type": "execute_result"
  66     }
  67    ],
  68    "source": [
  69     "payments = [1] * len(ratings)\n",
  70     "payments"
  71    ]
  72   },
  73   {
  74    "cell_type": "code",
  75    "execution_count": 4,
  76    "metadata": {
  77     "collapsed": false
  78    },
  79    "outputs": [
  80     {
  81      "data": {
  82       "text/plain": [
  83        "[1, 1, 2, 1, 2]"
  84       ]
  85      },
  86      "execution_count": 4,
  87      "metadata": {},
  88      "output_type": "execute_result"
  89     }
  90    ],
  91    "source": [
  92     "for i in range(1, len(payments)):\n",
  93     "    if ratings[i] == ratings[i-1]:\n",
  94     "        payments[i] = payments[i-1]\n",
  95     "    elif ratings[i] > ratings[i-1]:\n",
  96     "        payments[i] = payments[i-1] + 1\n",
  97     "payments"
  98    ]
  99   },
 100   {
 101    "cell_type": "code",
 102    "execution_count": 5,
 103    "metadata": {
 104     "collapsed": false
 105    },
 106    "outputs": [
 107     {
 108      "data": {
 109       "text/plain": [
 110        "[3, 2, 1, 0]"
 111       ]
 112      },
 113      "execution_count": 5,
 114      "metadata": {},
 115      "output_type": "execute_result"
 116     }
 117    ],
 118    "source": [
 119     "[i for i in reversed(range(len(payments)-1))]"
 120    ]
 121   },
 122   {
 123    "cell_type": "code",
 124    "execution_count": 6,
 125    "metadata": {
 126     "collapsed": false
 127    },
 128    "outputs": [
 129     {
 130      "data": {
 131       "text/plain": [
 132        "[2, 1, 2, 1, 2]"
 133       ]
 134      },
 135      "execution_count": 6,
 136      "metadata": {},
 137      "output_type": "execute_result"
 138     }
 139    ],
 140    "source": [
 141     "for i in reversed(range(len(payments) - 1)):\n",
 142     "    if ratings[i] == ratings[i+1]:\n",
 143     "        payments[i] = max(payments[i], payments[i+1])\n",
 144     "    elif ratings[i] > ratings[i+1]:\n",
 145     "        payments[i] = max(payments[i], payments[i+1] + 1)\n",
 146     "payments"
 147    ]
 148   },
 149   {
 150    "cell_type": "code",
 151    "execution_count": 7,
 152    "metadata": {
 153     "collapsed": true
 154    },
 155    "outputs": [],
 156    "source": [
 157     "def payments_dp(ratings):\n",
 158     "    payments = [1] * len(ratings)\n",
 159     "    \n",
 160     "    for i in range(1, len(payments)):\n",
 161     "        if ratings[i] == ratings[i-1]:\n",
 162     "            payments[i] = payments[i-1]\n",
 163     "        elif ratings[i] > ratings[i-1]:\n",
 164     "            payments[i] = payments[i-1] + 1\n",
 165     "        \n",
 166     "    for i in reversed(range(len(payments) - 1)):\n",
 167     "        if ratings[i] == ratings[i+1]:\n",
 168     "            payments[i] = max(payments[i], payments[i+1])\n",
 169     "        elif ratings[i] > ratings[i+1]:\n",
 170     "            payments[i] = max(payments[i], payments[i+1] + 1)\n",
 171     "            \n",
 172     "    return payments"
 173    ]
 174   },
 175   {
 176    "cell_type": "code",
 177    "execution_count": 8,
 178    "metadata": {
 179     "collapsed": false
 180    },
 181    "outputs": [
 182     {
 183      "data": {
 184       "text/plain": [
 185        "[2, 1, 2, 1, 2]"
 186       ]
 187      },
 188      "execution_count": 8,
 189      "metadata": {},
 190      "output_type": "execute_result"
 191     }
 192    ],
 193    "source": [
 194     "payments_dp(ratings)"
 195    ]
 196   },
 197   {
 198    "cell_type": "code",
 199    "execution_count": 14,
 200    "metadata": {
 201     "collapsed": false,
 202     "scrolled": false
 203    },
 204    "outputs": [
 205     {
 206      "data": {
 207       "text/plain": [
 208        "([76,\n",
 209        "  34,\n",
 210        "  76,\n",
 211        "  40,\n",
 212        "  14,\n",
 213        "  91,\n",
 214        "  88,\n",
 215        "  96,\n",
 216        "  14,\n",
 217        "  1,\n",
 218        "  22,\n",
 219        "  97,\n",
 220        "  75,\n",
 221        "  59,\n",
 222        "  27,\n",
 223        "  24,\n",
 224        "  96,\n",
 225        "  70,\n",
 226        "  79,\n",
 227        "  3],\n",
 228        " [2, 1, 3, 2, 1, 2, 1, 3, 2, 1, 2, 5, 4, 3, 2, 1, 2, 1, 2, 1])"
 229       ]
 230      },
 231      "execution_count": 14,
 232      "metadata": {},
 233      "output_type": "execute_result"
 234     }
 235    ],
 236    "source": [
 237     "ratings = [random.randrange(1, 100) for _ in range(20)]\n",
 238     "ratings, payments_dp(ratings)"
 239    ]
 240   },
 241   {
 242    "cell_type": "code",
 243    "execution_count": 10,
 244    "metadata": {
 245     "collapsed": false
 246    },
 247    "outputs": [
 248     {
 249      "data": {
 250       "text/plain": [
 251        "[1, 2, 3, 4, 5, 6, 7]"
 252       ]
 253      },
 254      "execution_count": 10,
 255      "metadata": {},
 256      "output_type": "execute_result"
 257     }
 258    ],
 259    "source": [
 260     "payments_dp([1,2,3,4,5,6,7])"
 261    ]
 262   },
 263   {
 264    "cell_type": "code",
 265    "execution_count": 37,
 266    "metadata": {
 267     "collapsed": false
 268    },
 269    "outputs": [],
 270    "source": [
 271     "def is_valid(ratings, payments):\n",
 272     "    valid = True\n",
 273     "    for i in range(len(ratings)):\n",
 274     "        if i == 0:\n",
 275     "            left_r = ratings[i]\n",
 276     "            left_p = payments[i]\n",
 277     "        else:\n",
 278     "            left_r = ratings[i-1]\n",
 279     "            left_p = payments[i-1]\n",
 280     "        if i == len(ratings)-1:\n",
 281     "            right_r = ratings[i]\n",
 282     "            right_p = payments[i]\n",
 283     "        else:\n",
 284     "            right_r = ratings[i+1]\n",
 285     "            right_p = payments[i+1]\n",
 286     "#         print(i, ':', left_r, ratings[i], right_r, ':', left_p, payments[i], right_p)\n",
 287     "        if ratings[i] > left_r and payments[i] <= left_p:\n",
 288     "            valid = False\n",
 289     "        elif ratings[i] == left_r and payments[i] != left_p:\n",
 290     "            valid = False\n",
 291     "        elif ratings[i] < left_r and payments[i] >= left_p:\n",
 292     "            valid = False\n",
 293     "        if ratings[i] > right_r and payments[i] <= right_p:\n",
 294     "            valid = False\n",
 295     "        elif ratings[i] == right_r and payments[i] != right_p:\n",
 296     "            valid = False\n",
 297     "        elif ratings[i] < right_r and payments[i] >= right_p:\n",
 298     "            valid = False\n",
 299     "            \n",
 300     "    return valid"
 301    ]
 302   },
 303   {
 304    "cell_type": "code",
 305    "execution_count": 38,
 306    "metadata": {
 307     "collapsed": false
 308    },
 309    "outputs": [
 310     {
 311      "data": {
 312       "text/plain": [
 313        "False"
 314       ]
 315      },
 316      "execution_count": 38,
 317      "metadata": {},
 318      "output_type": "execute_result"
 319     }
 320    ],
 321    "source": [
 322     "is_valid(ratings, [1]*len(ratings))"
 323    ]
 324   },
 325   {
 326    "cell_type": "code",
 327    "execution_count": 39,
 328    "metadata": {
 329     "collapsed": false
 330    },
 331    "outputs": [
 332     {
 333      "data": {
 334       "text/plain": [
 335        "True"
 336       ]
 337      },
 338      "execution_count": 39,
 339      "metadata": {},
 340      "output_type": "execute_result"
 341     }
 342    ],
 343    "source": [
 344     "is_valid(ratings, payments_dp(ratings))"
 345    ]
 346   },
 347   {
 348    "cell_type": "code",
 349    "execution_count": 40,
 350    "metadata": {
 351     "collapsed": true
 352    },
 353    "outputs": [],
 354    "source": [
 355     "def payments_naive(ratings):\n",
 356     "    payments = [1] * len(ratings)\n",
 357     "    changes = True\n",
 358     "    while changes:\n",
 359     "        changes = False\n",
 360     "        for i in range(len(ratings)):\n",
 361     "            if i == 0:\n",
 362     "                left_r = ratings[i]\n",
 363     "                left_p = payments[i]\n",
 364     "            else:\n",
 365     "                left_r = ratings[i-1]\n",
 366     "                left_p = payments[i-1]\n",
 367     "            if i == len(ratings)-1:\n",
 368     "                right_r = ratings[i]\n",
 369     "                right_p = payments[i]\n",
 370     "            else:\n",
 371     "                right_r = ratings[i+1]\n",
 372     "                right_p = payments[i+1]\n",
 373     "                \n",
 374     "            if ratings[i] > left_r and payments[i] <= left_p:\n",
 375     "                payments[i] = left_p + 1\n",
 376     "                changes = True\n",
 377     "            elif ratings[i] == left_r and payments[i] != left_p:\n",
 378     "                payments[i] = left_p\n",
 379     "                changes = True\n",
 380     "            elif ratings[i] > right_r and payments[i] <= right_p:\n",
 381     "                payments[i] = right_p + 1\n",
 382     "                changes = True\n",
 383     "            elif ratings[i] == right_r and payments[i] != right_p:\n",
 384     "                payments[i] = right_p\n",
 385     "                changes = True\n",
 386     "\n",
 387     "    return payments"
 388    ]
 389   },
 390   {
 391    "cell_type": "code",
 392    "execution_count": 41,
 393    "metadata": {
 394     "collapsed": false
 395    },
 396    "outputs": [
 397     {
 398      "data": {
 399       "text/plain": [
 400        "[2, 1, 3, 2, 1, 2, 1, 3, 2, 1, 2, 5, 4, 3, 2, 1, 2, 1, 2, 1]"
 401       ]
 402      },
 403      "execution_count": 41,
 404      "metadata": {},
 405      "output_type": "execute_result"
 406     }
 407    ],
 408    "source": [
 409     "payments_naive(ratings)"
 410    ]
 411   },
 412   {
 413    "cell_type": "code",
 414    "execution_count": 42,
 415    "metadata": {
 416     "collapsed": false
 417    },
 418    "outputs": [
 419     {
 420      "data": {
 421       "text/plain": [
 422        "[2, 1, 3, 2, 1, 2, 1, 3, 2, 1, 2, 5, 4, 3, 2, 1, 2, 1, 2, 1]"
 423       ]
 424      },
 425      "execution_count": 42,
 426      "metadata": {},
 427      "output_type": "execute_result"
 428     }
 429    ],
 430    "source": [
 431     "payments_dp(ratings)"
 432    ]
 433   },
 434   {
 435    "cell_type": "code",
 436    "execution_count": 43,
 437    "metadata": {
 438     "collapsed": false
 439    },
 440    "outputs": [
 441     {
 442      "data": {
 443       "text/plain": [
 444        "[76, 34, 76, 40, 14, 91, 88, 96, 14, 1, 22, 97, 75, 59, 27, 24, 96, 70, 79, 3]"
 445       ]
 446      },
 447      "execution_count": 43,
 448      "metadata": {},
 449      "output_type": "execute_result"
 450     }
 451    ],
 452    "source": [
 453     "ratings"
 454    ]
 455   },
 456   {
 457    "cell_type": "code",
 458    "execution_count": 44,
 459    "metadata": {
 460     "collapsed": false
 461    },
 462    "outputs": [
 463     {
 464      "data": {
 465       "text/plain": [
 466        "True"
 467       ]
 468      },
 469      "execution_count": 44,
 470      "metadata": {},
 471      "output_type": "execute_result"
 472     }
 473    ],
 474    "source": [
 475     "is_valid(ratings, payments_naive(ratings))"
 476    ]
 477   },
 478   {
 479    "cell_type": "code",
 480    "execution_count": 55,
 481    "metadata": {
 482     "collapsed": true
 483    },
 484    "outputs": [],
 485    "source": [
 486     "ratings = [random.randrange(1, 100) for _ in range(10**7)]"
 487    ]
 488   },
 489   {
 490    "cell_type": "code",
 491    "execution_count": 56,
 492    "metadata": {
 493     "collapsed": false
 494    },
 495    "outputs": [
 496     {
 497      "data": {
 498       "text/plain": [
 499        "True"
 500       ]
 501      },
 502      "execution_count": 56,
 503      "metadata": {},
 504      "output_type": "execute_result"
 505     }
 506    ],
 507    "source": [
 508     "is_valid(ratings, payments_naive(ratings))"
 509    ]
 510   },
 511   {
 512    "cell_type": "code",
 513    "execution_count": 57,
 514    "metadata": {
 515     "collapsed": false
 516    },
 517    "outputs": [
 518     {
 519      "data": {
 520       "text/plain": [
 521        "True"
 522       ]
 523      },
 524      "execution_count": 57,
 525      "metadata": {},
 526      "output_type": "execute_result"
 527     }
 528    ],
 529    "source": [
 530     "is_valid(ratings, payments_dp(ratings))"
 531    ]
 532   },
 533   {
 534    "cell_type": "code",
 535    "execution_count": 58,
 536    "metadata": {
 537     "collapsed": false
 538    },
 539    "outputs": [
 540     {
 541      "name": "stdout",
 542      "output_type": "stream",
 543      "text": [
 544       "1 loop, best of 3: 1min 17s per loop\n"
 545      ]
 546     }
 547    ],
 548    "source": [
 549     "%%timeit\n",
 550     "payments_naive(ratings)"
 551    ]
 552   },
 553   {
 554    "cell_type": "code",
 555    "execution_count": 59,
 556    "metadata": {
 557     "collapsed": false
 558    },
 559    "outputs": [
 560     {
 561      "name": "stdout",
 562      "output_type": "stream",
 563      "text": [
 564       "1 loop, best of 3: 7.77 s per loop\n"
 565      ]
 566     }
 567    ],
 568    "source": [
 569     "%%timeit\n",
 570     "payments_dp(ratings)"
 571    ]
 572   },
 573   {
 574    "cell_type": "code",
 575    "execution_count": null,
 576    "metadata": {
 577     "collapsed": true
 578    },
 579    "outputs": [],
 580    "source": []
 581   }
 582  ],
 583  "metadata": {
 584   "kernelspec": {
 585    "display_name": "Python 3",
 586    "language": "python",
 587    "name": "python3"
 588   },
 589   "language_info": {
 590    "codemirror_mode": {
 591     "name": "ipython",
 592     "version": 3
 593    },
 594    "file_extension": ".py",
 595    "mimetype": "text/x-python",
 596    "name": "python",
 597    "nbconvert_exporter": "python",
 598    "pygments_lexer": "ipython3",
 599    "version": "3.5.2"
 600   }
 601  },
 602  "nbformat": 4,
 603  "nbformat_minor": 1
 604 }