From: Neil Smith Date: Wed, 28 Jun 2017 13:49:31 +0000 (+0100) Subject: Started on the DP problem X-Git-Url: https://git.njae.me.uk/?p=ou-summer-of-code-2017.git;a=commitdiff_plain;h=63b5f6c0b7b6c18464cce2bc888cf26491b5e603 Started on the DP problem --- diff --git a/09-resolving-the-bill/interleaving.ipynb b/09-resolving-the-bill/interleaving.ipynb new file mode 100644 index 0000000..22140c9 --- /dev/null +++ b/09-resolving-the-bill/interleaving.ipynb @@ -0,0 +1,520 @@ +{ + "cells": [ + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "# Interleaved strings\n", + "\n", + "Given two strings a and b and a target c, could c be formed form some interleaving/merge of a and b?\n", + "\n", + "For example,\n", + "Given:\n", + "s1 = \"aabcc\",\n", + "s2 = \"dbbca\",\n", + "\n", + "When s3 = \"aadbbcbcac\", return true.\n", + "When s3 = \"aadbbbaccc\", return false." + ] + }, + { + "cell_type": "code", + "execution_count": 2, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "s1 = \"aabcc\"\n", + "s2 = \"dbbca\"\n", + "\n", + "s3t = \"aadbbcbcac\"\n", + "s3f = \"aadbbbaccc\"" + ] + }, + { + "cell_type": "code", + "execution_count": 8, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "[(0, ''), (1, 'a'), (2, 'aa'), (3, 'aab'), (4, 'aabc'), (5, 'aabcc')]" + ] + }, + "execution_count": 8, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "[(i, s1[:i]) for i in range(len(s1)+1)]" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "`dp_table[i, j]` is True if `s3[:i+j]` can be formed from interleaving `s1[:i]` and `s2[:j]`." + ] + }, + { + "cell_type": "code", + "execution_count": 11, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "[[True, False, False, False, False, False],\n", + " [False, False, False, False, False, False],\n", + " [False, False, False, False, False, False],\n", + " [False, False, False, False, False, False],\n", + " [False, False, False, False, False, False],\n", + " [False, False, False, False, False, False]]" + ] + }, + "execution_count": 11, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "dp_table = [[False] * (len(s1) + 1) for _ in range(len(s2) + 1)]\n", + "dp_table[0][0] = True\n", + "dp_table" + ] + }, + { + "cell_type": "code", + "execution_count": 24, + "metadata": { + "collapsed": false, + "scrolled": true + }, + "outputs": [ + { + "data": { + "text/plain": [ + "{(0, 0): False,\n", + " (0, 1): False,\n", + " (0, 2): False,\n", + " (0, 3): False,\n", + " (0, 4): False,\n", + " (0, 5): False,\n", + " (1, 0): False,\n", + " (1, 1): False,\n", + " (1, 2): False,\n", + " (1, 3): False,\n", + " (1, 4): False,\n", + " (1, 5): False,\n", + " (2, 0): False,\n", + " (2, 1): False,\n", + " (2, 2): False,\n", + " (2, 3): False,\n", + " (2, 4): False,\n", + " (2, 5): False,\n", + " (3, 0): False,\n", + " (3, 1): False,\n", + " (3, 2): False,\n", + " (3, 3): False,\n", + " (3, 4): False,\n", + " (3, 5): False,\n", + " (4, 0): False,\n", + " (4, 1): False,\n", + " (4, 2): False,\n", + " (4, 3): False,\n", + " (4, 4): False,\n", + " (4, 5): False,\n", + " (5, 0): False,\n", + " (5, 1): False,\n", + " (5, 2): False,\n", + " (5, 3): False,\n", + " (5, 4): False,\n", + " (5, 5): False}" + ] + }, + "execution_count": 24, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "dp_table = {(i, j): False\n", + " for i in range(len(s1)+1)\n", + " for j in range(len(s2)+1)}\n", + "dp_table" + ] + }, + { + "cell_type": "code", + "execution_count": 25, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "def show_table(table):\n", + " return '\\n'.join(\n", + " ' '.join(str(table[i, j])[0] for j in sorted(set([k[1] for k in table])))\n", + " for i in sorted(set([k[0] for k in table]))) " + ] + }, + { + "cell_type": "code", + "execution_count": 26, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "F F F F F F\n", + "F F F F F F\n", + "F F F F F F\n", + "F F F F F F\n", + "F F F F F F\n", + "F F F F F F\n" + ] + } + ], + "source": [ + "print(show_table(dp_table))" + ] + }, + { + "cell_type": "code", + "execution_count": 39, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "aabcc dbbca aadbbbaccc\n", + "aa 0 0 ! ! ! True\n", + "s2 0 1 ! d a False\n", + "s2 0 2 ! b a False\n", + "s2 0 3 ! b d False\n", + "s2 0 4 ! c b False\n", + "s2 0 5 ! a b False\n", + "s1 1 0 a ! a True\n", + "xx 1 1 a d a False\n", + "xx 1 2 a b d False\n", + "xx 1 3 a b b False\n", + "xx 1 4 a c b False\n", + "xx 1 5 a a b False\n", + "s1 2 0 a ! a True\n", + "s2 2 1 a d d True\n", + "s2 2 2 a b b True\n", + "s2 2 3 a b b True\n", + "xx 2 4 a c b False\n", + "xx 2 5 a a a False\n", + "s1 3 0 b ! d False\n", + "s1 3 1 b d b True\n", + "s2 3 2 b b b True\n", + "s1 3 2 b b b True\n", + "s2 3 3 b b b True\n", + "s1 3 3 b b b True\n", + "xx 3 4 b c a False\n", + "xx 3 5 b a c False\n", + "s1 4 0 c ! b False\n", + "xx 4 1 c d b False\n", + "xx 4 2 c b b False\n", + "xx 4 3 c b a False\n", + "xx 4 4 c c c False\n", + "xx 4 5 c a c False\n", + "s1 5 0 c ! b False\n", + "xx 5 1 c d b False\n", + "xx 5 2 c b a False\n", + "xx 5 3 c b c False\n", + "xx 5 4 c c c False\n", + "xx 5 5 c a c False\n", + "T F F F F F\n", + "T F F F F F\n", + "T T T T F F\n", + "F T T T F F\n", + "F F F F F F\n", + "F F F F F F\n" + ] + }, + { + "data": { + "text/plain": [ + "{(1, 0): (0, 0, 'a', 's1'),\n", + " (2, 0): (1, 0, 'a', 's1'),\n", + " (2, 1): (2, 0, 'd', 's2'),\n", + " (2, 2): (2, 1, 'b', 's2'),\n", + " (2, 3): (2, 2, 'b', 's2'),\n", + " (3, 1): (2, 1, 'b', 's1'),\n", + " (3, 2): (2, 2, 'b', 's1'),\n", + " (3, 3): (2, 3, 'b', 's1')}" + ] + }, + "execution_count": 39, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "s3 = s3f\n", + "\n", + "print(s1, s2, s3)\n", + "\n", + "dp_table = {(i, j): False\n", + " for i in range(len(s1)+1)\n", + " for j in range(len(s2)+1)}\n", + "\n", + "backpointers = {}\n", + "\n", + "for i in range(len(s1)+1):\n", + " for j in range(len(s2)+1):\n", + " if i == 0 and j == 0:\n", + " dp_table[i, j] = True\n", + " print('aa', i, j, '!', '!', '!', dp_table[i, j])\n", + " elif i == 0:\n", + " # extend by character from s2\n", + " if dp_table[i, j-1] and s2[j-1] == s3[i+j-1]:\n", + " dp_table[i, j] = True\n", + " backpointers[i, j] = (i, j-1, s2[j-1], 's2')\n", + " print('s2', i, j, '!', s2[j-1], s3[i+j-1], dp_table[i, j])\n", + " elif j == 0:\n", + " # extend by character from s1\n", + " if dp_table[i-1, j] and s1[i-1] == s3[i+j-1]:\n", + " dp_table[i, j] = True\n", + " backpointers[i, j] = (i-1, j, s1[i-1], 's1')\n", + " print('s1', i, j, s1[i-1], '!', s3[i+j-1], dp_table[i, j])\n", + " else:\n", + " # extend by character from s2\n", + " if dp_table[i, j-1] and s2[j-1] == s3[i+j-1]:\n", + " dp_table[i, j] = True\n", + " backpointers[i, j] = (i, j-1, s2[j-1], 's2')\n", + " print('s2', i, j, s1[i-1], s2[j-1], s3[i+j-1], dp_table[i, j]) \n", + " # extend by character from s1\n", + " if dp_table[i-1, j] and s1[i-1] == s3[i+j-1]:\n", + " dp_table[i, j] = True\n", + " backpointers[i, j] = (i-1, j, s1[i-1], 's1') \n", + " print('s1', i, j, s1[i-1], s2[j-1], s3[i+j-1], dp_table[i, j])\n", + " if not dp_table[i, j]:\n", + " print('xx', i, j, s1[i-1], s2[j-1], s3[i+j-1], dp_table[i, j])\n", + "\n", + "print(show_table(dp_table))\n", + "backpointers" + ] + }, + { + "cell_type": "code", + "execution_count": 49, + "metadata": { + "collapsed": false + }, + "outputs": [], + "source": [ + "def is_interleave(seq1, seq2, seq3, return_backpointers=False, debug=False):\n", + " \"\"\"Return true if seq3 is some interleaved merge of seq1 and seq2.\n", + " If return_backpointers, also return the set of backpointers to\n", + " reconstruct the interleaving\"\"\"\n", + " \n", + " # dp_table[i, j] is True if seq3[:i+j-1] is made up of an interleaving\n", + " # of the first i characters of seq1 and the first j characters of seq2\n", + " \n", + " if len(seq1) + len(seq2) != len(seq3):\n", + " if return_backpointers:\n", + " return False, {}\n", + " else:\n", + " return False\n", + " \n", + " dp_table = {(i, j): False\n", + " for i in range(len(seq1)+1)\n", + " for j in range(len(seq2)+1)}\n", + "\n", + " backpointers = {}\n", + "\n", + " for i in range(len(seq1)+1):\n", + " for j in range(len(seq2)+1):\n", + " if i == 0 and j == 0:\n", + " dp_table[i, j] = True\n", + " if debug: print('aa', i, j, '!', '!', '!', dp_table[i, j])\n", + " elif i == 0:\n", + " # extend by character from seq2\n", + " if dp_table[i, j-1] and seq2[j-1] == seq3[i+j-1]:\n", + " dp_table[i, j] = True\n", + " backpointers[i, j] = (i, j-1, seq2[j-1], 'seq2')\n", + " if debug: print('seq2', i, j, '!', seq2[j-1], seq3[i+j-1], dp_table[i, j])\n", + " elif j == 0:\n", + " # extend by character from seq1\n", + " if dp_table[i-1, j] and seq1[i-1] == seq3[i+j-1]:\n", + " dp_table[i, j] = True\n", + " backpointers[i, j] = (i-1, j, seq1[i-1], 'seq1')\n", + " if debug: print('seq1', i, j, seq1[i-1], '!', seq3[i+j-1], dp_table[i, j])\n", + " else:\n", + " # extend by character from seq2\n", + " if dp_table[i, j-1] and seq2[j-1] == seq3[i+j-1]:\n", + " dp_table[i, j] = True\n", + " backpointers[i, j] = (i, j-1, seq2[j-1], 'seq2')\n", + " if debug: print('seq2', i, j, seq1[i-1], seq2[j-1], seq3[i+j-1], dp_table[i, j]) \n", + " # extend by character from seq1\n", + " if dp_table[i-1, j] and seq1[i-1] == seq3[i+j-1]:\n", + " dp_table[i, j] = True\n", + " backpointers[i, j] = (i-1, j, seq1[i-1], 'seq1') \n", + " if debug: print('seq1', i, j, seq1[i-1], seq2[j-1], seq3[i+j-1], dp_table[i, j])\n", + " if not dp_table[i, j]:\n", + " if debug: print('xx', i, j, seq1[i-1], seq2[j-1], seq3[i+j-1], dp_table[i, j])\n", + "\n", + " if return_backpointers:\n", + " return dp_table[len(seq1), len(seq2)], backpointers\n", + " else:\n", + " return dp_table[len(seq1), len(seq2)]" + ] + }, + { + "cell_type": "code", + "execution_count": 50, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "True" + ] + }, + "execution_count": 50, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "is_interleave(s1, s2, s3t)" + ] + }, + { + "cell_type": "code", + "execution_count": 51, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "(True,\n", + " {(1, 0): (0, 0, 'a', 'seq1'),\n", + " (2, 0): (1, 0, 'a', 'seq1'),\n", + " (2, 1): (2, 0, 'd', 'seq2'),\n", + " (2, 2): (2, 1, 'b', 'seq2'),\n", + " (2, 3): (2, 2, 'b', 'seq2'),\n", + " (2, 4): (2, 3, 'c', 'seq2'),\n", + " (3, 1): (2, 1, 'b', 'seq1'),\n", + " (3, 2): (2, 2, 'b', 'seq1'),\n", + " (3, 4): (2, 4, 'b', 'seq1'),\n", + " (4, 2): (3, 2, 'c', 'seq1'),\n", + " (4, 3): (4, 2, 'b', 'seq2'),\n", + " (4, 4): (3, 4, 'c', 'seq1'),\n", + " (4, 5): (4, 4, 'a', 'seq2'),\n", + " (5, 3): (4, 3, 'c', 'seq1'),\n", + " (5, 5): (4, 5, 'c', 'seq1')})" + ] + }, + "execution_count": 51, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "is_interleave(s1, s2, s3t, return_backpointers=True)" + ] + }, + { + "cell_type": "code", + "execution_count": 52, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "False" + ] + }, + "execution_count": 52, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "is_interleave(s1, s2, s3f)" + ] + }, + { + "cell_type": "code", + "execution_count": 54, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "(True,\n", + " {(1, 0): (0, 0, 'a', 'seq1'),\n", + " (2, 0): (1, 0, 'a', 'seq1'),\n", + " (3, 0): (2, 0, 'a', 'seq1'),\n", + " (3, 1): (3, 0, 'b', 'seq2'),\n", + " (4, 1): (3, 1, 'a', 'seq1'),\n", + " (4, 2): (4, 1, 'b', 'seq2'),\n", + " (4, 3): (4, 2, 'b', 'seq2')})" + ] + }, + "execution_count": 54, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "is_interleave('aaaa', 'bbb', 'aaababb', return_backpointers=True)" + ] + }, + { + "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 +} diff --git a/09-resolving-the-bill/tipping-solution.ipynb b/09-resolving-the-bill/tipping-solution.ipynb new file mode 100644 index 0000000..7635c18 --- /dev/null +++ b/09-resolving-the-bill/tipping-solution.ipynb @@ -0,0 +1,604 @@ +{ + "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 +}