4 "cell_type": "markdown",
7 "# Monotone substrings\n",
9 "Given a list of numbers, find the length of longest increasing or decreasing substring in the list.\n",
11 "For instance, the sequence\n",
12 " 10, 1, 2, 3, 4, 5, 5, 5, 6, 4, 3, 5, 6\n",
13 "contains these increasing or decreasing substrings:\n",
20 "As an extension, allow the substring to contain runs of identical numbers, each of which is included in the length of the longest substring.\n",
22 "If identical numbers are allowed, the above sequence contains substrings:\n",
24 "* 1, 2, 3, 4, 5, 5, 5, 6\n",
28 "The list is given as a single line of comma-separated integers. "
39 "def longest_monotone(seq, allow_same=False, debug=False):\n",
40 " \"\"\"Find the longest monotonic substring. If allow_same is True, \n",
41 " instead find the longest non-decreasing or non-increasing substring\"\"\"\n",
42 " longest_length = 0\n",
43 " current_length = 1\n",
44 " current_same = 0\n",
45 " current_increasing = True\n",
46 " for (last, this) in zip(seq, seq[1:]):\n",
47 " if this == last:\n",
49 " current_length += 1\n",
50 " current_same += 1\n",
52 " current_length = 1\n",
53 " elif this > last:\n",
54 " if current_increasing:\n",
55 " current_length += 1\n",
57 " current_length = 2 + current_same\n",
58 " current_increasing = True\n",
59 " current_same = 0\n",
60 " elif this < last:\n",
61 " if not current_increasing:\n",
62 " current_length += 1\n",
64 " current_length = 2 + current_same\n",
65 " current_increasing = False\n",
66 " current_same = 0\n",
67 " if current_length > longest_length:\n",
68 " longest_length = current_length\n",
70 " if last < this: cmp = '<'\n",
71 " if last > this: cmp = '>'\n",
72 " if last == this: cmp = '='\n",
73 " print('{:4} {}\\t{}\\t{}\\t{}'.format(current_length, current_increasing, last, cmp, this))\n",
74 " return longest_length "
86 "output_type": "stream",
92 " 2 False\t5\t>\t4\n",
103 "execution_count": 2,
105 "output_type": "execute_result"
109 "longest_monotone([1,2,3,4,5,4,5,6], debug=True)"
114 "execution_count": 3,
121 "output_type": "stream",
123 " 2 False\t10\t>\t1\n",
124 " 2 True\t1\t<\t2\n",
125 " 3 True\t2\t<\t3\n",
126 " 4 True\t3\t<\t4\n",
127 " 5 True\t4\t<\t5\n",
128 " 2 False\t5\t>\t4\n",
129 " 2 True\t4\t<\t5\n",
139 "execution_count": 3,
141 "output_type": "execute_result"
145 "longest_monotone([10,1,2,3,4,5,4,5,6], debug=True)"
150 "execution_count": 8,
157 "output_type": "stream",
159 " 2 False\t10\t>\t1\n",
160 " 2 True\t1\t<\t2\n",
161 " 3 True\t2\t<\t3\n",
162 " 4 True\t3\t<\t4\n",
163 " 5 True\t4\t<\t5\n",
164 " 1 True\t5\t=\t5\n",
165 " 1 True\t5\t=\t5\n",
166 " 2 False\t5\t>\t4\n",
167 " 3 False\t4\t>\t3\n",
168 " 2 True\t3\t<\t5\n",
178 "execution_count": 8,
180 "output_type": "execute_result"
184 "longest_monotone([10,1,2,3,4,5,5,5,4,3,5,6], debug=True)"
189 "execution_count": 9,
196 "output_type": "stream",
198 " 2 False\t10\t>\t1\n",
199 " 2 True\t1\t<\t2\n",
200 " 3 True\t2\t<\t3\n",
201 " 4 True\t3\t<\t4\n",
202 " 5 True\t4\t<\t5\n",
203 " 1 True\t5\t=\t5\n",
204 " 1 True\t5\t=\t5\n",
205 " 2 True\t5\t<\t6\n",
206 " 2 False\t6\t>\t4\n",
207 " 3 False\t4\t>\t3\n",
208 " 2 True\t3\t<\t5\n",
218 "execution_count": 9,
220 "output_type": "execute_result"
224 "longest_monotone([10,1,2,3,4,5,5,5,6,4,3,5,6], debug=True)"
229 "execution_count": 7,
236 "output_type": "stream",
238 " 2 False\t10\t>\t1\n",
239 " 2 True\t1\t<\t2\n",
240 " 3 True\t2\t<\t3\n",
241 " 4 True\t3\t<\t4\n",
242 " 5 True\t4\t<\t5\n",
243 " 6 True\t5\t=\t5\n",
244 " 7 True\t5\t=\t5\n",
245 " 8 True\t5\t<\t6\n",
246 " 2 False\t6\t>\t4\n",
247 " 3 False\t4\t>\t3\n",
248 " 2 True\t3\t<\t5\n",
258 "execution_count": 7,
260 "output_type": "execute_result"
264 "longest_monotone([10,1,2,3,4,5,5,5,6,4,3,5,6], allow_same=True, debug=True)"
269 "execution_count": 6,
276 "output_type": "stream",
278 " 2 False\t10\t>\t1\n",
279 " 2 True\t1\t<\t2\n",
280 " 3 True\t2\t<\t5\n",
281 " 4 True\t5\t=\t5\n",
282 " 5 True\t5\t=\t5\n",
283 " 4 False\t5\t>\t4\n",
284 " 5 False\t4\t>\t3\n",
285 " 6 False\t3\t>\t2\n",
286 " 7 False\t2\t>\t1\n",
287 " 2 True\t1\t<\t5\n",
297 "execution_count": 6,
299 "output_type": "execute_result"
303 "longest_monotone([10,1,2,5,5,5,4,3,2,1,5,6], allow_same=True, debug=True)"
308 "execution_count": 7,
315 "output_type": "stream",
317 " 2 False\t10\t>\t1\n",
318 " 2 True\t1\t<\t2\n",
319 " 3 True\t2\t<\t5\n",
320 " 4 True\t5\t=\t5\n",
321 " 5 True\t5\t=\t5\n",
322 " 4 False\t5\t>\t4\n",
323 " 5 False\t4\t>\t3\n",
324 " 6 False\t3\t>\t2\n",
325 " 2 True\t2\t<\t5\n",
326 " 3 True\t5\t<\t6\n",
327 " 4 True\t6\t=\t6\n",
328 " 5 True\t6\t=\t6\n",
329 " 6 True\t6\t=\t6\n",
330 " 7 True\t6\t=\t6\n",
331 " 8 True\t6\t=\t6\n",
332 " 9 True\t6\t=\t6\n",
333 " 8 False\t6\t>\t2\n"
342 "execution_count": 7,
344 "output_type": "execute_result"
348 "longest_monotone([10,1,2,5,5,5,4,3,2,5,6,6,6,6,6,6,6,2], allow_same=True, debug=True)"
353 "execution_count": 8,
360 "output_type": "stream",
362 " 2 False\t10\t>\t1\n",
363 " 2 True\t1\t<\t2\n",
364 " 3 True\t2\t<\t5\n",
365 " 1 True\t5\t=\t5\n",
366 " 1 True\t5\t=\t5\n",
367 " 2 False\t5\t>\t4\n",
368 " 3 False\t4\t>\t3\n",
369 " 4 False\t3\t>\t2\n",
370 " 2 True\t2\t<\t5\n",
371 " 3 True\t5\t<\t6\n",
372 " 1 True\t6\t=\t6\n",
373 " 1 True\t6\t=\t6\n",
374 " 1 True\t6\t=\t6\n",
375 " 1 True\t6\t=\t6\n",
376 " 1 True\t6\t=\t6\n",
377 " 1 True\t6\t=\t6\n",
378 " 2 False\t6\t>\t2\n"
387 "execution_count": 8,
389 "output_type": "execute_result"
393 "longest_monotone([10,1,2,5,5,5,4,3,2,5,6,6,6,6,6,6,6,2], allow_same=False, debug=True)"
398 "execution_count": null,
404 "# for i in range(1):\n",
405 "# with open('sequence{:03}.txt'.format(i)) as f:\n",
406 "# sseq = f.read()\n",
407 "# seq = [int(s) for s in sseq.split(',')]\n",
408 "# s, l = longest_monotone(seq, debug=True)\n",
414 "execution_count": 10,
421 "output_type": "stream",
437 "for i in range(10):\n",
438 " with open('sequence{:03}.txt'.format(i)) as f:\n",
439 " sseq = f.read()\n",
440 " seq = [int(s) for s in sseq.split(',')]\n",
441 " s = longest_monotone(seq)\n",
447 "execution_count": 106,
454 "output_type": "stream",
470 "for i in range(10):\n",
471 " with open('sequence{:03}.txt'.format(i)) as f:\n",
472 " sseq = f.read()\n",
473 " seq = [int(s) for s in sseq.split(',')]\n",
474 " s = longest_monotone(seq, allow_same=True)\n",
480 "execution_count": null,
490 "display_name": "Python 3",
491 "language": "python",
499 "file_extension": ".py",
500 "mimetype": "text/x-python",
502 "nbconvert_exporter": "python",
503 "pygments_lexer": "ipython3",