Skip to content

Instantly share code, notes, and snippets.

View scvalex's full-sized avatar

Alexandru Scvorțov scvalex

View GitHub Profile
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAXN 5000000
int n;
char c[MAXN], *a[MAXN];
int pstrcmp(const void **x, const void **y) {
@scvalex
scvalex / bigdiv.py
Created March 13, 2010 20:58
Binary search division in Python
import sys
def bigmul(a, b):
"""r = a * b
where
r = bidmul(a, b)"""
xs = list(reversed(digits(a)))
ys = list(reversed(digits(b)))
zs = [0 for i in xrange(300)]
for i in xrange(len(ys)):
main :: IO ()
main = do
x <- getLine
y <- getLine
print (read x + read y)
@scvalex
scvalex / bdiv.hs
Created March 21, 2010 11:16
Binary search division
ultraDiv ∷ Integer → Integer → (Integer, Integer)
-- pre: 1 <= d <= n
-- post: a*d + b == n
-- && (A) x > d . (a*x > n)
-- where
-- (a, b) = ultraDiv n d
ultraDiv n d = bDiv n d 1 n
where
-- pre: same as ultraDiv
-- && d * lower <= n && d * upper > n
@scvalex
scvalex / gausselim.hs
Created April 3, 2010 19:21
Gaussian elimination on lists
-- PRE: xs is sorted and not null
-- POST: r is xs without the elements that vary by
-- more than err from the median
gausselim ∷ (Num a, Ord a) ⇒ a → [a] → [a]
gausselim err xs = filter good xs
where
middle = xs ‼ (length xs `div` 2)
good x = abs (x - middle) < err
@scvalex
scvalex / pi.py
Last active September 4, 2015 18:05
Calculate PI probabilistically
#!/usr/bin/python
from __future__ import print_function
import math, random
acErr = 1e-5
def inCircle(x, y):
"""inCircle(x, y) iff (x, y) is in the circle of radius 1 centered at
origin"""
@scvalex
scvalex / Owari.hs
Created April 25, 2010 22:25
Owari in Haskell
module Main where
import Data.Array.IArray
import Data.Array.Unboxed
import Data.Function
import Data.List
import Debug.Trace ( trace )
import System.IO.Unsafe ( unsafePerformIO )
import Text.Printf ( printf )
@scvalex
scvalex / Warshall.hs
Created May 4, 2010 21:00
Floyd-Warshall in 2 lines of Haskell
module Warshall where
import Data.Char ( isAlpha )
import Data.List ( nub, sort )
import System.Environment ( getArgs )
import Text.Parsec
import Text.Parsec.String
import Text.Printf ( printf )
type Vertex a = a
@scvalex
scvalex / toIpod.sh
Created May 7, 2010 10:22
Convert a movie to iPod mp4
#!/bin/sh
mencoder "$1" -o $1.mp4 -vf scale=480:320,harddup -of lavf -lavfopts format=ipod -alang en -sws 2 -oac faac -faacopts br=128:mpeg=4:object=2:raw -srate 44100 -ovc x264 -x264encopts bitrate=800:nocabac:level_idc=30:bframes=0:global_header:threads=2:subq=5:frameref=6:partitions=all:trellis=1:chroma_me:me=umh
@scvalex
scvalex / youtube-mp3.sh
Created May 7, 2010 10:23
Donwload an mp3 from YouTube
#!/bin/bash
#############
# FUNCTIONS
#############
function h1 {
echo
echo "###################"
echo "## $1"