--- /dev/null
+{
+ "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
+}
projects / ou-summer-of-code-2017.git / blobdiff