Skip to content

Instantly share code, notes, and snippets.

View chaoxu's full-sized avatar
😀

Chao Xu chaoxu

😀
  • University of Electronic Science and Technology of China
  • Chengdu, Sichuan, China
View GitHub Profile
bitonicMinimum :: (Integral a, Ord b) => (a->b)->a->b
bitonicMinimum f n
| g w /= g x = valley w x
| g w /= g y = valley w y
| g w /= g z = valley w z
| otherwise = minimum [g t|t<-[0..n-1]]
where (w,x,y,z) = (0, n `div` 4, n `div` 2, 3*n `div` 4)
valley x y
| x > y = bm x y (x+n)
| x < y = bm y (x+n) (y+n)
@chaoxu
chaoxu / minimaIncDec.go
Last active December 20, 2015 07:38
Find minima of an array with values that's first non-increasing then non-decreasing.
func min(a []int, l int, r int) int{
t := l
for i, v := range a[l:r] {
if a[t]>v {
t = i
}
}
return t
}
func minima(a []int, l int, r int) int{
@font-face {
font-family: 'STIXGeneral';
src: url('/files/fonts/stixgeneral-webfont.eot');
src: local('STIXGeneral'),local('STIXGeneral-Regular'), url('/files/fonts/stixgeneral-webfont.woff') format('woff'), url('/files/fonts/stixgeneral-webfont.ttf') format('truetype'), url('/files/fonts/stixgeneral-webfont.svg#webfontZXtFAA5Q') format('svg');
font-weight: normal;
font-style: normal;
}
@font-face {
font-family: 'STIXGeneral';
src: url('/files/fonts/stixgeneralitalic-webfont.eot');
@chaoxu
chaoxu / divisors.hs
Last active December 15, 2015 10:59
Find all the divisors of a positive integer
import Data.List
import Control.Monad
import Data.Numbers.Primes
divisors = sort . map (product . map (uncurry (^)))
. mapM (ap (zip . repeat . head) (enumFromTo 0 . length)) . group . primeFactors
--The simple version shows how the algorithm works
--but it produce large output.
import Data.Digits
data RegEx = Range Int Int | Epsilon | Or RegEx RegEx | Concat RegEx RegEx
alphabet = "\\d"
instance Show RegEx where
@chaoxu
chaoxu / RegIntIntval.hs
Last active March 5, 2024 09:01
Build a regular expression to match all non-negative integers between a and b.
module RegIntIntval (RegEx, matchIntRange, matchLessThan, matchGreaterThan) where
import Data.Digits
import Text.Regex.PCRE.Light
import Data.ByteString (pack)
import Data.ByteString.Internal (c2w)
import Data.Maybe
import Data.List
import FreeMonoidCompress
@chaoxu
chaoxu / spiral.hs
Last active December 13, 2015 20:28
Given a 2D array, print out(find the list) all the elements by a spiral from the outside. The array need to have dimension at least 1x1.
import Data.List
spiral xs = (take (n*m) . concat . concat . transpose) $ zipWith (build . ($ xs)) f v
where f = [id, init . reverse . transpose . tail, map (reverse . init) . reverse, map reverse . transpose . init]
v = [n,m-1,n-1,m-2]
n = length (head xs)
m = length xs
build s t = zipWith (\x l-> take (t-2*x) . drop x $ l) [0..] s
@chaoxu
chaoxu / lcs.hs
Created December 15, 2012 06:24 — forked from srayuws/lcsIO.hs
--ST Monad instead!
lcs :: (Eq a) => [a] -> [a] -> [a]
lcs s' t' = reverse $ build n m
where
a = runST $ do
b <- newArray ((0,0),(n,m)) 0
mapM_ (f b) $ range ((0,0),(n,m))
unsafeFreeze b
n = length s'
m = length t'
import Data.Array
lcs :: String -> String -> Int
lcs s t = a!(n,m)
where a = array ((0,0),(n,m)) [((x,y), f x y)|x<-[0..n],y<-[0..m]]
n = length s
m = length t
s'= array (0,n-1) $ zip [0..n-1] s
t'= array (0,m-1) $ zip [0..m-1] t
f :: Int->Int->Int
f i j
@chaoxu
chaoxu / Coins.java
Created August 18, 2012 20:42
Flushing Coins
package FlushingCoin;
import java.util.ArrayList;
import java.util.*;
public class Coins {
int[] d;
int[] c;
int[][] k;
int[][] x;