import Data.List

main :: IO()
main = do
    print $ "Hello world"
    print $ "Let's do it"

-- JUNE

-- first

getIndices :: [Int] -> (Int -> (Int, Int))
getIndices xs = (\x -> [(pos1, pos2) | (x1, pos1) <- zip xs [0..], (x2, pos2) <- zip xs [0..], x = x1 + x2 && pos1 /= pos2])

-- second

data NestedList a = Elem a | List [NestedList a]
    deriving Eq

mapNested :: (a -> b) -> NestedList a -> NestedList b
mapNested (Elem v) = Elem (f v)
mapNested (NestedList xs) = List (map (NestedList f) xs)

-- third

isPrime :: Int -> Bool
isPrime num = num > 1 && all (\x -> mod num x /= 0) [2 .. floor $ sqrt $ fromIntegral num]

traverseBFS :: BTree -> [[Char]]
traverseBFS t = takeWhile (/=[]) map (getLevel t) [0..]

getLevel :: BTree -> Int -> [Char]
getLevel Nil _ = 0
getLevel (Node value _ _ ) 0 = [value]
getLevel (Node value left right) k = getLevel left (k-1) ++ [value] ++ getLevel right (k-1)

height :: BTree -> Int
height Nil = 0
height (Node _ left right) = 1 + max (height left) (height right)

isPrimeDictionary :: BTree -> Vocabulary -> Bool
isPrimeDictionary t ws = isPrime $ sum [ k + length w | k <- [0 .. height t - 1], w <- ws, w `isInfixOf` getLevel t k]

type Vocabulary = [String]

data BTree = Nil | Node Char BTree BTree
    deriving (Show)

vocabulary :: Vocabulary
vocabulary = ["the", "a", "Some", "swimming", "liStS", "lisp"]

t1 :: BTree
t1 = Node 'a' (Node 't' (Node 'l' (Node 't' Nil Nil) (Node 'h' Nil Nil)) (Node 'i' (Node 'e' Nil Nil) (Node 'l' Nil Nil))) (Node 'h' (Node 's' (Node 'i' Nil Nil) (Node 'S' Nil Nil)) (Node 'a' (Node 't' Nil Nil) (Node 'S' Nil Nil)))

t2 :: BTree
t2 = Node 'a' (Node 't' (Node 'l' (Node 't' Nil Nil) (Node 'h' Nil Nil)) (Node 'i' (Node 'e' Nil Nil) (Node 'l' Nil Nil))) (Node 'h' (Node 's' (Node 'i' Nil Nil) (Node 's' Nil Nil)) (Node 'p' (Node 'p' Nil Nil) (Node 'S' Nil Nil)))

t3 :: BTree
t3 = Node 'a' (Node 't' (Node 'l' Nil Nil) (Node 'i' Nil Nil)) (Node 'h' (Node 's' Nil Nil) (Node 'p' Nil Nil))

-- forth task

findJudge :: Int -> [(Int, Int)] -> Int
findJudge n g = convert $ filter isJudge [1..n]
    where
        convert :: [Int] -> Int
        convert [] = -1
        convert (x:_) = x

        isJudge :: Int -> Bool
        isJudge = \x -> trustedByEveryone x && trustsNoOne x

        trustedByEveryone :: Int -> Bool
        trustedByEveryone x = n - 1 == length (nub $ map fst (filter (\ (a , b) -> b == x) g))

        trustsNoOne :: Int -> Bool
        trustsNoOne x = null [a | (a, _) <- g, a == x]

-- JULY

-- first

removeKth :: Int -> [a] -> [a]
removeKth n xs = helper xs 1
    where
        helper :: [a] -> Int -> [a]
        helper [] _ = []
        helper (x:xs) index
            | index == n = helper xs 1
            | otherwise = x : helper xs (index+1)

-- second

factorize :: Int -> [Int]
factorize num = helper num 2
    where
        helper :: Int -> Int -> [Int]
        helper 1 _ = []
        helper leftover divs
            | mod leftover divs == 0 = divs : helper (div leftover divs) divs
            | otherwise = helper leftover (divs+1)

-- third

poly :: [Int] -> (Int, Int)
poly xs = (\x -> sum [n * (x ^ i) | (n, i) <- zip xs [0 .. length xs]])

-- forth

data BTree = Empty | Node Int BTree BTree

deepestLeavesSum :: BTree -> Int
deepestLeavesSum t = sum $ getLevel t (height t - 1)

getLevel :: BTree -> Int -> [Int]
getLevel Empty _ = []
getLevel (Node value _ _) 0 = [value]
getLevel (Node value left right) k = getLevel left (k-1) ++ [value] ++ getLevel right (k-1)

height :: BTree -> Int
height Empty = 0
height (Node _ left right) = 1 + max (height left) (height right)

t3 :: BTree
t3 = Node 1 (Node 2 (Node 4 (Node 7 Empty Empty) Empty) (Node 5 Empty Empty)) (Node 3 Empty (Node 6 Empty (Node 8 Empty Empty)))

t4 :: BTree
t4 = Node 1 (Node 2 (Node 4 Empty Empty) Empty) (Node 3 Empty Empty)

-- AUGUST

-- first

listOfIndexes :: Int -> [Int] -> [Int]
listOfIndexes n xs = [index | (x, index) <- zip xs [0 .. length xs], x == n]

-- second

digits :: Int -> [Int]
digits = map digitToInt . show

decreasing :: Int -> Bool
decreasing [] = False
decreasing (x:xs)
    | length xs == 1 = head xs < x
    | x > head xs = decreasing xs
    | otherwise = False

decDigits :: Int -> Digits
decDigits n = decreasing (digits n)

-- third

averageFunction :: (Fractional a, RealFrac a) => [a -> a] -> a -> a
averageFunction fs n = roundN (average $ map (\f -> f n) fs) 6

average :: (Fractional a) => [a] -> a
average xs = sum xs / fromIntegral (length xs)

roundN :: (Fractional a, RealFrac a) => a -> Int -> a
roundN x n = fromIntegral (round (x * (10 ^ n))) / (10 ^ n)

-- forth

isBalanced :: BTree -> Bool
isBalanced Empty = True
isBalanced (Node _ l r)
    | abs (height l - height r) <= 1 = isBalanced l && isBalanced r
    | otherwise = False

height :: BTree -> Int
height Empty = 0
height (Node _ l r) = 1 + max (height l) (height r)

data BTree = Empty | Node Int BTree BTree

t1 :: BTree
t1 = Node 5 Empty (Node 4 (Node 5 Empty Empty) (Node 7 Empty Empty))

t2 :: BTree
t2 = Node 5 (Node 3 Empty Empty) (Node 4 (Node 5 Empty Empty) (Node 7 Empty Empty))

-- JANUARY

-- first

squareDigits :: Int-> Int
squareDigits n
    | n < 0 = (*(-1)) $ read $ concatMap (show.(^2).digitToInt) (show $ abs n)
    | otherwise = read $ concatMap (show.(^2).digitToInt) (show $ abs n)

 -- second

data Stock = Stock String Int
stocks :: [Stock]
stocks = [Stock "ABAR" 200, Stock "CDXE" 500, Stock "BKWR" 250, Stock "BTSQ" 890, Stock "DRTY" 600]

stocklist :: [Stock] -> [Char] -> [(Char, Int)]
stocklist ss xs = [(code, sum [n | (Stock m n) <- ss, head m == code]) | code <- xs]

 -- third

 matching :: String -> [(Int, Int)]
matching xs = helper (zip xs [0 ..]) []
 where
     helper :: [(Char, Int)] -> [(Int, Int)] -> [(Int, Int)]
     helper [] _ = []
     helper (('[',i):xs) stack = helper xs ((i,-1) : stack)
     helper ((']', j):xs) ((i, -1):stack) = (i, j) : helper xs stack
     helper (_:xs) stack = helper xs stack

 -- forth

data BTree a = Nil | Node a (BTree a) (BTree a)

t1 :: BTree Char
t1 = Node 'H' (Node 'a' (Node 'k' Nil Nil) (Node 'e' Nil Nil)) (Node 's' (Node 'l' Nil Nil) (Node 'l' Nil Nil))

isPerfectlyBalanced :: BTree a -> Bool
isPerfectlyBalanced t = 2^height t - 1 == size t

height :: BTree a -> Int
height Nil = 0
height (Node _ l r) = 1 + max (height l) (height r)

size :: BTree a -> Int
size Nil = 0
size (Node _ l r) = 1 + size l + size r

-- SEPTEMBAR

-- first

bestStudents :: [(Name,Grade)] -> [Name]
bestStudents xs = [name | (name, gr) <- xs, gr == maxGrade xs]

maxGrade :: [(Name,Grade)] -> Double
maxGrade xs = maximum [gr | (_, gr) <- xs]

type Name = String
type Grade = Double

-- second

iterator :: [Int] -> (Int -> Int) -> Bool
iterator xs f = helper xs
    where
        helper [] = True
        helper (x:xs)
            | null xs = True
            | head xs == f x = helper xs
            | otherwise = False

-- third

f :: Int -> Int
f = listToFunction [1, 2, 3]

listToFunction :: [Int] -> (Int -> Int)
listToFunction lst = (\x -> sum [xi + 10 | xi <- lst, xi == x])

-- forth

getLevel :: BTree -> Int -> [Int]
getLevel Nil _ = []
getLevel (Node v Nil Nil) 0 = [v]
getLevel (Node v l r) k = getLevel l (k - 1) ++ getLevel r (k - 1)

height :: BTree -> Int
height Nil = 0
height (Node _ l r) = 1 + max (height l) (height r)

data BTree = Nil | Node Int BTree BTree

tree :: BTree
tree = Node 1 (Node 2 (Node 4 (Node 8 Nil Nil) (Node 9 Nil Nil)) (Node 5 Nil (Node 10 Nil Nil))) (Node 3 (Node 6 Nil (Node 11 Nil Nil)) (Node 7 Nil (Node 12 Nil Nil)))

-- additional tasks from third preparation

-- first

seriesSum :: Double -> Int -> Double
seriesSum x n = sum [s | i <- [1..n], s <- [x^i + fromIntegral (i^2) + 1]]

-- second

kthNumber :: [Int] -> (Int -> Bool) -> (Int -> Int)
kthNumber xs p = (\k -> if length filtered < k then error "No such number" else filtered!!(k-1))
    where
        filtered = (filter p xs)

-- third

getCriticalBalance  ::  ([Account],  [Person])  ->  (Person  -> Bool)  ->  Balance  ->  [(PersonID,  Balance)]
getCriticalBalance (accs, ppl) p s = nub $ [(id, sum (getBalancesById db id)) | (_, aId, bal) <- accs, (id, _, home) <- filter p ppl, aId == id, bal < s]

getBalancesById :: ([Account], [Person]) -> PersonID -> [Balance]
getBalancesById (accs, ps) pId = [b | (_, p, b) <- accs, pId == p]

db = ([(1, 1, 10), (2, 1, 11), (3, 1, 12), (4, 2, 3), (5, 2, 1), (6, 3, 2), (7, 3, 3), (8, 4, 12)], [(1, "Ivan", "Varna"), (2, "Petar", "Burgas"), (3, "Georgi", "Varna"), (4, "Yordan", "Plovdiv")])

fromVarna :: Person -> Bool
fromVarna (_, _, "Varna") = True
fromVarna _ = False

type PersonID = Int
type Name = String
type City = String
type AccountID = Int
type Balance = Double
type Person = (PersonID, Name, City)
type Account = (AccountID, PersonID, Balance)

-- forth

findNodes  ::  BTree  ->  [Int]
findNodes Empty = []
findNodes c@(Node v l r)
    | v > sumOfChildren c = sort $ v : findNodes l ++ findNodes r
    | otherwise = sort $ findNodes l ++ findNodes r

sumOfChildren :: BTree -> Int
sumOfChildren Empty = 0
sumOfChildren (Node _ (Node v1 _ _) (Node v2 _ _)) = v1 + v2
sumOfChildren (Node _ (Node v1 _ _) _) = v1
sumOfChildren (Node _ _ (Node v2 _ _)) = v2
sumOfChildren (Node _ Empty Empty) = maxBound :: Int

data BTree = Empty | Node Int BTree BTree

t1 :: BTree
t1 = Node 1 (Node 12 (Node 2 Empty Empty) (Node 3 Empty Empty)) (Node 20 (Node 17 (Node 13 Empty Empty) Empty) Empty)

t2 :: BTree
t2 = Node 10 (Node 2 Empty (Node 3 (Node 4 Empty Empty) Empty)) (Node 11 (Node 1 Empty Empty) (Node 6 Empty Empty))

-- first


findNb :: Integer -> Integer
findNb m = helper m 1
    where
        helper 0 i = i - 1
        helper m i
            | m < 0 = -1
            | otherwise = helper (m - i ^ 3) (i + 1)

-- second

dominates :: (Int -> Int) -> (Int -> Int) -> [Int] -> Bool
dominates f g xs = and [abs (f x) >= abs (g x) | x <- xs]

-- third

splitPoints :: Point -> Double -> [Point] -> ([Point],[Point])
splitPoints p r ps = (filter (isInCircle p r) ps, filter (not . isInCircle p r) ps)

isInCircle :: Point -> Double -> Point -> Bool
isInCircle (x1, y1) r (x2, y2) = sqrt ((x2 - x1) ^ 2 + (y2 - y1) ^ 2) <= r

type Point = (Double,Double)

-- forth

isBinarySearchTree :: BTree -> Bool
isBinarySearchTree t = sort (traverseDFS t) == traverseDFS t

traverseDFS :: BTree -> [Int]
traverseDFS Empty = []
traverseDFS (Node v l r) = traverseDFS l ++ [v] ++ traverseDFS r

data BTree = Empty | Node Int BTree BTree

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

-- first

biggestNumber :: [Int] -> Int
biggestNumber xs = listToInt $ reverse $ sort xs

listToInt :: [Int] -> Int
listToInt xs = helper xs 0
    where
        helper [] num = num
        helper (x:xs) num = helper xs (num * 10 + x)

-- second

intersectionPoints :: (Int -> Int) -> (Int -> Int) -> Int -> Int -> [Int]
intersectionPoints f g x y = [p1 | (p1,p2) <- zip [f p1 | p1 <- [min x y..max x y]] [g p2 | p2 <- [min x y..max x y]], p1 == p2]

-- third

levelSum :: (Num a) => BTree a -> Int -> a
levelSum Nil _ = 0
levelSum (Node v _ _) 0 = v
levelSum (Node v l r) k = levelSum l (k - 1) + levelSum r (k - 1)

cone :: (Num a, Ord a) => BTree a -> Bool
cone Nil = True
cone (Node v Nil Nil) = True
cone t@(Node v l r) = levelSum t 0 < levelSum t 1 && cone l && cone r

data BTree a = Nil | Node a (BTree a) (BTree a)

numberBTree :: BTree Int
numberBTree = Node 10 (Node 5 (Node 1 Nil Nil) (Node 9 Nil Nil)) (Node 6 (Node 8 Nil Nil) (Node 7 Nil Nil))

-- first

applyEveryKth :: (a -> a) -> Int -> [a] -> [a]
applyEveryKth f k xs = helper 1 xs
    where
        helper _ [] = []
        helper i (x:xs)
            | i == k = f x : helper 1 xs
            | otherwise = x : helper (i + 1) xs

-- second

speak :: String -> (Char -> String)
speak str c = foldl (\ acc (x,pos) ->  if x==c then acc ++ show pos else acc ++ [x]) [] $ zip str $ reverse [0 .. length str - 1]

-- third

data Food = ApplePie | Burger | Chicken
    deriving (Show, Eq)
data Weather = Sunny | Rainy
    deriving (Show, Eq)

cook :: [Food] -> [Weather]
cook [] = []
cook [_] = []
cook (f1:f2:xs)
    | f1 == f2 = Sunny : cook (f2:xs)
    | otherwise = Rainy : cook (f2:xs)

-- forth

deepestNodesSum :: (Int -> Bool) -> BTree -> Int
deepestNodesSum f t = sum [x | x <- getLevel t (height t - 1), f x]

height :: BTree -> Int
height Empty = 0
height (Node _ l r) = 1 + max (height l) (height r)

getLevel :: BTree -> Int -> [Int]
getLevel Empty _ = []
getLevel (Node v _ _ ) 0 = [v]
getLevel (Node v l r) k = getLevel l (k-1) ++ getLevel r (k - 1)

data BTree = Empty | Node Int BTree BTree

t1 :: BTree
t1 = Node 1 (Node 2 (Node 4 (Node 7 Empty Empty) Empty) (Node 5 Empty Empty)) (Node 3 Empty (Node 6 Empty (Node 8 Empty Empty)))

t2 :: BTree
t2 = Node 1 (Node 2 (Node 4 Empty Empty) Empty) (Node 3 Empty Empty)