A solution for the August 2016 Community Challenge (Rainfall).I've intentionally left out error checking on the file formatting.This seems like a very obvious graph problem to me - we want to partition some graph based off of relative elevations.  I've used networkx 1.9.1 to operate on the graphs, and matplotlib to make it pretty(ish).Haven't tested this on a large sample, but I suspect that it will go pretty slowly. t.txt refers to a file like this - the name was for brevity's sake, and would be a different one were I making a production application.31 5 22 4 73 6 9The general idea is to build up a graph of all of the plots and their neighbors, while also building up a list of plots sorted by elevation (which is fairly efficient due to the binary search insertion) and then starting from the highest elevation and moving down, removing edges that get disqualified. I then do a little extra at the end to set the basin property on each node to the correct value, but that isn't strictly necessary (I'd get the correct answer either way, and the coloring would only require a minor change to work).I wrote this and ran it on Python 2, but at a first glance it should work on Python 3 without modification (famous last words...).from collections import namedtupleimport bisectimport functoolsimport networkx as nximport matplotlib.pyplot as pltimport numpy as np@functools.total_orderingclass PlotData(namedtuple('PlotData', 'plot elevation')):    def __lt__(self, other):        return self.elevation < other.elevation    def __eq__(self, other):        return self.elevation == other.elevationdef build_topography(filename):    with open(filename) as elevation_data:        lines = iter(elevation_data)        next(lines)        topography = nx.Graph()        sorted_plots = []        for row_index, row in enumerate(lines):            for plot_index, elevation in enumerate(map(int, row.split())):                plot = (row_index, plot_index)                data = PlotData(plot, elevation)                bisect.insort(sorted_plots, data)                topography.add_node(                    plot,                    elevation=elevation,                    basin=plot,                    parents=[]                )                add_edges(topography, plot)    return topography, reversed(sorted_plots)def add_edges(topography, plot):    above_node = (plot[0] - 1, plot[1])    left_node = (plot[0], plot[1] - 1)    if above_node in topography:        topography.add_edge(plot, above_node)    if left_node in topography:        topography.add_edge(plot, left_node)def process_topography(topography, sorted_nodes):    for node in sorted_nodes:        node = node.plot        edges = topography[node]        if edges:            min_elevation = topography.node[node]['elevation']            basin = node            parents = topography.node[node]['parents']            for connected_node in edges:                elevation = topography.node[connected_node]['elevation']                if elevation < min_elevation:                    min_elevation = elevation                    basin = connected_node            topography.node[node]['basin'] = basin            topography.node[basin]['parents'].append(node)            topography.node[basin]['parents'].extend(parents)            edges_to_remove = [connected_node                               for connected_node in edges                               if connected_node != basin and                                  connected_node not in parents]            for edge_to_remove in edges_to_remove:                topography.remove_edge(node, edge_to_remove)    fix_basins(topography)def fix_basins(topography):    for node in topography.nodes():        if is_sink(topography, node):            for parent in topography.node[node]['parents']:                topography.node[parent]['basin'] = nodedef is_sink(topography, node):    connected_nodes = topography[node]    parents = topography.node[node]['parents']    return all(connected in parents for connected in connected_nodes)def get_label(topography, node):    n_dict = topography.node[node]    return {} - {}.format(n_dict['basin'], n_dict['elevation'])def get_basin_colors(topography):    connected_components = list(nx.connected_components(topography))    colors = np.linspace(0, 1, len(connected_components))    return {        topography.node[component[0]]['basin'] : color        for component, color in zip(connected_components, colors)    }def get_basin_sizes(connected_components):    return (        len(component)        for component in sorted(connected_components, key=len, reverse=True)    )def display_graph(topography, colored=False):    labels = {node : get_label(topography, node) for node in topography.nodes()}    kwargs = {        'with_labels': True,        'layout': nx.shell_layout(topography),        'labels': labels    }    if colored:        color_dict = get_basin_colors(topography)        colors = [color_dict[topography.node[node]['basin']] for node in topography.nodes()]        kwargs['node_color'] = colors    nx.draw(topography, **kwargs)    plt.draw()    plt.show()if __name__ == '__main__':    topography, sorted_plots = build_topography('t.txt')    display_graph(topography)    process_topography(topography, sorted_plots)    display_graph(topography, colored=True)    for basin in get_basin_sizes(nx.connected_components(topography)):        print basin,This displays these graphs:And then this output:7 2
Rainfall - August 2016 Community Challenge (Hooray for graphs!)
python;performance;python 2.7;graph;community challenge