Skip to content

Instantly share code, notes, and snippets.

@m00nlight
m00nlight / gist:117e44a2c8cbf8b45c09
Last active August 29, 2015 14:16
Haskell Range Minimum Query
import Data.List.Split
import qualified Data.Vector as V
rmqBuild :: [Int] -> (Int, V.Vector Int)
rmqBuild xs =
let l = length xs
n = until (\ x -> x >= l) (*2) 1
inf = maxBound :: Int
f ys = map minimum $ chunksOf 2 ys
in (n ,V.fromList $ concat $
@m00nlight
m00nlight / gist:18df8064dda4fcd3bf8c
Created March 14, 2015 15:33
Haskell lowerBound and upperBound
import qualified Data.Vector as V
import qualified Data.List as L
accSum :: Num t => [t] -> [t]
accSum xs = aux xs 0
where aux [] a = []
aux (x:xs') a = (a + x) : aux xs' (a + x)
lowerBound :: (Num a, Ord a) => V.Vector a -> a -> Int
@m00nlight
m00nlight / gist:2868363ec217f97072b4
Created March 30, 2015 09:15
Simple Haskell arithmetic parser and evaluator
import Text.Parsec
import Text.Parsec.Expr
import Text.Parsec.Combinator
import Data.Functor
data Exp = Num Int
| Add Exp Exp
| Sub Exp Exp
| Mul Exp Exp
| Div Exp Exp
@m00nlight
m00nlight / DFA.hs
Last active August 29, 2015 14:18 — forked from romac/DFA.hs
{-# LANGUAGE ExistentialQuantification #-}
module DFA (
DFA,
runDFA,
scanDFA,
isAccepting,
) where
import Data.Set (Set)
@m00nlight
m00nlight / gist:4c5d3e44f38298714092
Created April 13, 2015 03:19
The while language parser in haskell
import System.IO
import Control.Monad
import Text.ParserCombinators.Parsec
import Text.ParserCombinators.Parsec.Expr
import Text.ParserCombinators.Parsec.Language
import qualified Text.ParserCombinators.Parsec.Token as Token
data BExpr = BoolConst Bool
| Not BExpr
@m00nlight
m00nlight / gist:cf89e14d93ed69c204f8
Last active June 30, 2019 06:10
python binary index tree
from __future__ import division
class BinaryIndexTree:
def __init__(self, n):
self.sz = n
self.vals = [0] * (n + 1)
def update(self, idx, delta):
"add c to the value at index idx"
@m00nlight
m00nlight / gist:5b6eeebc28ab15a35b10
Last active September 27, 2022 23:24
Haskell segment tree with lazy propagation
import Control.Applicative
import Control.Monad
import qualified Data.ByteString.Char8 as BS
import Data.List
import Data.Maybe
import qualified Data.Vector as V
data SegTree a =
Node {
val :: a
@m00nlight
m00nlight / gist:ddb333a6d6b10a5bac38
Created June 28, 2015 09:32
Basic python graph algorithm library
from __future__ import division
from collections import defaultdict, deque
from heapq import heappush, heappop
from sys import stdin
class UnionFindSet:
def __init__(self, nodes):
self.fa = {}
for n in nodes:
self.fa[n] = n
@m00nlight
m00nlight / gist:51171c9ba28b979fffd2
Created July 6, 2015 09:38
Ruby decorator pattern
module Decorator
def initialize(decorated)
@decorated = decorated
end
def method_missing(method, *args)
args.empty? ? @decorated.send(method) : @decorated.send(method, args)
end
end
@m00nlight
m00nlight / list.py
Created August 28, 2015 05:25
Python list function
class Solution(object):
def addTwoNumbers(self, l1, l2):
ll1 = self.list2naive(l1)
ll2 = self.list2naive(l2)
a = 0 if ll1 == [] else int(''.join(map(str, ll1))[::-1])
b = 0 if ll2 == [] else int(''.join(map(str, ll2))[::-1])
res = a + b
return self.naive2list(map(int, list(str(res)[::-1])))
def list2naive(self, l):