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.