{ "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 }