Skyline solutions

skyline.py

#!/usr/bin/env python3

"""Skyline solutions.

See https://pykello.github.io/programming/2015/12/12/haskell-skyline/

Bench with ipython:

%timeit -r 10 skyline.skyline1(skyline.buildings)
10000 loops, best of 10: 19.6 µs per loop

%timeit -r 10 skyline.skyline2(skyline.buildings)
10000 loops, best of 10: 40.2 µs per loop
"""

import functools
import operator

def skyline1(buildings):
    # Find highest height for each points
    points = {}
    min_x = buildings[0][0]
    max_x = min_x
    for x1, height, x2 in buildings:
        for i in range(x1, x2):
            if points.get(i, 0) < height:
                points[i] = height
        max_x = max(max_x, x2)

    # Find change in points and register this skyline update
    skyline = []
    last_height = -1
    for i in range(min_x, max_x):
        height = points.get(i, 0)
        if last_height != height:
            skyline.append((i, height))
            last_height = height

    return skyline

def skyline2(buildings):
    hightest = lambda buildings, x: max(h if x1 <= x and x < x2 else 0 for x1, h, x2 in buildings)
    return functools.reduce(
        # Third step: ignore skyline point if previous point has the same height
        lambda l1, p: l1 if l1 and l1[-1][-1] == p[-1] else l1 + [p],
        # Second step: for each points, find highest height
        [(x, hightest(buildings, x)) for x in
            # First step: collect sorted begin/end points
            sorted(functools.reduce(operator.add, ([x1, x2] for x1, _, x2 in buildings)))],
        # Initial list used in this reduce
        [])

buildings = [(1,11,5),(2,6,7),(3,13,9),(12,7,16),(14,3,25),(19,18,22),(23,13,29),(24,4,28)]
expected = [(1,11),(3,13),(9,0),(12,7),(16,3),(19,18),(22,3),(23,13),(29,0)]

if __name__ == '__main__':
    print("buildings: %s" % buildings)
    print("Skyline : %s" % skyline2(buildings))
    print("Expected: %s" % expected)