16 "execution_count": 13,
33 "execution_count": 110,
39 "def longest_monotone(seq, allow_same=False, debug=False):\n",
40 " \"\"\"Find the longest monotonic sequence. If allow_same is True, \n",
41 " instead find the longest non-decreasing or non-increasing sequence\"\"\"\n",
42 " cmps = [cmp(x, y) for x, y in zip(seq, seq[1:])]\n",
43 " groups = [(k, len(list(g)) + 1) for k, g in itertools.groupby(cmps)]\n",
45 " groups = merged(groups)\n",
47 " return max(t[1] for t in groups), groups\n",
49 " return max(t[1] for t in groups)"
54 "execution_count": 85,
61 " padded = gs + [(0, 0)]\n",
64 " for curr, nxt in zip(padded, padded[1:]):\n",
65 " if prev[0] == 0:\n",
66 " prev = (curr[0], prev[1] + curr[1] - 1)\n",
67 " elif curr[0] == 0:\n",
68 " prev = (prev[0], prev[1] + curr[1] - 1)\n",
69 " if prev[0] != nxt[0]:\n",
71 " prev = (0, curr[1])\n",
72 " elif prev[0] == curr[0]:\n",
73 " prev = (prev[0], prev[1] + curr[1] - 1)\n",
83 "execution_count": 111,
94 "execution_count": 111,
96 "output_type": "execute_result"
100 "longest_monotone([1,2,3,4,5,4,5,6])"
105 "execution_count": 112,
113 "(5, [(1, 5), (-1, 2), (1, 3)])"
116 "execution_count": 112,
118 "output_type": "execute_result"
122 "longest_monotone([1,2,3,4,5,4,5,6], debug=True)"
127 "execution_count": 102,
138 "execution_count": 102,
140 "output_type": "execute_result"
144 "longest_monotone([10,1,2,3,4,5,4,5,6])"
149 "execution_count": 103,
160 "execution_count": 103,
162 "output_type": "execute_result"
166 "longest_monotone([10,1,2,3,4,5,5,5,4,3,5,6])"
171 "execution_count": 104,
182 "execution_count": 104,
184 "output_type": "execute_result"
188 "longest_monotone([10,1,2,3,4,5,5,5,4,3,5,6], allow_same=True)"
193 "execution_count": 105,
204 "execution_count": 105,
206 "output_type": "execute_result"
210 "longest_monotone([10,1,2,5,5,5,4,3,2,1,5,6])"
215 "execution_count": 106,
226 "execution_count": 106,
228 "output_type": "execute_result"
232 "longest_monotone([10,1,2,5,5,5,4,3,2,1,5,6], allow_same=True)"
237 "execution_count": 107,
248 "execution_count": 107,
250 "output_type": "execute_result"
254 "longest_monotone([10,1,2,5,5,5,4,3,2,5,6,6,6,6,6,6,6,2])"
259 "execution_count": 108,
270 "execution_count": 108,
272 "output_type": "execute_result"
276 "longest_monotone([10,1,2,5,5,5,4,3,2,5,6,6,6,6,6,6,6,2], allow_same=True)"
281 "execution_count": 109,
292 "execution_count": 109,
294 "output_type": "execute_result"
298 "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)"
303 "execution_count": 113,
314 "execution_count": 113,
316 "output_type": "execute_result"
320 "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)"
325 "execution_count": 114,
332 "output_type": "stream",
339 "for i in range(1):\n",
340 " with open('sequence{:03}.txt'.format(i)) as f:\n",
341 " sseq = f.read()\n",
342 " seq = [int(s) for s in sseq.split(',')]\n",
343 " s = longest_monotone(seq)\n",
349 "execution_count": 115,
356 "output_type": "stream",
372 "for i in range(10):\n",
373 " with open('sequence{:03}.txt'.format(i)) as f:\n",
374 " sseq = f.read()\n",
375 " seq = [int(s) for s in sseq.split(',')]\n",
376 " s = longest_monotone(seq)\n",
382 "execution_count": 116,
389 "output_type": "stream",
405 "for i in range(10):\n",
406 " with open('sequence{:03}.txt'.format(i)) as f:\n",
407 " sseq = f.read()\n",
408 " seq = [int(s) for s in sseq.split(',')]\n",
409 " s = longest_monotone(seq, allow_same=True)\n",
415 "execution_count": null,
425 "display_name": "Python 3",
426 "language": "python",
434 "file_extension": ".py",
435 "mimetype": "text/x-python",
437 "nbconvert_exporter": "python",
438 "pygments_lexer": "ipython3",