Skip to content

Instantly share code, notes, and snippets.

@zpconn
zpconn / kalman.html
Created April 23, 2015 14:43
Simple Kalman-type filter for position tracking
<!DOCTYPE html>
<html>
<head>
<style type="text/css">
html,
body {
margin: 0;
overflow: hidden;
height: 100%;
}
@zpconn
zpconn / reservoir_max.py
Created August 6, 2014 04:01
Any finite list of integers has a maximum element. There may be multiple occurrences of this maximum. This finds uniformly and randomly the index of one of the occurrences of the maximum element with a single pass over the array using reservoir sampling.
import random
def rand_max(arr):
curr_max = 0
curr_max_idx = 0
curr_max_count = 1
for i,x in enumerate(arr):
if x > curr_max:
curr_max = x
curr_max_idx = i
@zpconn
zpconn / README.md
Last active August 29, 2015 14:00
Spherical alpha shapes

This example demonstrates spherical alpha shapes in the orthographic projection. An alpha shape is a generalized concave hull which seeks to characterize the "shape" of a set of points on a surface. It is obtained here by computing the (spherical) Delaunay triangulation (accomplished with the aid of an excellent script from Jason Davies), stripping out triangles that are "too big", and then merging the resulting mesh to remove excess interior geometry that remains from the triangulation.

@zpconn
zpconn / rabin-karp.py
Created January 16, 2014 21:51
A simple implementation of the Rabin-Karp substring search algorithm with a fairly naive running hash function.
class RollingHash:
s = None
start = 0
end = 0
hash = 0
def __init__(self, s, length):
self.s = s
self.end = length - 1
for i in range(length):
@zpconn
zpconn / trie.py
Created January 16, 2014 01:56
A minimal implementation of a trie (or prefix tree) in Python.
def trie(*words):
root = {}
for word in words:
curr_node = root
for letter in word:
curr_node = curr_node.setdefault(letter, {})
curr_node.setdefault(None, None)
return root
def trie_contains(trie, word):
@zpconn
zpconn / inverse_phone.py
Created January 15, 2014 22:08
A solution to the inverse telephone problem in Python (with no imports). Given a mapping like 1 -> A,B,C 2 -> D,E,F etc. and a string of integers like "112", determine all possible images of this string under the mapping ("AAD", "AAE", etc.).
def product(lists):
result = [[]]
for l in lists:
result = [x + [y] for x in result for y in l]
for prod in result:
yield prod
def inverse_phone(mappings, s):
numbers = set([int(n) for n in s])
combinations = product([mappings[n] for n in numbers])
@zpconn
zpconn / tree_weight.py
Created January 14, 2014 04:00
Given a list of triples (a,b,c), where a is the ID of a node in a tree, b is the ID of its parent, and c is the weight of the node, this computes the total weight of every subtree. By convention, the root node has both ID and weight 0.
from collections import defaultdict
def weights(triples):
tree = defaultdict(list)
weights = defaultdict(int)
cache = defaultdict(int)
for t in triples:
weights[t[0]] = t[2]
tree[t[1]].append(t[0])
@zpconn
zpconn / partition.py
Created January 14, 2014 02:33
This solves a simplified version of the partition problem in polynomial time. Namely, given a list, this finds a pair of sublists of equal length whose sums are the same.
def sublists(a, n):
if n == 0:
return [[]]
elif len(a) == 0:
return []
else:
return sublists(a[1:], n) + [[a[0]] + s for s in sublists(a[1:], n - 1)]
def partition(a):
@zpconn
zpconn / mergesort.py
Created January 13, 2014 04:30
This is a very simple implementation of merge sort in Python.
def merge(a1, a2):
res = []
i = 0
j = 0
while i < len(a1) and j < len(a2):
if a1[i] < a2[j]:
res.append(a1[i])
i += 1
else:
res.append(a2[j])
@zpconn
zpconn / quicksort.py
Created January 13, 2014 04:30
This is a very simple recursive implementation of quicksort, mimicking the standard approach in Haskell. It's not particularly efficient, but quite elegant.
def quicksort(a):
if len(a) <= 1:
return a
lesser = [x for x in a[1:] if x < a[0]]
greater = [x for x in a[1:] if x >= a[0]]
return quicksort(lesser) + [a[0]] + quicksort(greater)
print quicksort([4, 6, 5, 3, 4, 7, 6, 5, 8, 9])