## 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.

Pages: 1 2

### 10 Responses to “Skyline Puzzle”

1. 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-> foreach \$b->..(\$b->-1);
}
foreach (1 .. @r) {
printf '(%d %d) ',\$_, length \$r[\$_] unless \$r[\$_] == \$r[\$_-1];
}
print "\n";
}
```
2. András said

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)
{
lastHeight = height;
}
}
return result;
}

3. András said

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)
{
lastHeight = height;
}
}
return result;
}```
4. matthew said

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)
```
5. matthew said

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) =
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  . 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)
```
6. Paul said

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

"""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:
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:
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))
for b in buildings[1:]:
skyline(get_intervals_from_tree(root))
```

On Stack Overflow you can find much shorter solutions.

7. Christophe said

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)
(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))
```
8. Abhi said

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, p))
points.append((p, -p))
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 > 0:
# left edges
if p > top:
top = p
skln.append((p, top))
drp += p
else:
# right edges
drp += p
if abs(p) > drp:
top = drp
skln.append((p, 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)

9. Abhi said

Simple Python 3 solution –

``` 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, p)) points.append((p, -p)) 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 > 0: # left edges if p > top: top = p skln.append((p, top)) drp += p else: # right edges drp += p if abs(p) > drp: top = drp skln.append((p, 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) ```

10. 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))))))
```