Skip to content

Instantly share code, notes, and snippets.

@methodin
methodin / fordFulkerson.js
Created January 4, 2012 20:08
Ford-Fulkerson Max Flow
// Represents an edge from source to sink with capacity
var Edge = function(source, sink, capacity) {
this.source = source;
this.sink = sink;
this.capacity = capacity;
this.reverseEdge = null;
this.flow = 0;
};
// Main class to manage the network
@methodin
methodin / mersenne.js
Created January 3, 2012 06:28
Mersenne Twister
var MersenneTwister = function(seed) {
// Holds the state of the register
this.state = [seed];
this.index = 0;
for(var i=1;i<=623;i++) {
var s = this.state[i-1] ^ (this.state[i-1] >>> 30);
this.state[i] = (((((s & 0xffff0000) >>> 16) * 1812433253) << 16) + (s & 0x0000ffff) * 1812433253) + i;
this.state[i] >>>= 0;
}
@methodin
methodin / mersenne-twister.js
Created January 3, 2012 06:13 — forked from banksean/mersenne-twister.js
a Mersenne Twister implementation in javascript. Makes up for Math.random() not letting you specify a seed value.
/*
I've wrapped Makoto Matsumoto and Takuji Nishimura's code in a namespace
so it's better encapsulated. Now you can have multiple random number generators
and they won't stomp all over eachother's state.
If you want to use this as a substitute for Math.random(), use the random()
method like so:
var m = new MersenneTwister();
@methodin
methodin / djikstra.js
Created January 3, 2012 01:29
Djikstra's Algorithm
function Djikstra(graph, source) {
this.infinity = 1.7976931348623157E+10308;
this.dist = {};
this.previous = {};
this.queue = [];
// Get the smallest distance in the queue
this.findSmallest = function() {
var min = infinity;
var smallest = null;
@methodin
methodin / graph.js
Created January 2, 2012 13:34
Graph
var Graph = function() {
this.nodes = {};
this.edges = {};
this.addNode = function(id, data) {
this.nodes[id] = data;
};
this.getNode = function(id) {
return this.nodes[id] || null;
@methodin
methodin / gale.js
Created December 30, 2011 04:35
Gale-Shipley Algorithm
var men = {
'Joe': ['Mary','Jane','Dorothy','Susan'],
'Tim': ['Jane','Dorothy','Mary','Susan'],
'Jack': ['Dorothy','Jane','Susan','Mary'],
'Matt': ['Mary','Jane','Susan','Dorothy']
};
var women = {
'Mary': ['Tim','Joe','Jack','Matt'],
'Jane': ['Matt','Jack','Joe','Tim'],
@methodin
methodin / astar.js
Created December 29, 2011 17:37
A* Path Finding
String.prototype.replaceAt=function(index, char) {
return this.substr(0, index) + char + this.substr(index+char.length);
};
var Point = function(x,y, parent) {
this.x = x;
this.y = y;
this.cost = 0;
this.moveCost = 0;
this.goalCost = 0;
this.parent = parent === undefined ? null : parent;
@methodin
methodin / sieve.js
Created December 28, 2011 19:41
Sieve of Eratosthenes
function primes(from, to) {
var arr = [];
for(var i=from;i<=to;i++) arr.push(i);
for(var check=0;check<to/2;check++) {
for(var j=check+arr[check]; j<=to,j<=arr.length-1; j+=arr[check]) {
arr.splice(j--,1);
}
}
return arr;
}
@methodin
methodin / fib.js
Created December 28, 2011 16:49
Fibonacci Sequence
function fib(n) {
return n<2 ? n : fib(n-1)+fib(n-2);
}
var n = 16;
var result = fib(n);
@methodin
methodin / hash.js
Created December 28, 2011 15:16
Hash Table
var Hash = function() {
this.tableSize = 16;
this.table = new Array(this.tableSize);
this.convert = function(key) {
var hash = 0;
for (var i=0;i<key.length;i++) hash += key[i].charCodeAt() * (i+1);
return Math.abs(hash) % this.tableSize;
};