aboutsummaryrefslogtreecommitdiff
path: root/lib/Utils.hs
blob: e0f9d6255503bcb44ac99242914645bceff309eb (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
module Utils where 

import           Data.Char (digitToInt)
import           Control.Monad
import           Data.Either
import           Data.List (inits, tails)
import           Data.Map (Map)
import qualified Data.Map as Map

binaryToInt :: String -> Int
binaryToInt = foldl (\a x -> a * 2 + digitToInt x) 0

countElem :: (Eq a) => a -> [a] -> Int
countElem c ls = sum $ map (fromEnum . (== c)) ls

xor :: Bool -> Bool -> Bool
xor a b = (not a && b) || (a && not b)

right :: Either a b -> b
right (Right b) = b
right _ = undefined

bet k (l, u) = k >= l && k <= u
bet' k (l, u) = k > l && k < u

-- combine filter predicates
(&+) :: (a -> Bool) -> (a -> Bool) -> (a -> Bool)
(&+) = liftM2 (&&)

(|+) :: (a -> Bool) -> (a -> Bool) -> (a -> Bool)
(|+) = liftM2 (||)

howMany :: (a -> Bool) -> [a] -> Int
howMany predicate = length . filter predicate

sublists :: [a] -> [[a]]
sublists = concatMap inits . tails

windows :: Int -> [a] -> [[a]]
windows m = foldr (zipWith (:)) (repeat []) . take m . tails

kadane :: [Int] -> Int
kadane = go 0 0
    where go :: Int -> Int -> [Int] -> Int
          go best _ [] = best
          go best current (l:ls) = go (max best (current + l)) (max current (current + l)) ls

-- tuple stuff

add (x, y) (a, b) = (x+a, y+b)
shear c (x, y) = (c * x, c * y)
inside  (p, q) (r, s) (a, b) = bet a (p, r) && bet b (q, s)
inside' (p, q) (r, s) (a, b) = bet' a (p, r) && bet' b (q, s)

rotate (x, y) t = (nx, ny)
    where nx = x*cos(pi*t/180) - y*sin(pi*t/180)
          ny = x*sin(pi*t/180) + y*cos(pi*t/180)

-- [f, f.f, f.f.f, ...]
repeatF f = f : map (f .) (repeatF f) 

makeGrid :: String -> (Map (Int, Int) Char, Int, Int)
makeGrid s = (grid, width, height) where
    rows = lines s
    grid = Map.fromList [((x, y), a) | (y, row) <- zip [0..] rows , (x, a) <- zip [0..] row]
    width = length (head rows)
    height = length rows

-- number theory 

egcd :: Int -> Int -> (Int, Int)
egcd _ 0 = (1, 0)
egcd a b = (t, s - q * t)
    where
        (s, t) = egcd b r
        (q, r) = a `quotRem` b

modInv :: Int -> Int -> Maybe Int
modInv a b =
    case egcd a b of
      (x, y)
        | a * x + b * y == 1 -> Just x
        | otherwise -> Nothing

-- from rosetta code
chineseRemainder :: [(Int, Int)] -> Maybe Int
chineseRemainder ls =
    zipWithM modInv crtModulii modulii >>=
        (Just . (`mod` modPI) . sum . zipWith (*) crtModulii . zipWith (*) residues)
            where
                residues = map fst ls
                modulii = map snd ls
                modPI = product modulii
                crtModulii = (modPI `div`) <$> modulii