-- 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 (лявото поддърво не е двоично дърво за търсене)