[FP/HW2] Solved second exercise

1 files changed, 41 insertions, 30 deletions

diff --git a/Year 2/Functional Programming/hw2.rkt b/Year 2/Functional Programming/hw2.rkt
index 4cff576..336bb5a 100644
--- a/Year 2/Functional Programming/hw2.rkt
+++ b/Year 2/Functional Programming/hw2.rkt
@@ -19,41 +19,52 @@
 
 ;;; Задача 2
 
-(define (inside-range? point range)
-  (and (<= (car range) point) (>= (cdr range) point)))
+(define (pop&pushb lst elem)
+  (append (cdr lst) (list elem)))
 
-(define (range-covers? range ranges)
-  (cond [(null? ranges) #f]
-        [(or (inside-range? (car range) (car ranges)) (inside-range? (cdr range) (car ranges))) #t]
-        [else (range-covers? range (cdr ranges))]))
+(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 (woodcutters xs)
-  (define (calc-check xs fallen count)
-    (if (null? xs)
-      count
-      (calc xs fallen count)))
-  (define (calc xs fallen count)
-    
-    (define leftRange (cons (- (car (car xs)) (cdr (car xs))) (car (car xs))))
-    (define rightRange (cons (cdr (car xs)) (+ (car (car xs)) (cdr (car xs)))))
+;; Превръща всички двойки '(позиция . височина) в двойки '(позиция . позиция)
+(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 withLeft (if (range-covers? leftRange fallen)
-                         0
-                         (calc-check (cdr xs) (list* leftRange fallen) (add1 count))))
-    (define withRight (if (range-covers? rightRange fallen)
-                          0
-                          (calc-check (cdr xs) (list* rightRange fallen) (add1 count))))
-    (define noRange (calc-check (cdr xs) fallen count))
+(define (fell-right treeh) ; treeh са дървета от тип '(позиция . височина)
+  (cons (car treeh) (+ (car treeh) (cdr treeh))))
 
-    (max withLeft withRight noRange))
-  (calc-check xs '() 0))
+(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
+(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