1. Introduction

This code is my attempt at solving the August 2016 Community Challenge. Coming from a city where it rains cats and dogs on a daily basis this challenge was right up my alley =)

2. Algorithm

I used the solution 200_success ♦ outlined in his answer here:

1. Each Cell keeps track of which Basin it belongs to; each Cell is initially assume to be in its own Basin. Each Basin has a sink, or lowest Cell, which acts as a "representative element" of the Basin, as well as a member count. Topography keeps track of all Basins. 2. For each Basin, find lowest of the sink's neighbours. If the lowest is not already a member of this Basin, transfer its cells into the lowest neighbour's Basin, and notify Topography that the higher basin no longer exists.
2. Repeat step 2 until no further action is necessary.
3. Have Topography enumerate the Basins and their counts.

3. Input and output

Example 1

Input: rainfall-example-1.txt

Output:

Height Farmland:
[[1 5 2]
 [2 4 7]
 [3 6 9]]

Basins:
 (A)  A  (B) 
  A   A   B  
  A   A   A  

Letter  Size  Sink
A       7     (0, 0) 
B       2     (0, 2) 

Example 2

Input: rainfall-example-2.txt

Output:

Height Farmland:
[[1 0 2 5 8]
 [2 3 4 7 9]
 [3 5 7 8 9]
 [1 2 5 4 3]
 [3 3 5 2 1]]

Basins:
  A   (A)  A  A   A  
  A    A   A  A   A  
  B    B   A  C   C  
 (B)   B   B  C   C  
  B    B   C  C  (C) 

Letter  Size  Sink
A       11    (0, 1) 
B        7    (3, 0) 
C        7    (4, 4) 

Example 3

Input: rainfall-example-3.txt

Output:

Height Farmland:
[[0 2 1 3]
 [2 1 0 4]
 [3 3 3 3]
 [5 5 2 1]]

Basins:
 (B)  B   A    A  
  B   A  (A)   A  
  B   A   A    C  
  B   C   C   (C) 

Letter  Size  Sink
A       7     (1, 2) 
B       5     (0, 0) 
C       4     (3, 3) 

Example 4

Input: rainfall-example-4.txt

Output:

Height Farmland:
[[ 4 23 25 21 29 16 23 29 12 28]
 [ 0 12 26  0 19 23  9 13 11 29]
 [26 24 18 21 22  4 29  1  5 28]
 [13 15 18  3  6  7 15 15  0  9]
 [29 29 23  6 28  1 11  1  3 21]
 [ 6  3  0 13 11  0 28  0 25 17]
 [20 15  7 24  3  8  5 21 12 23]
 [ 0  9 24 12 19 23  9 29 26 21]
 [ 1 12 12  2 14  2  0 16  2  6]
 [14  5 14  7 26 12 24  6  5 25]
 [18 25 20 29 17 23 23  2 24 19]
 [ 9  0  6  2 19 19 12 10 18 28]
 [ 8 27  7 23 14  9  3 14 18 25]
 [ 6 19 13  9  3  0 21  3  2 16]
 [ 6  1 14 12 19 22 15  2 19 12]
 [17 24 27  8 15 26 16  6  0 27]
 [ 0 15  3  4  2 19  0  3 17 19]
 [ 3 17 14 19 20 20 25  1  7 19]
 [10 13 13 22 27 20 21 28 12  4]
 [27 20 19 17 28  0 13  4  1 10]]

Basins:
  K     K     M     M     AI   (AI)   AE    A     A     A   
 (K)    K     M    (M)    M     Y    (AE)   AB    A     A   
  K     K    (AN)   M     Y    (Y)    AB   (AB)   A     A   
 (AJ)   AJ    X    (X)    X     C     C     A    (A)    A   
  B     B     B     X     C     C     C     T     A     A   
  B     B    (B)    B     C    (C)    C    (T)    T    (AR) 
  N     B     B     AA   (AA)   C    (AS)   T    (AK)   AK  
 (N)    N     B     L     AA    F     F     F     P     P   
  N     N     L    (L)    L     F    (F)    F    (P)    P   
  N    (AL)   AL    L     L     F     F     I     P     P   
  H     H     H     U    (AP)   F     I    (I)    I    (AO) 
  H    (H)    H    (U)    U     G     AF    I     I     I   
  AH    H     H     U     G     G    (AF)   V     W     W   
 (AH)   Q     H     G     G    (G)    G     V    (W)    W   
  Q    (Q)    Q     E     G     G     V    (V)    O    (AQ) 
  D     Q     AD    E     E     E     J     O    (O)    O   
 (D)    D    (AD)   E    (E)    J    (J)    J     O     O   
  D     D     AD    E     E     J     J    (Z)    Z     AG  
  D     D    (AC)   AC    E     R     R     Z     S    (AG) 
  D     D     AC   (AM)   R    (R)    R     S    (S)    S   

Letter  Size  Sink
 A      12    (3, 8) 
 B      10    (5, 2) 
 C       9    (5, 5) 
 D       9    (16, 0) 
 E       9    (16, 4) 
 F       9    (8, 6) 
 G       9    (13, 5) 
 H       9    (11, 1) 
 I       7    (10, 7) 
 J       6    (16, 6) 
 K       6    (1, 0) 
 L       6    (8, 3) 
 M       6    (1, 3) 
 N       6    (7, 0) 
 O       6    (15, 8) 
 P       6    (8, 8) 
 Q       5    (14, 1) 
 R       5    (19, 5) 
 S       4    (19, 8) 
 T       4    (5, 7) 
 U       4    (11, 3) 
 V       4    (14, 7) 
 W       4    (13, 8) 
 X       4    (3, 3) 
 Y       3    (2, 5) 
 Z       3    (17, 7) 
AA       3    (6, 4) 
AB       3    (2, 7) 
AC       3    (18, 2) 
AD       3    (16, 2) 
AE       2    (1, 6) 
AF       2    (12, 6) 
AG       2    (18, 9) 
AH       2    (13, 0) 
AI       2    (0, 5) 
AJ       2    (3, 0) 
AK       2    (6, 8) 
AL       2    (9, 1) 
AM       1    (19, 3) 
AN       1    (2, 2) 
AO       1    (10, 9) 
AP       1    (10, 4) 
AQ       1    (14, 9) 
AR       1    (5, 9) 
AS       1    (6, 6) 

Example 5

Input: rainfall-example-5.txt [20x20 map, height = 1000]

Example 6

Input: rainfall-example-6.txt [map: 55x55, height: 55^2]

4. Comments

• Not happy with using chararray as it seem it is deprecated. I tried using an array with the bool = string, but that threw me an error when I tried to update the array.
• The way I handle strings and str_rep feels wrong.
• The structure of my code feels right, but the classes feels very empty.
• My code struggles with big farmlands for an example for rainfall-example-6.txt. Is this normal, or could the algorithm be improved?
• Useless docstrings?

5. Code

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import string
import numpy as np
from numpy import unravel_index

ALPHABETH = string.ascii_uppercase
ALPHABETH_len = len(ALPHABETH)


def num_2_alpha(num):
    '''
    Converts an arabic number 0, 1, 2.. to it's corresponding letter A, B, C, ....
    Example:
        0 > A
        1 > B
        26 > Z 
        27 > AA
    '''
    quotient, remainder = divmod(num, ALPHABETH_len)
    return quotient*ALPHABETH[0] + ALPHABETH[remainder]


def create_test_file(max_height, shape):
    '''
    Creates a random height map with dimensions x, y (from shape)
    and height from 0 to max_height.
    '''
    random_integers = np.random.randint(max_height, size=shape[0]*shape[1])
    return random_integers.reshape(shape[0], shape[1])


def format_topography(topography_):
    '''
    Inputs a typography of the farmland formated in a character array
    this function formats the typography into a nicer looking string. 
    Input
        [['(A)' 'A' '(B)']
         ['A' 'A' 'B']
         ['A' 'A' 'A']]
    Output:
        (A)  A  (B) 
         A   A   B  
         A   A   A  
    '''
    rows, columns = topography_.shape
    column_padding = [0]*columns

    for i in range(columns):
        column_padding[i] = len(max(topography_[:, i], key=len))

    padded_string = ''
    for i in range(rows):
        for j in range(columns):
            padded_string += ' {:^{}} '.format(
                topography_[i, j], column_padding[j])
        padded_string += '\n'
    return padded_string


def basin_2_string(basin_list):
    '''
    Input is a dictionary of basins where the key is the sink
    Example output:
        A: 7, Sink: (1, 2)
        B: 5, Sink: (0, 0)
        C: 4, Sink: (3, 3)
    '''

    letter_padding = len(num_2_alpha(len(basin_list)))
    sep1 = ' '*(len('letter')-letter_padding)

    size_padding = len(str(basin_list[0].size))
    sep2 = ' '*(len('Size')-size_padding)

    basin_string = 'Letter  Size  Sink\n'
    for i, basin in enumerate(basin_list):
        basin_string += '''{:>{}} {} {:{}d} {} {} 
'''.format(num_2_alpha(i), letter_padding, sep1, basin.size, size_padding, sep2, basin.sink)
    return basin_string


def create_height_map(filename):
    '''
    Input: a filename with a textfile formated as
    1 5 2 
    2 4 7 
    3 6 9
    Ouputs a matrix of the height map.
    '''
    file = open(filename, 'r')
    matrix = np.matrix([map(int, line.split()) for line in file])
    file.close()
    return matrix


def create_matrix_map(class_type, shape):
    '''
    Creates a dictionary where the keys are (x, y) coordinates. 
    This is used to store / index the basins and the cells
    '''
    length, width = shape
    matrix = dict()
    for i in xrange(length):
        for j in xrange(width):
            matrix[(i, j)] = class_type([i, j], [length, width])
    return matrix


def neighboors_list(coordinates, shape):
    '''
    Makes a list of all the neighboors to a point in the height map
    '''
    length, width = shape
    x, y = coordinates
    neighboors = []

    if x < 0 or x == length or y < 0 or y == width:
        ValueError("The coordinates lies outside the matrix")
    if x > 0:
        neighboors.append((x-1, y))
    if x + 1 < length:
        neighboors.append((x+1, y))
    if y > 0:
        neighboors.append((x, y-1))
    if y + 1 < width:
        neighboors.append((x, y+1))
    return neighboors


def create_basins_and_cells(height_map, shape):
    '''
    This creates the basins and the cells using the following algorithm:
    1. Each Cell keeps track of which Basin it belongs to; each Cell is initially assume to be in its own Basin. 
       Each Basin has a sink, or lowest Cell, which acts as a "representative element" of the Basin, 
       as well as a member count. Topography keeps track of all Basins.
    2. For each Basin, find lowest of the sink's neighbours. If the lowest is not already a member of this Basin, 
       transfer its cells into the lowest neighbour's Basin, and notify Topography that the higher basin no longer exists.
    3. Repeat step 2 until no further action is necessary.
    '''

    basins = create_matrix_map(Basin, shape)
    cells = create_matrix_map(Cell, shape)

    topography_changed = True
    while topography_changed:
        topography_changed = False

        for old_basin_coords in basins:
            sink_coords = basins[old_basin_coords].sink
            lowest_neighboor_height = height_map[sink_coords]
            lowest_neighboor_coords = sink_coords

            for neighboor in cells[sink_coords].neighboors:
                if height_map[neighboor] < lowest_neighboor_height:
                    lowest_neighboor_height = height_map[neighboor]
                    lowest_neighboor_coords = neighboor

            if lowest_neighboor_coords not in basins[old_basin_coords].cells:
                topography_changed = True
                new_basin_coords = cells[lowest_neighboor_coords].basin

                for cell_coords in basins[old_basin_coords].cells:
                    basins[new_basin_coords].cells.append(tuple(cell_coords))
                    cells[cell_coords].basin = new_basin_coords

                basins[new_basin_coords].size = len(
                    basins[new_basin_coords].cells)
                del basins[old_basin_coords]
                break

    basin_list = sorted(basins.values(), key=lambda x: x.size, reverse=True)
    return basin_list, cells


def create_topography(basin_list, shape):
    '''
    Enumerates the basins, in practice this creates the topography of the farmland
    '''
    character_length = len(num_2_alpha(len(basin_list)))
    topography = np.chararray(shape, itemsize=character_length+2)
    for i, basin in enumerate(basin_list):
        letter = num_2_alpha(i)
        for coords in basin.cells:
            if coords == basin.sink:
                topography[coords] = '('+letter+')'
            else:
                topography[coords] = letter
    return topography


class Cell():

    '''
    Simple class describing a single cell in the height map.
    '''

    def __init__(self, coordinates, shape):
        self.coordinates = tuple(coordinates)
        self.neighboors = neighboors_list(coordinates, shape)
        self.basin = tuple(coordinates)


class Basin():

    '''
    Simple class describing the basins in the height map. 
    '''

    def __init__(self, coordinates, shape):
        self.coordinates = tuple(coordinates)
        self.sink = tuple(coordinates)
        self.cells = [tuple(coordinates)]
        self.size = 1

    def __repr__(self):
        return '''<Size: {}, Sink: {}, Cells: {}>\n
        '''.format(self.size, self.sink, self.cells)


class Topography():

    '''
    A group of farmers has some elevation data, and we're going to help them understand 
    how rainfall flows over their farmland.

    We'll represent the land as a two-dimensional array of altitudes and use the following 
    model, based on the idea that water flows downhill:

    If a cell’s four neighboring cells all have higher altitudes, we call this cell a sink; water collects in sinks.

    Otherwise, water will flow to the neighboring cell with the lowest altitude. If a cell is not a sink, 
    you may assume it has a unique lowest neighbor and that this neighbor will be lower than the cell.

    Cells that drain into the same sink – directly or indirectly – are said to be part of the same basin.

    Your challenge is to partition the map into basins. In particular, given a map of elevations,
    your code should partition the map into basins and output the sizes of the basins, in descending order. 
    '''

    def __init__(self, filename):
        self.height_map = create_height_map(filename)
        self.shape = self.height_map.shape
        self.basins, self.cells = create_basins_and_cells(
            self.height_map, self.shape)
        self.topography = create_topography(self.basins, self.shape)
        self.basin_sizes = [basin.size for basin in self.basins]

    def __str__(self):
        string = '''
Height Farmland:
{}

Basins:
{}
{}'''.format(
            str(self.height_map),
            format_topography(self.topography),
            basin_2_string(self.basins))
        return string

if __name__ == '__main__':

    n = 50
    seperator = '-'*n
    print seperator
    for i in range(1, 5):
        print Topography('rainfall-example-{}.txt'.format(i))
        print seperator
    print
    # np.savetxt('rainfall-example-4.txt', create_test_file(30, (20, 10)), delimiter = ' ', fmt='%d')
    # np.savetxt('rainfall-example-5.txt', create_test_file(15, (30, 25)), delimiter = ' ', fmt='%d')