X-Git-Url: https://git.njae.me.uk/?a=blobdiff_plain;f=monotone-sequences%2Fsingle_sequence-itertools.ipynb;fp=monotone-sequences%2Fsingle_sequence-itertools.ipynb;h=111b7befad72d5256806c6f44b2b3dfc3b3d4c01;hb=e70f19374b89d58b52e4cf3b9b2f41aac7c0884b;hp=0000000000000000000000000000000000000000;hpb=335b6630be1dbcfba9f1d84bea26cf8b657512c4;p=ou-summer-of-code-2017.git diff --git a/monotone-sequences/single_sequence-itertools.ipynb b/monotone-sequences/single_sequence-itertools.ipynb new file mode 100644 index 0000000..111b7be --- /dev/null +++ b/monotone-sequences/single_sequence-itertools.ipynb @@ -0,0 +1,444 @@ +{ + "cells": [ + { + "cell_type": "code", + "execution_count": 2, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "import itertools" + ] + }, + { + "cell_type": "code", + "execution_count": 13, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "def cmp(x, y):\n", + " if x == y:\n", + " return 0\n", + " elif x > y:\n", + " return -1\n", + " else:\n", + " return 1" + ] + }, + { + "cell_type": "code", + "execution_count": 110, + "metadata": { + "collapsed": false + }, + "outputs": [], + "source": [ + "def longest_monotone(seq, allow_same=False, debug=False):\n", + " \"\"\"Find the longest monotonic sequence. If allow_same is True, \n", + " instead find the longest non-decreasing or non-increasing sequence\"\"\"\n", + " cmps = [cmp(x, y) for x, y in zip(seq, seq[1:])]\n", + " groups = [(k, len(list(g)) + 1) for k, g in itertools.groupby(cmps)]\n", + " if allow_same:\n", + " groups = merged(groups)\n", + " if debug:\n", + " return max(t[1] for t in groups), groups\n", + " else:\n", + " return max(t[1] for t in groups)" + ] + }, + { + "cell_type": "code", + "execution_count": 85, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "def merged(gs):\n", + " padded = gs + [(0, 0)]\n", + " mgs = []\n", + " prev = (0, 1)\n", + " for curr, nxt in zip(padded, padded[1:]):\n", + " if prev[0] == 0:\n", + " prev = (curr[0], prev[1] + curr[1] - 1)\n", + " elif curr[0] == 0:\n", + " prev = (prev[0], prev[1] + curr[1] - 1)\n", + " if prev[0] != nxt[0]:\n", + " mgs += [prev]\n", + " prev = (0, curr[1])\n", + " elif prev[0] == curr[0]:\n", + " prev = (prev[0], prev[1] + curr[1] - 1)\n", + " else:\n", + " mgs += [prev]\n", + " prev = curr\n", + " mgs += [prev]\n", + " return mgs " + ] + }, + { + "cell_type": "code", + "execution_count": 111, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "5" + ] + }, + "execution_count": 111, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "longest_monotone([1,2,3,4,5,4,5,6])" + ] + }, + { + "cell_type": "code", + "execution_count": 112, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "(5, [(1, 5), (-1, 2), (1, 3)])" + ] + }, + "execution_count": 112, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "longest_monotone([1,2,3,4,5,4,5,6], debug=True)" + ] + }, + { + "cell_type": "code", + "execution_count": 102, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "5" + ] + }, + "execution_count": 102, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "longest_monotone([10,1,2,3,4,5,4,5,6])" + ] + }, + { + "cell_type": "code", + "execution_count": 103, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "5" + ] + }, + "execution_count": 103, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "longest_monotone([10,1,2,3,4,5,5,5,4,3,5,6])" + ] + }, + { + "cell_type": "code", + "execution_count": 104, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "7" + ] + }, + "execution_count": 104, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "longest_monotone([10,1,2,3,4,5,5,5,4,3,5,6], allow_same=True)" + ] + }, + { + "cell_type": "code", + "execution_count": 105, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "5" + ] + }, + "execution_count": 105, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "longest_monotone([10,1,2,5,5,5,4,3,2,1,5,6])" + ] + }, + { + "cell_type": "code", + "execution_count": 106, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "7" + ] + }, + "execution_count": 106, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "longest_monotone([10,1,2,5,5,5,4,3,2,1,5,6], allow_same=True)" + ] + }, + { + "cell_type": "code", + "execution_count": 107, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "7" + ] + }, + "execution_count": 107, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "longest_monotone([10,1,2,5,5,5,4,3,2,5,6,6,6,6,6,6,6,2])" + ] + }, + { + "cell_type": "code", + "execution_count": 108, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "9" + ] + }, + "execution_count": 108, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "longest_monotone([10,1,2,5,5,5,4,3,2,5,6,6,6,6,6,6,6,2], allow_same=True)" + ] + }, + { + "cell_type": "code", + "execution_count": 109, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "7" + ] + }, + "execution_count": 109, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "longest_monotone([10,1,2,5,5,5,6,7,7,8,8,3,2,5,6,6,6,6,6,6,6,2], allow_same=False)" + ] + }, + { + "cell_type": "code", + "execution_count": 113, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "10" + ] + }, + "execution_count": 113, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "longest_monotone([10,1,2,5,5,5,6,7,7,8,8,3,2,5,6,6,6,6,6,6,6,2], allow_same=True)" + ] + }, + { + "cell_type": "code", + "execution_count": 114, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "0 24\n" + ] + } + ], + "source": [ + "for i in range(1):\n", + " with open('sequence{:03}.txt'.format(i)) as f:\n", + " sseq = f.read()\n", + " seq = [int(s) for s in sseq.split(',')]\n", + " s = longest_monotone(seq)\n", + " print(i, s)" + ] + }, + { + "cell_type": "code", + "execution_count": 115, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "0 24\n", + "1 34\n", + "2 23\n", + "3 23\n", + "4 22\n", + "5 27\n", + "6 27\n", + "7 24\n", + "8 22\n", + "9 21\n" + ] + } + ], + "source": [ + "for i in range(10):\n", + " with open('sequence{:03}.txt'.format(i)) as f:\n", + " sseq = f.read()\n", + " seq = [int(s) for s in sseq.split(',')]\n", + " s = longest_monotone(seq)\n", + " print(i, s)" + ] + }, + { + "cell_type": "code", + "execution_count": 116, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "0 29\n", + "1 34\n", + "2 25\n", + "3 30\n", + "4 29\n", + "5 27\n", + "6 27\n", + "7 28\n", + "8 23\n", + "9 26\n" + ] + } + ], + "source": [ + "for i in range(10):\n", + " with open('sequence{:03}.txt'.format(i)) as f:\n", + " sseq = f.read()\n", + " seq = [int(s) for s in sseq.split(',')]\n", + " s = longest_monotone(seq, allow_same=True)\n", + " print(i, s)" + ] + }, + { + "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": 0 +}