Skyline Problem in Scheme


I’ve solved another puzzle. The skyline problem.  I have to admit though, I started out totally wrong. I set out to write a solution that would only require a single pass over the list of buildings, which was really hard. It would have been doable if all buildings only overlapped with the last one. I spent a few hours going down that path before I realized I could do it so much simpler.

The solution is done in Scheme (<3) for once. On Stack Overflow there is a code-golf for the shortest solution but I didn’t manage to do that though. My solution counts 690 characters, so I can’t really compete with the current record of 40 characters.  I’m just glad I solved it!

(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 
                           (vector-ref skyline-vector index) 
                           (cadr building)))
             (if (< index  (- (caddr building) 1))
                 (update-vector (+ 1 index)))))
    ; 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))))))
    ; Add the last coordinate to the vector.
    (append output (list (vector-length skyline-vector) 0))))
(equal? solution (create-skyline buildings))

Leave a Reply

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

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

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s