{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Monotone substrings\n",
"\n",
"Given a list of numbers, find the length of longest increasing or decreasing substring in the list.\n",
"\n",
"For instance, the sequence\n",
" 10, 1, 2, 3, 4, 5, 5, 5, 6, 4, 3, 5, 6\n",
"contains these increasing or decreasing substrings:\n",
"* 10, 1\n",
"* 1, 2, 3, 4, 5\n",
"* 5, 6\n",
"* 6, 4, 3\n",
"* 3, 5, 6\n",
"\n",
"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",
"\n",
"If identical numbers are allowed, the above sequence contains substrings:\n",
"* 10, 1\n",
"* 1, 2, 3, 4, 5, 5, 5, 6\n",
"* 6, 4, 3\n",
"* 3, 5, 6\n",
"\n",
"The list is given as a single line of comma-separated integers. "
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"def longest_monotone(seq, allow_same=False, debug=False):\n",
" \"\"\"Find the longest monotonic substring. If allow_same is True, \n",
" instead find the longest non-decreasing or non-increasing substring\"\"\"\n",
" longest_length = 0\n",
" current_length = 1\n",
" current_same = 0\n",
" current_increasing = True\n",
" for (last, this) in zip(seq, seq[1:]):\n",
" if this == last:\n",
" if allow_same:\n",
" current_length += 1\n",
" current_same += 1\n",
" else:\n",
" current_length = 1\n",
" elif this > last:\n",
" if current_increasing:\n",
" current_length += 1\n",
" else:\n",
" current_length = 2 + current_same\n",
" current_increasing = True\n",
" current_same = 0\n",
" elif this < last:\n",
" if not current_increasing:\n",
" current_length += 1\n",
" else:\n",
" current_length = 2 + current_same\n",
" current_increasing = False\n",
" current_same = 0\n",
" if current_length > longest_length:\n",
" longest_length = current_length\n",
" if debug:\n",
" if last < this: cmp = '<'\n",
" if last > this: cmp = '>'\n",
" if last == this: cmp = '='\n",
" print('{:4} {}\\t{}\\t{}\\t{}'.format(current_length, current_increasing, last, cmp, this))\n",
" return longest_length "
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" 2 True\t1\t<\t2\n",
" 3 True\t2\t<\t3\n",
" 4 True\t3\t<\t4\n",
" 5 True\t4\t<\t5\n",
" 2 False\t5\t>\t4\n",
" 2 True\t4\t<\t5\n",
" 3 True\t5\t<\t6\n"
]
},
{
"data": {
"text/plain": [
"5"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"longest_monotone([1,2,3,4,5,4,5,6], debug=True)"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" 2 False\t10\t>\t1\n",
" 2 True\t1\t<\t2\n",
" 3 True\t2\t<\t3\n",
" 4 True\t3\t<\t4\n",
" 5 True\t4\t<\t5\n",
" 2 False\t5\t>\t4\n",
" 2 True\t4\t<\t5\n",
" 3 True\t5\t<\t6\n"
]
},
{
"data": {
"text/plain": [
"5"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"longest_monotone([10,1,2,3,4,5,4,5,6], debug=True)"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" 2 False\t10\t>\t1\n",
" 2 True\t1\t<\t2\n",
" 3 True\t2\t<\t3\n",
" 4 True\t3\t<\t4\n",
" 5 True\t4\t<\t5\n",
" 1 True\t5\t=\t5\n",
" 1 True\t5\t=\t5\n",
" 2 False\t5\t>\t4\n",
" 3 False\t4\t>\t3\n",
" 2 True\t3\t<\t5\n",
" 3 True\t5\t<\t6\n"
]
},
{
"data": {
"text/plain": [
"5"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"longest_monotone([10,1,2,3,4,5,5,5,4,3,5,6], debug=True)"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" 2 False\t10\t>\t1\n",
" 2 True\t1\t<\t2\n",
" 3 True\t2\t<\t3\n",
" 4 True\t3\t<\t4\n",
" 5 True\t4\t<\t5\n",
" 1 True\t5\t=\t5\n",
" 1 True\t5\t=\t5\n",
" 2 True\t5\t<\t6\n",
" 2 False\t6\t>\t4\n",
" 3 False\t4\t>\t3\n",
" 2 True\t3\t<\t5\n",
" 3 True\t5\t<\t6\n"
]
},
{
"data": {
"text/plain": [
"5"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"longest_monotone([10,1,2,3,4,5,5,5,6,4,3,5,6], debug=True)"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" 2 False\t10\t>\t1\n",
" 2 True\t1\t<\t2\n",
" 3 True\t2\t<\t3\n",
" 4 True\t3\t<\t4\n",
" 5 True\t4\t<\t5\n",
" 6 True\t5\t=\t5\n",
" 7 True\t5\t=\t5\n",
" 8 True\t5\t<\t6\n",
" 2 False\t6\t>\t4\n",
" 3 False\t4\t>\t3\n",
" 2 True\t3\t<\t5\n",
" 3 True\t5\t<\t6\n"
]
},
{
"data": {
"text/plain": [
"8"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"longest_monotone([10,1,2,3,4,5,5,5,6,4,3,5,6], allow_same=True, debug=True)"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" 2 False\t10\t>\t1\n",
" 2 True\t1\t<\t2\n",
" 3 True\t2\t<\t5\n",
" 4 True\t5\t=\t5\n",
" 5 True\t5\t=\t5\n",
" 4 False\t5\t>\t4\n",
" 5 False\t4\t>\t3\n",
" 6 False\t3\t>\t2\n",
" 7 False\t2\t>\t1\n",
" 2 True\t1\t<\t5\n",
" 3 True\t5\t<\t6\n"
]
},
{
"data": {
"text/plain": [
"7"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"longest_monotone([10,1,2,5,5,5,4,3,2,1,5,6], allow_same=True, debug=True)"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" 2 False\t10\t>\t1\n",
" 2 True\t1\t<\t2\n",
" 3 True\t2\t<\t5\n",
" 4 True\t5\t=\t5\n",
" 5 True\t5\t=\t5\n",
" 4 False\t5\t>\t4\n",
" 5 False\t4\t>\t3\n",
" 6 False\t3\t>\t2\n",
" 2 True\t2\t<\t5\n",
" 3 True\t5\t<\t6\n",
" 4 True\t6\t=\t6\n",
" 5 True\t6\t=\t6\n",
" 6 True\t6\t=\t6\n",
" 7 True\t6\t=\t6\n",
" 8 True\t6\t=\t6\n",
" 9 True\t6\t=\t6\n",
" 8 False\t6\t>\t2\n"
]
},
{
"data": {
"text/plain": [
"9"
]
},
"execution_count": 7,
"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, debug=True)"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" 2 False\t10\t>\t1\n",
" 2 True\t1\t<\t2\n",
" 3 True\t2\t<\t5\n",
" 1 True\t5\t=\t5\n",
" 1 True\t5\t=\t5\n",
" 2 False\t5\t>\t4\n",
" 3 False\t4\t>\t3\n",
" 4 False\t3\t>\t2\n",
" 2 True\t2\t<\t5\n",
" 3 True\t5\t<\t6\n",
" 1 True\t6\t=\t6\n",
" 1 True\t6\t=\t6\n",
" 1 True\t6\t=\t6\n",
" 1 True\t6\t=\t6\n",
" 1 True\t6\t=\t6\n",
" 1 True\t6\t=\t6\n",
" 2 False\t6\t>\t2\n"
]
},
{
"data": {
"text/plain": [
"4"
]
},
"execution_count": 8,
"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=False, debug=True)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"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, l = longest_monotone(seq, debug=True)\n",
"# print(i, s, l)"
]
},
{
"cell_type": "code",
"execution_count": 10,
"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": 106,
"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
}