{ "metadata": { "name": "" }, "nbformat": 3, "nbformat_minor": 0, "worksheets": [ { "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "## Twitter Puddle Puzzle\n", "http://puzzles.bostonpython.com/puddle.html\n", "\n", "Solutions by Steve Witham.\n", "\n", "* The first is based on a simple declarative definition of water depth.\n", "* The second is an optimization of the first.\n", "* The third is a stack-based solution for speed and memory use comparison.\n" ] }, { "cell_type": "code", "collapsed": false, "input": [ "# Set up the list of problem examples and the list of methods.\n", "# Methods and more problems get added to the lists later.\n", "\n", "from collections import OrderedDict\n", "\n", "EXAMPLES = []\n", "\n", "EXAMPLES.append( (\"Empty\", [], 0) )\n", "\n", "\"\"\"\n", " _ _ _\n", " |2|w|2|w|2|_\n", " |__1___1___1|\n", " 0 1 2 3 4 5\n", "\"\"\"\n", "EXAMPLES.append( (\"Two puddles same height\", [2, 1, 2, 1, 2, 1], 2) )\n", "\"\"\"\n", " _ _\n", " |7 7|_\n", " _ | 6|\n", " |5|w w w w| |\n", " | |w w w|4 |\n", " _| |w w|3 |\n", " |2 |w|2 |\n", " |____1____________|\n", " 0 1 2 3 4 5 6 7 8\n", "\"\"\"\n", "EXAMPLES.append( (\"Original\", [2, 5, 1, 2, 3, 4, 7, 7, 6], 10) )\n", "\n", "METHODS = OrderedDict()\n", "def METHOD(method):\n", " \" A decorator to register OR REREGISTER a method function in METHODS. \"\n", " METHODS[method.__name__] = method\n", " return method" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 1 }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Cumulative Maxes to the Left and Right\n", "\n", "The height of the water surface above a given block is the lower of\n", "\n", "* the highest wall to the left (including this block) and\n", "* the highest wall to the right (including this block).\n", "\n", "" ] }, { "cell_type": "code", "collapsed": false, "input": [ "from itertools import izip\n", "\n", "def cumulative_maxes(ys):\n", " m = None\n", " for y in ys:\n", " m = max(m, y)\n", " yield m\n", "\n", "@METHOD\n", "def puddle_vol_cumulative_maxes(ys):\n", " \"\"\" \n", " This relies on ys being a list, and uses an equal amount of extra memory.\n", " \"\"\"\n", " maxes_to_L = cumulative_maxes(ys)\n", " maxes_to_R = reversed(list(cumulative_maxes(reversed(ys))))\n", " return sum(min(mL, mR) - y for mL, y, mR in izip(maxes_to_L, ys, maxes_to_R))" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 227 }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Find the Peak, then Climb the Slopes" ] }, { "cell_type": "code", "collapsed": false, "input": [ "@METHOD\n", "def puddle_vol_peak_then_slopes(ys):\n", " \"\"\"\n", " Once you know the max of the whole ys list, and its position in the list\n", " (if the max appears in more than one place, it doesn't matter which you pick),\n", " then water heights on its left only depend on wall heights to their left,\n", " and water heights on its right only depend on wall heights to their right.\n", " \n", " This depends on ys being a list, but creates no other lists.\n", " \"\"\"\n", " if not ys: return 0 # Can't take max of an empty list.\n", " \n", " peak_i = ys.index(max(ys))\n", " vol = 0\n", " for slope in xrange(peak_i), xrange(len(ys) - 1, peak_i, -1):\n", " highest = None\n", " for i in slope:\n", " y = ys[i]\n", " highest = max(highest, y)\n", " vol += highest - y\n", " return vol" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 228 }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Strictly Left-to-Right with a Stack" ] }, { "cell_type": "code", "collapsed": false, "input": [ "@METHOD\n", "def puddle_vol_L_to_R_stack(ys):\n", " \"\"\"\n", " This is a stack-based solution for speed and space comparison.\n", " Each stack entry locates the upper-right square of a rectangle.\n", " x's of Points on the stack are strictly increasing; y's strictly decreasing.\n", " \n", " This does not depend on ys being a list.\n", " The size of the stack can be twice the size of ys.\n", " \"\"\"\n", " stack_x, stack_y = [], []\n", " vol = 0\n", " for cx, cy in enumerate(ys):\n", " while len(stack_y) >= 2 and stack_y[-1] < cy:\n", " bx, by = stack_x.pop(), stack_y.pop()\n", " ax, ay = stack_x[-1], stack_y[-1]\n", " vol += (min(ay, cy) - by) * (cx - ax - 1)\n", " if ay < cy:\n", " stack_x[-1] = bx\n", " if stack_y and stack_y[-1] <= cy:\n", " stack_x.pop(), stack_y.pop()\n", " stack_x.append(cx)\n", " stack_y.append(cy)\n", " return vol" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 232 }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Testing and Timing" ] }, { "cell_type": "code", "collapsed": false, "input": [ "from time import clock\n", "import random\n", "\n", "def make_problems(n_problems, n_heights):\n", " problems = []\n", " for i in range(1, n_problems + 1):\n", " name = \"random problem %d\" % i\n", " heights = [random.randrange(1, n_heights + 1) for j in range(n_heights)]\n", " correct_vol = None\n", " problems.append( (name, heights, correct_vol) )\n", " return problems\n", "\n", "\n", "def make_example_pairs(examples):\n", " example_pairs = []\n", " for example in examples:\n", " name, heights, correct_vol = example\n", " rev_heights = list(reversed(heights))\n", " rev_example = (\"reversed \" + name, rev_heights, correct_vol)\n", " example_pairs.append( (example, rev_example) )\n", " return example_pairs\n", "\n", "\n", "def test(methods, examples, n_repeats=100):\n", " example_pairs = make_example_pairs(examples)\n", " results = []\n", " for method in METHODS.values():\n", " start = clock()\n", " answer_pairs = []\n", " for example_pair in example_pairs:\n", " answer_pair = []\n", " for example in example_pair:\n", " name, heights, correct_vol = example\n", " for i in range(n_repeats):\n", " answer = method(heights)\n", " answer_pair.append(answer)\n", " answer_pairs.append(answer_pair)\n", " duration = (clock() - start) / n_repeats\n", " results.append( (method, answer_pairs, duration) )\n", " return results\n", "\n", "\n", "def show_results(results):\n", " for method, answer_pairs, duration in results:\n", " print method.__name__\n", " n_mistakes = 0\n", " n_mismatches = 0\n", " for i, (problem, answer_pair) in enumerate(zip(problem_set, answer_pairs)):\n", " problem_name, heights, correct_vol = problem\n", " for answer in answer_pair:\n", " if correct_vol != None and answer != correct_vol:\n", " n_mistakes += 1\n", " if answer != results[0][1][i][0]:\n", " n_mismatches += 1\n", " if n_mistakes:\n", " print \" \", n_mistakes, \"mistakes\"\n", " if n_mismatches:\n", " print \" \", n_mismatches, \"disagreements with\", results[0][0].__name__\n", " print \" \", duration, \"sec.\"\n", " \n", "\n", "random.seed(201406271651)\n", "problem_set = EXAMPLES + make_problems(n_problems=100, n_heights=100)\n", "results = test(METHODS, problem_set, n_repeats=10)\n", "show_results(results)\n" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "puddle_vol_max_L_max_R\n", " 0.0644718 sec.\n", "puddle_vol_peak_then_slopes\n", " 0.0244862 sec.\n", "puddle_vol_L_to_R_stack\n", " 0.1103731 sec.\n" ] } ], "prompt_number": 233 }, { "cell_type": "code", "collapsed": false, "input": [], "language": "python", "metadata": {}, "outputs": [] } ], "metadata": {} } ] }