## Skyline Puzzle

### September 5, 2014

The Skyline Puzzle is a classic programming exercise; it draws a silhouette of a city skyline by blocking out portions of buildings that are masked by taller buildings. A city is a list of buildings specified as triples containing left edge, height, and right edge. For instance, the list of triples `(1 11 5) (2 6 7) (3 13 9) (12 7 16) (14 3 25) (19 18 22) (23 13 29) (24 4 28)`

encodes the eight buildings shown at the left of the diagram, and the path `1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0`

encodes the skyline shown at the right of the diagram, where the odd-indexed elements of the output are the x-coordinate of the skyline and the even-indexed elements of the output are the y-coordinate of the skyline. (It makes more sense to me that the output should look like `(1 11) (3 13) (9 0) (12 7) (16 3) (19 18) (22 3) (23 13) (29 0)`

but that’s not the way the puzzle is ever specified.) Notice that the second (2 6 7) and eighth (24 4 28) buildings are not part of the skyline.

Your task is to write a program that takes a list of buildings and returns a skyline. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

In perl

Java 8 solution

public static List skyLinePuzzle(List buildings)

{

int start = buildings.stream().map(b -> b.start).min(Integer::compareTo).orElse(0);

int end = buildings.stream().map(b -> b.end).max(Integer::compareTo).orElse(start);

List result = newArrayList();

int lastHeight = -1;

for (int i = start; i b.start <= index && index

b.height).max(Integer::compareTo).orElse(0);if (height != lastHeight)

{

result.add(index);

result.add(height);

lastHeight = height;

}

}

return result;

}

Java 8 with Formatter from http://java2html.blogspot.de/

Haskell. Make a list of start/end positions and heights. Sort it, then scan to find maximum height at each point, finally filter out redundant entries and flatten list:

Slightly improved version: Haskell insert/insertBy keeps list ordered, so can just use head to get maximum height (a serious implementation might use a heap-based priority queue here). Complexity is m n log n, for n buildings, maximum overlapping buildings m.

In Python. This solution is way more complicated than it should be, but this should also work for real x, y coordinates and can handle large cities as well. First sort all buidling on height (descending) and then build a BST. If a building is overlapping with a higher building, cut off the overlapping part and feed it down the tree. The result is a tree with non-verlapping intervals, that are visible in the skyline.

On Stack Overflow you can find much shorter solutions.

My lengthy Scheme solution:

A simple solution in Python 3 –

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

def find_skyline(blds):

# ensure the building coordinates are x – axis sorted

blds.sort()

# transform the coodinates to left & right edges (right -ve height)

points = []

for p in blds:

points.append((p[0], p[1]))

points.append((p[2], -p[1]))

points.sort()

#print(points) # print for debuggung

top = 0 # top / ceiling for traversal

drp = 0 # height stack for right edge

skln = [] # skyline points

for p in points:

if p[1] > 0:

# left edges

if p[1] > top:

top = p[1]

skln.append((p[0], top))

drp += p[1]

else:

# right edges

drp += p[1]

if abs(p[1]) > drp:

top = drp

skln.append((p[0], top))

return skln

print(find_skyline (p))

#(1 11) (3 13) (9 0) (12 7) (16 3) (19 18) (22 3) (23 13) (29 0)

Simple Python 3 solution –

A simple Clojure solution; this is not the most efficient, as it makes multiple passes over the list of buildings to compute the height at each point.