Hi,

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

### Like this:

Like Loading...

*Related*