Skyline Puzzle
September 5, 2014
There are several ways to solve this problem. Our solution works in two passes: the first pass collects the maximum height at each x-coordinate, and the second pass outputs a portion of the skyline each time the height changes. Here’s the first pass:
(define (heights buildings)
(let* ((len (apply max (map caddr buildings)))
(hites (make-vector (+ len 1) 0)))
(do ((buildings buildings (cdr buildings)))
((null? buildings) (vector->list hites))
(let ((building (car buildings)))
(do ((x (car building) (+ x 1))) ((= x (caddr building)))
(vector-set! hites x
(max (vector-ref hites x) (cadr building))))))))
We cheat by making a pre-pass before the first pass to compute the width of the skyline, which is stored in the len
variable. The outer do
iterates over the input buildings and the inner do
iterates over the x-coordinates from each building’s left edge to its right edge. The second pass runs through the list of heights, printing output each time the height changes:
(define (skyline buildings)
(let loop ((x 0) (prev 0) (hites (heights buildings)) (skys (list)))
(cond ((null? hites) (reverse skys))
((= (car hites) prev) (loop (+ x 1) prev (cdr hites) skys))
(else (loop (+ x 1) (car hites) (cdr hites) (cons (car hites) (cons x skys)))))))
Here’s the output from the example problem:
> (skyline '((1 11 5) (2 6 7) (3 13 9) (12 7 16)
(14 3 25) (19 18 22) (23 13 29) (24 4 28)))
(1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0)
You can run the program at http://programmingpraxis.codepad.org/0YYexYt9.
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.