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->[1] foreach $b->[0]..($b->[2]-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)
    {
    result.add(index);
    result.add(height);
    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)
                {
                    result.add(index);
                    result.add(height);
                    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) = 
         (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)
    
  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
        
    
    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.

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

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

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: