Twitter Puddle Puzzle

<a href=http://puzzles.bostonpython.com/puddle.html>http://puzzles.bostonpython.com/puddle.html</a>

Solutions by Steve Witham.

  • The first is based on a simple declarative definition of water depth.
  • The second is an optimization of the first.
  • The third is a stack-based solution for speed and memory use comparison.
In [1]:
# Set up the list of problem examples and the list of methods.
# Methods and more problems get added to the lists later.

from collections import OrderedDict

EXAMPLES = []

EXAMPLES.append( ("Empty", [], 0) )

"""
     _   _   _
    |2|w|2|w|2|_
    |__1___1___1|
     0 1 2 3 4 5
"""
EXAMPLES.append( ("Two puddles same height", [2, 1, 2, 1, 2, 1], 2) )
"""
                 _ _
                |7 7|_
       _        |    6|
      |5|w w w w|     |
      | |w w w|4      |
     _| |w w|3        |
    |2  |w|2          |
    |____1____________|
     0 1 2 3 4 5 6 7 8
"""
EXAMPLES.append( ("Original", [2, 5, 1, 2, 3, 4, 7, 7, 6], 10) )

METHODS = OrderedDict()
def METHOD(method):
    " A decorator to register OR REREGISTER a method function in METHODS. "
    METHODS[method.__name__] = method
    return method

Cumulative Maxes to the Left and Right

The height of the water surface above a given block is the lower of

  • the highest wall to the left (including this block) and
  • the highest wall to the right (including this block).

In [227]:
from itertools import izip

def cumulative_maxes(ys):
    m = None
    for y in ys:
        m = max(m, y)
        yield m

@METHOD
def puddle_vol_cumulative_maxes(ys):
    """ 
    This relies on ys being a list, and uses an equal amount of extra memory.
    """
    maxes_to_L = cumulative_maxes(ys)
    maxes_to_R = reversed(list(cumulative_maxes(reversed(ys))))
    return sum(min(mL, mR) - y for mL, y, mR in izip(maxes_to_L, ys, maxes_to_R))

Find the Peak, then Climb the Slopes

In [228]:
@METHOD
def puddle_vol_peak_then_slopes(ys):
    """
    Once you know the max of the whole ys list, and its position in the list
    (if the max appears in more than one place, it doesn't matter which you pick),
    then water heights on its left only depend on wall heights to their left,
    and water heights on its right only depend on wall heights to their right.
    
    This depends on ys being a list, but creates no other lists.
    """
    if not ys: return 0  #  Can't take max of an empty list.
    
    peak_i = ys.index(max(ys))
    vol = 0
    for slope in xrange(peak_i), xrange(len(ys) - 1, peak_i, -1):
        highest = None
        for i in slope:
            y = ys[i]
            highest = max(highest, y)
            vol += highest - y
    return vol

Strictly Left-to-Right with a Stack

In [232]:
@METHOD
def puddle_vol_L_to_R_stack(ys):
    """
    This is a stack-based solution for speed and space comparison.
    Each stack entry locates the upper-right square of a rectangle.
    x's of Points on the stack are strictly increasing; y's strictly decreasing.
    
    This does not depend on ys being a list.
    The size of the stack can be twice the size of ys.
    """
    stack_x, stack_y = [], []
    vol = 0
    for cx, cy in enumerate(ys):
        while len(stack_y) >= 2 and stack_y[-1] < cy:
            bx, by = stack_x.pop(), stack_y.pop()
            ax, ay = stack_x[-1], stack_y[-1]
            vol += (min(ay, cy) - by) * (cx - ax - 1)
            if ay < cy:
                stack_x[-1] = bx
        if stack_y and stack_y[-1] <= cy:
            stack_x.pop(), stack_y.pop()
        stack_x.append(cx)
        stack_y.append(cy)
    return vol

Testing and Timing

In [233]:
from time import clock
import random

def make_problems(n_problems, n_heights):
    problems = []
    for i in range(1, n_problems + 1):
        name = "random problem %d" % i
        heights = [random.randrange(1, n_heights + 1) for j in range(n_heights)]
        correct_vol = None
        problems.append( (name, heights, correct_vol) )
    return problems


def make_example_pairs(examples):
    example_pairs = []
    for example in examples:
        name, heights, correct_vol = example
        rev_heights = list(reversed(heights))
        rev_example = ("reversed " + name, rev_heights, correct_vol)
        example_pairs.append( (example, rev_example) )
    return example_pairs


def test(methods, examples, n_repeats=100):
    example_pairs = make_example_pairs(examples)
    results = []
    for method in METHODS.values():
        start = clock()
        answer_pairs = []
        for example_pair in example_pairs:
            answer_pair = []
            for example in example_pair:
                name, heights, correct_vol = example
                for i in range(n_repeats):
                    answer = method(heights)
                answer_pair.append(answer)
            answer_pairs.append(answer_pair)
        duration = (clock() - start) / n_repeats
        results.append( (method, answer_pairs, duration) )
    return results


def show_results(results):
    for method, answer_pairs, duration in results:
        print method.__name__
        n_mistakes = 0
        n_mismatches = 0
        for i, (problem, answer_pair) in enumerate(zip(problem_set, answer_pairs)):
            problem_name, heights, correct_vol = problem
            for answer in answer_pair:
                if correct_vol != None and answer != correct_vol:
                    n_mistakes += 1
                if answer != results[0][1][i][0]:
                    n_mismatches += 1
        if n_mistakes:
            print "   ", n_mistakes, "mistakes"
        if n_mismatches:
            print "   ", n_mismatches, "disagreements with", results[0][0].__name__
        print "   ", duration, "sec."
    

random.seed(201406271651)
problem_set = EXAMPLES + make_problems(n_problems=100, n_heights=100)
results = test(METHODS, problem_set, n_repeats=10)
show_results(results)
puddle_vol_max_L_max_R
    0.0644718 sec.
puddle_vol_peak_then_slopes
    0.0244862 sec.
puddle_vol_L_to_R_stack
    0.1103731 sec.