4
\$\begingroup\$

The Skyline problem from UVa Online Judge is as follows:

You are to design a program to assist an architect in drawing the skyline of a city given the locations of the buildings in the city. A building is specified by an ordered triple \$ (L_i,H_i,R_i) \$ where \$ L_i \$ and \$ R_i \$ are left and right coordinates, respectively, of building \$ i \$ and \$ H_i \$ is the height of the building.

The input is a sequence of building triples. All coordinates of buildings are integers less than 10,000 and there will be at least one and at most 5,000 buildings in the input file. Each building triple is on a line by itself in the input file. All integers in a triple are separated by one or more spaces. The triples will be sorted by \$ L_i \$, the left x-coordinate of the building, so the building with the smallest left x-coordinate is first in the input file.

The output should consist of the skyline vector \$ (v_1, v_2, v_3, \ldots, v_{n−2}, v_{n−1}, v_n)\$, the \$ v_i \$ such that \$ i \$ is an even number represent a horizontal line (height). The \$ v_i \$ such that \$ i \$ is an odd number represent a vertical line (x-coordinate). The skyline vector should represent the “path” taken, for example, by a bug starting at the minimum x-coordinate and traveling horizontally and vertically over all the lines that define the skyline. Thus the last entry in all skyline vectors will be a 0.

This is my solution:

# [SortedDict](http://www.grantjenks.com/docs/sortedcontainers/sorteddict.html)
from sortedcontainers import SortedDict # pip3 install sortedcontainers
from collections import deque
import heapq

def skyline(buildings_by_L): # a deque.
    buildings_by_H = SortedDict() # a self-balancing binary tree.
    buildings_by_R = [] # a priority queue.
    skyline = []
    def add_point(x):
        h = buildings_by_H.iloc[-1] if buildings_by_H else 0
        if not skyline:
            skyline.append((x, h))
        else:
            x0, h0 = skyline[-1]
            if h != h0:
                if x == x0:
                    skyline[-1] = (x, max(h, h0))
                else:
                    skyline.append((x, h))
    def insert(b, sets=[set()]):
        heapq.heappush(buildings_by_R, (b[2], b))
        s = buildings_by_H.setdefault(b[1], sets[0])
        s.add(b)
        if s == sets[0]:
            sets[0] = set()
        add_point(b[0])
    def delete(b):
        buildings_by_H[b[1]].remove(b)
        if not buildings_by_H[b[1]]:
            del buildings_by_H[b[1]]
        add_point(b[2])
    while buildings_by_L or buildings_by_R: # another sweep line algorithm
        if (not buildings_by_R
            or buildings_by_L
               and buildings_by_L[0][0] <= buildings_by_R[0][0]):
            insert(buildings_by_L.popleft())
        else:
            delete(heapq.heappop(buildings_by_R)[1])
    return skyline

Test Cases:

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

Can you please suggest more elegant and eloquent ways for this problem? (Perhaps better ways to represent a graph with vertices and edges?)

\$\endgroup\$
  • 2
    \$\begingroup\$ Hiya! This looks like two completely different and unrelated problems to me... I suggest you ask one question per review (aka. problem). Additionally links are not well recieved here for problem statements. It would be preferrable if you could sum up the problem statement in the question itself (and provide the link for reference)... \$\endgroup\$ – Vogel612 Oct 15 '14 at 17:32
  • 2
    \$\begingroup\$ Please ask two questions as suggested by Vogel612. \$\endgroup\$ – 200_success Oct 15 '14 at 17:58
  • 2
    \$\begingroup\$ Thank you for removing the second problem. Could you also edit in a summary of the problem statement? Unfortunately, links rot, so we find them undesirable as integral parts of the question. Another issue is that it is hard to find this question via search if half the content is embedded in a PDF on a different site. \$\endgroup\$ – Brythan Oct 16 '14 at 20:30
6
\$\begingroup\$

1. Bug

If the city contains two identical buildings then skyline raises an exception:

>>> skyline(deque([(1, 2, 3), (1, 2, 3)]))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "cr66776.py", line 97, in skyline
    delete(heapq.heappop(buildings_by_R)[1])
  File "cr66776.py", line 87, in delete
    buildings_by_H[b[1]].remove(b)
KeyError: 2

This is because the code represents buildings by tuples of numbers, and that means that two identical buildings get stored just once in a set, so when you come to remove the second building, it's not there. To fix this, buildings need to be represented such that each building is unique. One way to do this would be to use a Building class, as objects are always unique unless they implement an __eq__ method.

2. Review

  1. It's not clear to the reader how the data is represented. The variable b represents a building, but what are b[0], b[1] and b[2]? These are the building's left x-coordinate, height, and right x-coordinate respectively, so it would make the code a lot easier to read if these were b.left, b.height, and b.right. It's easy to do this using a class, or collections.namedtuple.

  2. It's not clear exactly what the helper functions add_point, insert, delete do. In particular, add_point doesn't always add a point to the skyline list: sometimes it updates the last point in the list. The insert function adds a building to the buildings_by_R and buildings_by_H collections, but also calls add_point. These functions could do with comments explaining what exactly it is that they do.

  3. Some of the operations could do with a comment to explain their purpose. For example here:

    h = buildings_by_H.iloc[-1] if buildings_by_H else 0
    

    It would be worth noting that this finds the height of the highest building currently standing.

  4. The insert and delete helper functions are only called once, so there's no particular advantage to making them into functions. The code might be clearer if these functions were inlined at the point of use.

  5. The insert function contains the following lines of code that manipulate the vaguely named sets parameter:

    def insert(b, sets=[set()]):
        s = buildings_by_H.setdefault(b[1], sets[0])
        s.add(b)
        if s == sets[0]:
            sets[0] = set()
    

    It looks as if there was a concern that if the code were written in the obvious way:

    def insert(b):
        buildings_by_H.setdefault(b[1], set()).add(b)
    

    then a set() object would be created and immediately discarded each time a building was inserted at a position for which buildings_by_H already had an entry. This is a valid concern, but the following would seem to be a clearer way to handle it:

    def insert(b):
        try:
            s = buildings_by_H[b[1]]
        except KeyError:
            buildings_by_H[b[1]] = s = set()
        s.add(b)
    
  6. It's worth making a little effort to avoid using libraries that are not built into Python. Having to install sortedcontainers is a small but genuine barrier to running code (and might partly account for the time this question has languished without being reviewed). In this case, SortedDict is used to maintain the collection of currently standing buildings, such that (i) the height of the highest building can be found via buildings_by_H.iloc[-1]; and (ii) the set of buildings at a given height can by located via buildings_by_H[b[1]] and so a building can be removed.

    However, we can implement (i) by storing the buildings in a heap, because as it says in the heapq documentation:

    The interesting property of a heap is that its smallest element is always the root, heap[0].

    Python heaps are min-heaps but we want the highest building, so we have to reverse the comparison order on buildings. If buildings are represented by objects, as recommended in §1 above, then this can be done by implementing a __lt__ method on the Building class.

    How do we implement (ii)? You can't easily delete elements from a heap. The insight here is that we don't have to delete the building from the heap, we can leave it in the heap but mark it as finished (if buildings are represented by objects, as recommended in §1, above then this can be done by setting an attribute). We only care about the highest standing building, which is at the root of the heap, so we can just check that one to see if it is finished and pop it if so.

  7. There's a lot of complexity in the add_point function. This complexity is due to the fact that when add_point(x) is called, we don't know whether or not we've processed all the buildings that start or end at x, so when we construct a point (x, h) we don't know whether we're done with it, or whether we might have to revise it later.

    It would simplify this code considerably if we could be sure that all the buildings that start or end at x have been processed. Then we would know that the point would not need to be revised, and we could just yield it.

3. Revised code

from collections import defaultdict, namedtuple
from heapq import heappop, heappush

class Building:
    def __init__(self, height):
        self.height = height
        self.finished = False

    def __lt__(self, other):
        # Reverse order by height, so that when we store buildings in
        # a heap, the first building is the highest.
        return other.height < self.height

# An event represents the buildings that start and end at a particular
# x-coordinate.
Event = namedtuple('Event', 'start end')

def skyline(buildings):
    """Given an iterable of buildings represented as triples (left, height,
    right), generate the co-ordinates of the skyline.

    >>> list(skyline([(1,9,3), (1,11,5), (2,6,7), (3,13,9), (12,7,16), 
    ...               (14,3,25), (19,18,22), (23,13,29), (24,4,28)]))
    ... # doctest: +NORMALIZE_WHITESPACE
    [(1, 11), (3, 13), (9, 0), (12, 7), (16, 3), (19, 18), (22, 3),
     (23, 13), (29, 0)]
    >>> list(skyline([(1, 3, 2), (1, 3, 2)]))
    [(1, 3), (2, 0)]

    """
    # Map from x-coordinate to event.
    events = defaultdict(lambda:Event(start=[], end=[]))
    for left, height, right in buildings:
        b = Building(height)
        events[left].start.append(b)
        events[right].end.append(b)

    standing = []               # Heap of buildings currently standing.
    last_h = 0                  # Last emitted skyline height.

    # Process events in order by x-coordinate.
    for x, event in sorted(events.items()):        
        # Update buildings currently standing.
        for b in event.start:
            heappush(standing, b)
        for b in event.end:
            b.finished = True

        # Pop any finished buildings from the top of the heap.
        while standing and standing[0].finished:
            heappop(standing)

        # Top of heap (if any) is the highest standing building, so
        # its height is the current height of the skyline.
        h = standing[0].height if standing else 0

        # Yield co-ordinates if the skyline height has changed.
        if h != last_h:
            yield x, h
            last_h = h

4. Performance comparison

Test case (this is an order of magnitude bigger than the largest case specified in the problem description):

>>> from timeit import timeit
>>> import random
>>> R = lambda n:random.randrange(n) + 1
>>> buildings = sorted((x, R(10000), x + R(1000)) for x in (R(10000) for _ in range(50000)))

Original code:

>>> queue = deque(buildings)
>>> timeit(lambda:skyline(queue), number=1)
1.46421534800902

Revised code:

>>> timeit(lambda:list(skyline(buildings)), number=1)
0.9026356039103121

The revised code is about 40% faster than the original.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.