#lang racket

;;; Задача 1

(define (pair-compose fs xs)
  (cond [(= (length fs) 0) 0]
        [(= (length fs) 1) (lambda (y) ((car fs) (car xs) y))]
        [else (lambda (y) (+ ((first fs) (first xs) ((second fs) (second xs) y))
                             ((pair-compose (cddr fs) (cddr xs)) y) ))]))

;; Примери
(define fs (list *
                 (lambda (x y) (* x x x y))
                 (lambda (x y) (+ x 1 y))
                 (lambda (x y) (- x (+ 1 y)))
                 (lambda (x y) (* x y 2))))
(define xs '(1 2 3 4 5))
((pair-compose fs xs) 5) ; → 92

;;; Задача 2

(define (pop&pushb lst elem)
  (append (cdr lst) (list elem)))

(define (range-doesnt-cover? range ranges)
  (cond [(null? ranges) #t]
        [(and (<= (car range) (cdar ranges))
              (>= (cdr range) (caar ranges))) #f]
        [else (range-doesnt-cover? range (cdr ranges))]))

;; Превръща всички двойки '(позиция . височина) в двойки '(позиция . позиция)
(define (treehs-to-range treehs) ; treeh са дървета от тип '(позиция . височина)
  (define current (cons (caar treehs) (caar treehs)))
  (if (null? (cdr treehs))
    (list current)
    (list* current (treehs-to-range (cdr treehs)))))

(define (fell-left treeh) ; treeh са дървета от тип '(позиция . височина)
  (cons (- (car treeh) (cdr treeh)) (car treeh)))

(define (fell-right treeh) ; treeh са дървета от тип '(позиция . височина)
  (cons (car treeh) (+ (car treeh) (cdr treeh))))

(define (woodcutters xs)
  (define (calc xs trees count)
    ;; Третираме всяко дърво, което не е паднало, като интервал [xi, xi]
    ;; Така лесно проверяваме дали паднало дърво би се засекло с някое стоящо или друго паднало
    ;; За опростение на кода, винаги (car trees) трябва да бъде [xi, xi] представянето на (car xs),
    ;; затова ползваме pop&pushb
    (cond [(null? xs) count]
          ; Ако падне в ляво и не покрива нищо
          [(range-doesnt-cover? (fell-left  (car xs)) (cdr trees))
            (calc (cdr xs) (pop&pushb trees (fell-left  (car xs))) (add1 count))]
          ; Ако падне в дясно и не покрива нищо
          [(range-doesnt-cover? (fell-right (car xs)) (cdr trees))
            (calc (cdr xs) (pop&pushb trees (fell-right (car xs))) (add1 count))]
          [else
            (calc (cdr xs) (pop&pushb trees (car trees)) count)]))
  (calc xs (treehs-to-range xs) 0))

;; Примери
(woodcutters '((1 . 2) (2 . 1) (5 . 10) (10 . 9) (19 . 1))) ; → 3
(woodcutters '((1 . 2) (2 . 1) (5 . 10) (10 . 9) (20 . 1))) ; → 4
(woodcutters '((10 . 4) (15 . 1) (19 . 3) (20 . 1))) ; → 4
(woodcutters '((1 . 7) (3 . 11) (6 . 12) (7 . 6) (8 . 5) (9 . 11)
  (15 . 3) (16 . 10) (22 . 2) (23 . 3) (25 . 7) (27 . 3) (34 . 5)
  (35 . 10) (37 . 3) (39 . 4) (40 . 5) (41 . 1) (44 . 1) (47 . 7)
  (48 . 11) (50 . 6) (52 . 5) (57 . 2) (58 . 7) (60 . 4) (62 . 1)
  (67 . 3) (68 . 12) (69 . 8) (70 . 1) (71 . 5) (72 . 5)
  (73 . 6) (74 . 4) ) ) ; → 10