Skip to content

Instantly share code, notes, and snippets.

Avatar

André Lima andlima

  • Rio de Janeiro, Brazil
View GitHub Profile
View Expectation–maximization algorithm.ipynb
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
@andlima
andlima / mersenne_twister.rs
Last active Aug 29, 2015
Mersenne Twister 19937 PRNG
View mersenne_twister.rs
fn initialize_generator(mt: &mut [uint], index: &mut uint, seed: uint)
{
mt[0] = seed;
*index = 0;
for i in range(1, 624) {
mt[i] = (
(
1812433253 * (mt[i-1] ^ (mt[i-1] >> 30))
) + i
View trie.py
from __future__ import print_function
class Trie(object):
'''Implementation of a trie.'''
def __init__(self, collection=None):
self.ends = False
self.children = {}
if collection is not None:
@andlima
andlima / problem_c.py
Last active Dec 16, 2015
Google Code Jam 2013 - Qualification Round - Problem C
View problem_c.py
from bisect import bisect_left, bisect_right
def solve(numbers, a, b):
answer = bisect_right(numbers, b) - bisect_left(numbers, a)
return answer if answer > 0 else 0
def main():
numbers = [1, 4, 9]
previous = ('012', [''])
View gist:2872210
def distance(points, i, j):
x1, y1 = points[i]
x2, y2 = points[j]
return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5
def find_root(height_and_parent, i):
hi, pi = height_and_parent[i]
if pi is None:
return i
return find_root(height_and_parent, pi)
@andlima
andlima / p2.py
Created May 27, 2012
Solução do P2 - 2016
View p2.py
def distance(points, i, j):
x1, y1 = points[i]
x2, y2 = points[j]
return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5
def merge_root(root, i, j):
good, bad = sorted([root[i], root[j]])
bad_keys = [k for k, v in root.iteritems() if v == bad]
for key in bad_keys:
root[key] = good
@andlima
andlima / scrape_letras_terra.py
Created Apr 7, 2012
Scrape letras.terra.com.br
View scrape_letras_terra.py
"""
A short script that, given an artist, scrapes all his/her/their songs
from 'http://letras.terra.com.br'
Dependence: BeautifulSoup, to parse the lyrics from each song page.
Author: Andre Lima - http://github.com/andlima
Licensed under MIT License
@andlima
andlima / gist:1776496
Created Feb 9, 2012
Quick selection algorithm
View gist:1776496
int quick_find_kth(int *v, int n, int k) {
if (n == 1 && k == 0) return v[0];
int pivot = v[n-1];
int store = 0;
for (int i=0; i<n-1; i++) {
if (v[i] < pivot) {
swap(v[i], v[store++]);
}
@andlima
andlima / gist:1774060
Created Feb 8, 2012
Median of medians selection algorithm
View gist:1774060
int find_kth(int *v, int n, int k) {
if (n == 1 && k == 0) return v[0];
int m = (n + 4)/5;
int *medians = new int[m];
for (int i=0; i<m; i++) {
if (5*i + 4 < n) {
int *w = v + 5*i;
for (int j0=0; j0<3; j0++) {
int jmin = j0;