4 "cell_type": "markdown",
7 "# How much do you tip the staff?\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",
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"
42 "output_type": "execute_result"
46 "ratings = [random.randrange(1, 10) for _ in range(5)]\n",
65 "output_type": "execute_result"
69 "payments = [1] * len(ratings)\n",
88 "output_type": "execute_result"
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",
102 "execution_count": 5,
113 "execution_count": 5,
115 "output_type": "execute_result"
119 "[i for i in reversed(range(len(payments)-1))]"
124 "execution_count": 6,
135 "execution_count": 6,
137 "output_type": "execute_result"
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",
151 "execution_count": 7,
157 "def payments_dp(ratings):\n",
158 " payments = [1] * len(ratings)\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",
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",
177 "execution_count": 8,
188 "execution_count": 8,
190 "output_type": "execute_result"
194 "payments_dp(ratings)"
199 "execution_count": 14,
228 " [2, 1, 3, 2, 1, 2, 1, 3, 2, 1, 2, 5, 4, 3, 2, 1, 2, 1, 2, 1])"
231 "execution_count": 14,
233 "output_type": "execute_result"
237 "ratings = [random.randrange(1, 100) for _ in range(20)]\n",
238 "ratings, payments_dp(ratings)"
243 "execution_count": 10,
251 "[1, 2, 3, 4, 5, 6, 7]"
254 "execution_count": 10,
256 "output_type": "execute_result"
260 "payments_dp([1,2,3,4,5,6,7])"
265 "execution_count": 37,
271 "def is_valid(ratings, payments):\n",
273 " for i in range(len(ratings)):\n",
275 " left_r = ratings[i]\n",
276 " left_p = payments[i]\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",
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",
289 " elif ratings[i] == left_r and payments[i] != left_p:\n",
291 " elif ratings[i] < left_r and payments[i] >= left_p:\n",
293 " if ratings[i] > right_r and payments[i] <= right_p:\n",
295 " elif ratings[i] == right_r and payments[i] != right_p:\n",
297 " elif ratings[i] < right_r and payments[i] >= right_p:\n",
305 "execution_count": 38,
316 "execution_count": 38,
318 "output_type": "execute_result"
322 "is_valid(ratings, [1]*len(ratings))"
327 "execution_count": 39,
338 "execution_count": 39,
340 "output_type": "execute_result"
344 "is_valid(ratings, payments_dp(ratings))"
349 "execution_count": 40,
355 "def payments_naive(ratings):\n",
356 " payments = [1] * len(ratings)\n",
359 " changes = False\n",
360 " for i in range(len(ratings)):\n",
362 " left_r = ratings[i]\n",
363 " left_p = payments[i]\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",
371 " right_r = ratings[i+1]\n",
372 " right_p = payments[i+1]\n",
374 " if ratings[i] > left_r and payments[i] <= left_p:\n",
375 " payments[i] = left_p + 1\n",
377 " elif ratings[i] == left_r and payments[i] != left_p:\n",
378 " payments[i] = left_p\n",
380 " elif ratings[i] > right_r and payments[i] <= right_p:\n",
381 " payments[i] = right_p + 1\n",
383 " elif ratings[i] == right_r and payments[i] != right_p:\n",
384 " payments[i] = right_p\n",
392 "execution_count": 41,
400 "[2, 1, 3, 2, 1, 2, 1, 3, 2, 1, 2, 5, 4, 3, 2, 1, 2, 1, 2, 1]"
403 "execution_count": 41,
405 "output_type": "execute_result"
409 "payments_naive(ratings)"
414 "execution_count": 42,
422 "[2, 1, 3, 2, 1, 2, 1, 3, 2, 1, 2, 5, 4, 3, 2, 1, 2, 1, 2, 1]"
425 "execution_count": 42,
427 "output_type": "execute_result"
431 "payments_dp(ratings)"
436 "execution_count": 43,
444 "[76, 34, 76, 40, 14, 91, 88, 96, 14, 1, 22, 97, 75, 59, 27, 24, 96, 70, 79, 3]"
447 "execution_count": 43,
449 "output_type": "execute_result"
458 "execution_count": 44,
469 "execution_count": 44,
471 "output_type": "execute_result"
475 "is_valid(ratings, payments_naive(ratings))"
480 "execution_count": 55,
486 "ratings = [random.randrange(1, 100) for _ in range(10**7)]"
491 "execution_count": 56,
502 "execution_count": 56,
504 "output_type": "execute_result"
508 "is_valid(ratings, payments_naive(ratings))"
513 "execution_count": 57,
524 "execution_count": 57,
526 "output_type": "execute_result"
530 "is_valid(ratings, payments_dp(ratings))"
535 "execution_count": 58,
542 "output_type": "stream",
544 "1 loop, best of 3: 1min 17s per loop\n"
550 "payments_naive(ratings)"
555 "execution_count": 59,
562 "output_type": "stream",
564 "1 loop, best of 3: 7.77 s per loop\n"
570 "payments_dp(ratings)"
575 "execution_count": null,
585 "display_name": "Python 3",
586 "language": "python",
594 "file_extension": ".py",
595 "mimetype": "text/x-python",
597 "nbconvert_exporter": "python",
598 "pygments_lexer": "ipython3",