m00nlight

class KMP:
    def partial(self, pattern):
        """ Calculate partial match table: String -> [Int]"""
        ret = [0]
        
        for i in range(1, len(pattern)):
            j = ret[i - 1]
            while j > 0 and pattern[j] != pattern[i]:
                j = ret[j - 1]
            ret.append(j + 1 if pattern[j] == pattern[i] else j)

m00nlight

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

def lower_bound(nums, target):
    l, r = 0, len(nums) - 1
    while l <= r:
        mid = l + (r - l) / 2
        if nums[mid] >= target:
            r = mid - 1
        else:
            l = mid + 1
    return l
    

m00nlight

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

import sys
from heapq import heappush, heappop

class Dijkstra:
    def __init__(self, adjacents):
        self.adj = adjacents
        self.n = len(adjacents)

    def dijkstra(self, start):
        dis, vis, hq = {}, {}, []

m00nlight

import sys
import itertools

class RMQ:
    def __init__(self, n):
        self.sz = 1
        self.inf = (1 << 31) - 1
        while self.sz <= n: self.sz = self.sz << 1
        self.dat = [self.inf] * (2 * self.sz - 1)
    

m00nlight

from Queue import Queue
from threading import Thread
from random import randrange

queue = Queue(10)

class Consumer(Thread):
    def __init__(self, queue):
        Thread.__init__(self)
        self.queue = queue

m00nlight

import kotlin.math.abs

// https://leetcode.com/problems/target-sum/
// dp function:  dp[i][j] = dp[i - 1][j - nums[i]] + dp[i - 1][j + nums[i]]
class TargetSum {
    fun findTargetSumWays(nums: IntArray, target: Int): Int {
        val dp = Array(nums.size + 1) { mutableMapOf<Int, Int>().withDefault { 0 } }
        dp[0][0] = 1

        for (i in 1..nums.size) {

m00nlight

import random

def merge_sort(xs):
    """Inplace merge sort of array without recursive. The basic idea
    is to avoid the recursive call while using iterative solution. 
    The algorithm first merge chunk of length of 2, then merge chunks
    of length 4, then 8, 16, .... , until 2^k where 2^k is large than 
    the length of the array
    """
    

m00nlight

from random import randrange

def reservoir_sampling(items, k):
    """ 
    Reservoir sampling algorithm for large sample space or unknow end list
    See <http://en.wikipedia.org/wiki/Reservoir_sampling> for detail>
    Type: ([a] * Int) -> [a]
    Prev constrain: k is positive and items at least of k items
    Post constrain: the length of return array is k
    """