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
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))))))