Skip to content

Instantly share code, notes, and snippets.

@hillscottc
hillscottc / no_global.js
Created May 1, 2015 01:29
Keep stuff out of global by creating and calling an anon func.
/* Keep stuff out of global by creating and calling an anon func.
*/
(function() {
function square(x) { return x * x; }
var hundred = 100;
console.log(square(hundred));
})();
// → 10000
@hillscottc
hillscottc / TestFloyd.py
Last active August 29, 2015 14:02 — forked from Ceasar/floydwarshall.py
The Floyd-Warshall, All-Pairs Shortest Path algorithm.
import unittest
from floydwarshall import floyd
class TestFloyd(unittest.TestCase):
def test_floyd_1(self):
inf = float('inf')
g = {0: {0: 0, 1: 1, 2: 4},
1: {0: inf, 1: 0, 2: 2},
@hillscottc
hillscottc / getUsedItems.py
Created June 1, 2014 16:09
0-1 Knapsack Problem
# w = list of item weight or cost
# c = the cost matrix created by the dynamic programming solution
def getUsedItems(w,c):
# item count
i = len(c)-1
currentW = len(c[0])-1
# set everything to not marked
marked = []
for i in range(i+1):
marked.append(0)
@hillscottc
hillscottc / fabfile_db.py
Created June 1, 2014 06:01
Sample Fabric file to rebuild db.
from __future__ import with_statement
import os
from fabric.api import local, settings, abort, sudo, env
from fabric.contrib.console import confirm
env.hosts = [
# 'me@my-imac',
'me@my-desk',
]
@hillscottc
hillscottc / lcs.py
Created June 1, 2014 04:43 — forked from istepanov/lcs.py
Longest common substrings using generalized suffix trees built with Ukkonen's algorithm.
#!/usr/bin/env python
# -*- coding: utf-8
"""
Search longest common substrings using generalized suffix trees built with Ukkonen's algorithm
Author: Ilya Stepanov <code at ilyastepanov.com>
(c) 2013
"""
@hillscottc
hillscottc / suffix_tree.py
Created June 1, 2014 04:32
A Simple Suffix Tree Implementation in Python.
"""http://goo-apple.appspot.com/article/2e8d3c6a-2c38-48b9-96c6-240b4ded253a"""
class Node:
def __init__(self, start, substr):
self.start = start
self.substr = substr
self.branches = {}
def insert_into_tree(subroot, suffix, start):
prefix_len = len(subroot.substr)
new_suffix = str(suffix[prefix_len:])
@hillscottc
hillscottc / long_substr.py
Created June 1, 2014 03:51
Longest Common Substring, Dynamic
"""http://stackoverflow.com/questions/2892931/longest-common-substring-from-more-than-two-strings-python"""
def long_substr(data):
"""Finds the longest common string in any arbitrary array of strings"""
substr = ''
if len(data) > 1 and len(data[0]) > 0:
for i in range(len(data[0])):
for j in range(len(data[0])-i+1):
if j > len(substr) and all(data[0][i:i+j] in x for x in data):
substr = data[0][i:i+j]
@hillscottc
hillscottc / coin_change.py
Last active August 29, 2015 14:02
Coin change problem, dynamic.
def make_change(cents_needed, coin_vals):
min_coins = [[0 for j in range(cents_needed + 1)]
for i in range(len(coin_vals))]
min_coins[0] = range(cents_needed + 1)
for i in range(1, len(coin_vals)):
for j in range(0, cents_needed + 1):
if j < coin_vals[i]:
min_coins[i][j] = min_coins[i-1][j]
import sys
def knapsack(items, maxweight):
# Create an (N+1) by (W+1) 2-d list to contain the running values
# which are to be filled by the dynamic programming routine.
#
# There are N+1 rows because we need to account for the possibility
# of choosing from 0 up to and including N possible items.
# There are W+1 columns because we need to account for possible
# "running capacities" from 0 up to and including the maximum weight W.
@hillscottc
hillscottc / dijkstra.py
Last active August 29, 2015 14:02
Dijkstras Algorithm for shortest path.
"""
Dijkstra's algorithm for shortest paths.
http://code.activestate.com/recipes/577343-dijkstras-algorithm-for-shortest-paths/)
- dijkstra(G, s) finds all shortest paths from s to each other vertex.
- shortest_path(G, s, t) uses dijkstra to find the shortest path from s to t.
The input graph G is assumed to have the following representation:
- A vertex can be any object that can be used as an index into a dictionary.