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
use strict; skyline( [qw(1 11 5)], [qw(2 6 7)], [qw(3 13 9)], [qw(12 7 16)], [qw(14 3 25)], [qw(19 18 22)], [qw(23 13 29)], [qw(24 4 28)], ); sub skyline { my @r; foreach my $b (@_) { $r[$_] |= '1' x $b->[1] foreach $b->[0]..($b->[2]-1); } foreach (1 .. @r) { printf '(%d %d) ',$_, length $r[$_] unless $r[$_] == $r[$_-1]; } print "\n"; }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/
public static List<Integer> skyLinePuzzle(List<Building> 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<Integer> result = newArrayList(); int lastHeight = -1; for (int i = start; i <= end; i++) { final int index = i; int height = buildings.stream().filter(b -> b.start <= index && index < b.end).map(b -> b.height).max(Integer::compareTo).orElse(0); if (height != lastHeight) { result.add(index); result.add(height); lastHeight = height; } } return result; }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:
#!/usr/bin/runghc import Data.List import Data.Function nmax [] = 0 nmax s = maximum s -- Make a list of position, height pairs, positive height is start -- of building, negative height is end. expand(l,h,r) = [(l,h),(r,-h)] -- Track the current buildings & get maximum height scan s [] = [] scan s ((m,h):t) = (m,nmax s'):scan s' t where s' = if h < 0 then delete (-h) s else insert h s -- Filter out redundant entries from list filt ((n,h):(n',h'):s) = if n == n' then filt ((n',h'):s) -- Same position else if h == h' then filt ((n,h):s) -- Same height else n:h:filt((n',h'):s) filt [(n,h)] = [n,h] filt [] = [] skyline = filt . scan [] . sortBy (compare `on` fst) . concatMap expand s = [(12,1,29),(1,11,5),(3,13,9),(12,7,16),(2,6,7),(14,3,25),(19,18,22),(23,13,29),(24,4,28)] main = print (skyline s)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.
#!/usr/bin/runghc import Data.List import Data.Function -- Make a list of position, height pairs, positive height is start -- of building, negative height is end. expand(l,h,r) = [(l,h),(r,-h)] -- Track the current buildings & get maximum height scan s [] = [] scan s ((m,h):t) = (m,head s'):scan s' t where s' = if h < 0 then delete (-h) s else insertBy (flip compare) h s -- Filter out redundant entries from list filt ((n,h):(n',h'):s) = if n == n' then filt ((n',h'):s) -- Same position else if h == h' then filt ((n,h):s) -- Same height else (n,h):filt((n',h'):s) filt s = s skyline = filt . scan [0] . sortBy (compare `on` fst) . concatMap expand -- Some extra, redundant, buildings here. s = [(12,1,29),(1,11,5),(1,11,5),(1,11,4),(1,10,5),(3,13,9), (12,7,16),(2,6,7),(14,3,25),(19,18,22),(23,13,29),(24,4,28)] main = print (skyline s)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.
from collections import namedtuple from operator import itemgetter 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)] Interval = namedtuple("Interval", "x value y") class Node(object): def __init__(self, value): self.value = value self.left = self.right = None # keft and right pointers def add_to_node(node, interval): """build a BST """ if interval.x < node.value.x: # excess to the left - trim, if necessary new_interval = Interval(interval.x, interval.value, min(interval.y, node.value.x)) if node.left: add_to_node(node.left, new_interval) else: node.left = Node(new_interval) if interval.y > node.value.y: # excess to the right - trim, if necessary new_interval = Interval(max(interval.x, node.value.y), interval.value, interval.y) if node.right: add_to_node(node.right, new_interval) else: node.right = Node(new_interval) def get_intervals_from_tree(root): """returns all non-verlapping intervals (sorted on x)""" intervals = [] stack = [root] while stack: node = stack.pop() if not node: continue intervals.append(node.value) stack.append(node.left) stack.append(node.right) return sorted(intervals) def skyline(sorted_intervals): lasty = sorted_intervals[-1].y for item in sorted_intervals: if item.x > lasty: print lasty, 0, print item.x, item.value, lasty = item.y print lasty, 0 buildings = sorted(BUILDINGS, key=itemgetter(1), reverse=True) #sort on height root = Node(Interval(*buildings[0])) for b in buildings[1:]: add_to_node(root, Interval(*b)) skyline(get_intervals_from_tree(root))On Stack Overflow you can find much shorter solutions.
My lengthy Scheme solution:
(define 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))) (define solution '(1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0)) ; Map a function over a vector. ; Function needs to parameters: ; The value and the index of the value. (define (vector-map! proc v) (let map ((index 0)) (vector-set! v index (proc (vector-ref v index) index)) (if (< index (- (vector-length v) 1)) (map (+ 1 index))))) (define (create-skyline buildings) ; Determine total width. (let ((width 0) (skyline-vector '()) (output '()) (current-height -1)) (map (lambda (building) (set! width (max width (caddr building)))) buildings) ; Create the vector with the proper width. (set! skyline-vector (make-vector width 0)) ; Loop over the buildings and update the vector. (map (lambda (building) (let update-vector ((index (car building))) (vector-set! skyline-vector index (max (vector-ref skyline-vector index) (cadr building))) (if (< index (- (caddr building) 1)) (update-vector (+ 1 index))))) buildings) ; Iterate over vector and create list. (vector-map! (lambda (value position) (if (and (not (eq? value current-height)) (not (equal? position 0))) (begin (set! current-height value) (set! output (append output (list position value)))))) skyline-vector) ; Add the last coordinate to the vector. (append output (list (vector-length skyline-vector) 0)))) (equal? solution (create-skyline buildings))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.
(def 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))) (defn height-at [buildings position] (let [overlapping-buildings (filter (fn [[l _ r]] (and (<= l position) (< position r))) buildings)] (reduce max 0 (map second overlapping-buildings)))) (defn skyline [buildings] (reduce (fn [accum position] (let [height (height-at buildings position) previous-height (last accum)] (if (= height previous-height) accum (conj accum position height)))) [] (range (ffirst buildings) (+ 2 (last (last buildings))))))