+++ /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