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
|
