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