[FP] Solved second exam from 2021

1 files changed, 71 insertions, 0 deletions

diff --git a/Year 2/Functional Programming/Exam2-2021.hs b/Year 2/Functional Programming/Exam2-2021.hs
new file mode 100644
index 0000000..f68faa9
--- /dev/null
+++ b/Year 2/Functional Programming/Exam2-2021.hs
@@ -0,0 +1,71 @@
+-- Exercise 1
+
+findNb :: Integer -> Integer
+findNb m = calc 1 m 0
+  where
+    calc curr m n
+      | m < 0 = -1
+      | m == 0 = n
+      | otherwise = calc (curr + 1) (m - curr^3) (n + 1)
+
+-- Exercise 2
+
+dominates :: (Int -> Int) -> (Int -> Int) -> [Int] -> Bool
+dominates _ _ [] = True
+dominates f g xs = abs (f (head xs)) >= abs (g (head xs)) && dominates f g (tail xs)
+
+-- Exercise 3
+
+type Point = (Double,Double)
+
+splitPoints :: Point -> Double -> [Point] -> ([Point],[Point])
+splitPoints (px, py) r ps = (filter (\(x, y) -> (x^2 + y^2) <= ((px+r)^2 + (py+r)^2)) ps, filter (\(x, y) -> (x^2 + y^2) > ((px+r)^2 + (py+r)^2)) ps)
+
+-- Exercise 4
+
+data BTree = Empty | Node Int BTree BTree
+
+isBinarySearchTree :: BTree -> Bool
+isBinarySearchTree Empty = True
+isBinarySearchTree (Node n bt1 bt2) = smallerAndBigger bt1 [] [n] && smallerAndBigger bt2 [n] []
+  where
+    smallerAndBigger Empty _ _ = True
+    smallerAndBigger (Node n bt1 bt2) min max = all (n<) max && all (n>=) min && smallerAndBigger bt1 min (n:max) && smallerAndBigger bt2 (n:min) max
+
+-- main
+
+t1 :: BTree                                 --      8
+t1 = Node 8 (Node 3 (Node 1 Empty Empty)    --    /   \
+                    (Node 4 Empty Empty))   --   3     10
+            (Node 10 (Node 9 Empty Empty)   --  / \    / \
+                     (Node 14 Empty Empty)) -- 1   4  9   14
+
+t2 :: BTree                                 --      8
+t2 = Node 8 (Node 3 (Node 1 Empty Empty)    --    /   \
+                    (Node 4 Empty Empty))   --   3     10
+            (Node 10 (Node 5 Empty Empty)   --  / \    / \
+                     (Node 14 Empty Empty)) -- 1   4  5   14
+
+t3 :: BTree                                 --      8
+t3 = Node 8 (Node 3 (Node 5 Empty Empty)    --    /   \
+                    (Node 6 Empty Empty))   --   3     10
+            (Node 10 (Node 9 Empty Empty)   --  / \    / \
+                     (Node 14 Empty Empty)) -- 5   6  9   14
+
+main :: IO()
+main = do
+  print(findNb 1071225)         -- --> 45
+  print(findNb 40539911473216)  -- --> 3568
+  print(findNb 135440716410000) -- --> 4824
+  print(findNb 4183059834009)   -- --> 2022
+  print(findNb 91716553919377)  -- --> -1
+  print(findNb 24723578342962)  -- --> -1
+
+  print(dominates (+4) (*2) [1..4]) -- --> True
+  print(dominates (+4) (*2) [1..5]) -- --> False (5+4=9 < 5*2=10)
+
+  print(splitPoints (1,1) 5 [(1,2),(2,3),(10,15),(-1,1),(12,14)]) -- --> ([(1.0,2.0),(2.0,3.0),(-1.0,1.0)],[(10.0,15.0),(12.0,14.0)])
+
+  print(isBinarySearchTree t1) -- --> True
+  print(isBinarySearchTree t2) -- --> False (в дясното поддърво има стойности, по-малки от тази в корена)
+  print(isBinarySearchTree t3) -- --> False (лявото поддърво не е двоично дърво за търсене)