BellmanFord.js

var V = ["A", "B", "C"]
var E = [
	["A", "B", 3],
	["A", "C", 10],
	["B", "C", 5],
	["C", "A", -8]
]

BF(V, E, "A")

function createGraph(V, start) {
	var G = {}
	V.forEach(function(v){
		G[v] = Node(v)
		if (v === start) {
			G[v].distance = 0
		}
	})
	return G
}

function Node(v) {
	return {
		val: v,
		parent: null,
		distance: Infinity
	}
}

function relax(G, E) {
	var s = E[0]
	var u = E[1]
	var w = E[2]

	var S = G[s]
	var U = G[u]
	if (U.distance > S.distance + w) {
		U.distance = S.distance + w
		U.parent = S.val
	}
}


function BF(V, E, start) {
	var G = createGraph(V, start)
	for(var i = 1; i < V.length; i++) {
		for (var j = 0; j < E.length; j++) {
			relax(G, E[j])
		}
	}
	for (var j = 0; j < E.length; j++) {
		var node = G[E[j][1]]
		var distance = node.distance
		relax(G, E[j])
		if (node.distance < distance) {
			node.distance = -Infinity
		}
	}
	return G
}

binheap.js

var heap = []

for (var i = 0; i < 10; i++) {
	insert(heap, i)
	console.log(heap)
}
for (var i = 0; i < 10; i++) {
	del(heap)
	console.log(heap)
}

function insert(heap, value) {
	heap.push(value)
	var idx = heap.length - 1
	var unsorted = true
	while(idx !== 0 && unsorted) {
		// var [parent, pIdx] = getParent(heap, idx)
		var parent = getParent(heap, idx)
		var pIdx = parent[0]
		parent = parent[1]
		if (value < parent) {
			unsorted = false
		} else {
			heap = swap(heap, idx, pIdx)
			idx = pIdx
		}
	}
	return heap
}
function del(heap) {
	var idx = 0
	var end = heap.length - 1
	var value = heap[end]
	var unsorted = true
	heap.pop()
	end--
	heap[0] = value
	while (unsorted && idx < end) {
		//var [left, lIdx, right, rIdx] = getChildren
		var children = getChildren(heap, idx)
		var left = children[0]
		var right = children[1]
		var lIdx = left[0]
		left = left[1]
		var rIdx = right[0]
		right = right[1]
		if (left && value < left && (!right || left > right)) {
			swap(heap, idx, lIdx)
			idx = lIdx
		} else if (right && value < right && right > left) {
			swap(heap, idx, rIdx)
			idx = rIdx
		} else {
			unsorted = false
		}
	}
	return heap
}

function swap(arr, a, b) {
	var temp = arr[a]
	arr[a] = arr[b]
	arr[b] = temp
	return arr
}


function getParent(heap, idx) {
	var pIdx
	if (idx <= 2 || idx === 0 ) {
		pIdx = 0
	} else {
		pIdx = Math.floor((idx-1)/2)
	}
	return [pIdx, heap[pIdx]]
}

function getChildren(heap, idx) {
	var lIdx = 2*idx + 1
	var rIdx = 2*idx + 2
	var lChild = heap[lIdx]
	var rChild = heap[rIdx]
	return [[lIdx, lChild],[rIdx, rChild]]
}

NaiveQTree.js

var M = [
    [0,1,2],
    [3,4,5],
    [6,7,8]
    //[6,7]
]

function QT(M, rs, re, cs, ce) {
    if (rs >= re || cs >= ce) {
        return null
    }
    if (rs + 1 == re && cs + 1 == ce) {
        return M[rs][cs]
    }
    var node = createNode({coords: [rs, re, cs, ce]})
    var H = Math.floor((re - rs)/2) + rs
    var V = Math.floor((ce - cs)/2) + cs
    var TL = QT(M, rs, H, cs, V)
    var TR = QT(M, rs, H, V, ce)
    var BL = QT(M, H, re, cs, V)
    var BR = QT(M, H, re, V, ce)
    node.children.push(TL, TR, BL, BR)
    return node
}

function createNode(box) {
    return {
        val: box,
        children: []
    }

}

function DFS(N, cb) {
    if (N === null) {
        return null
    }
    if (!N.children) {
        return cb(N)
    }
    //cb(N)
    N.children.forEach(function (child) {
        // doesn't do anything. but this is where such a search would work
        if (contains(child, S)) {
            DFS(child, cb)
        }
    })
}

var T = QT(M, 0, M.length, 0, M[0].length)

function print (x) {
    console.log(x)
}

DFS(T, print)

prefixOffByOne.js

function offByOne(A, B, i, j, diff) {
    i = i || 0
    j = j || 0
    diff = diff || 0
    if (i > A.length -1) {
        return diff < 2
    }
    if (j > B.length - 1) {
        return diff + i - j < 2
    }
    if (A[i] === B[i]) {
        return offByOne(A, B, i+1, j+1, diff)
    }
    diff += 1
    // check if A had a char deleted
    var deleted = offByOne(A, B, i, j+1, diff)
    if (deleted) {
        return true
    }
    var inserted = offByOne(A, B, i+1, j, diff)
    if (inserted) {
        return true
    }
    var mutated = offByOne(A, B, i+1, j+1, diff)
    if (mutated) {
        return true
    }
    
    return false
}

UberShortestPath.js

function nightRoute(city) {
    var G = convertToNodes(city)
    var start = G[0]
    var end = G[city.length-1]
    
    var Q = new PQ()
    Q.insert(start)
    start.queued = true
    start.distance = 0
    
    while (Q.peek()) {
        var node = Q.top()
        node.visited = true
        for (var i = 0; i < node.children.length; i++) {
            var child = node.children[i]
            var weight = city[node.val][child.val]
            if (relax(child, node, weight)) {
                if (child.queued) {
                    Q.update()
                }
                if (!child.queued && !child.visited) {
                    Q.insert(child)
                    child.queued = true
                }
            }
        }
    }
    return end.distance
}

function convertToNodes(M) {
    var G = {}
    for (var i = 0; i < M.length; i++) {
        if (!G[i]) {
            G[i] = Node(i)
        }
        var node = G[i]
        for (var j = 0; j < M[0].length; j++) {
            if (i == j) {
                continue
            }
            if (M[i][j] >= 0) {
                if (!G[j]) {
                    G[j] = Node(j)
                }
                var child = G[j]
                node.children.push(child)
            }
        }
    }
    return G
}

function Node(val) {
    return {
        queued: false,
        visited: false,
        val: val,
        distance: Infinity,
        children: []
    }
}

function relax (child, parent, weight) {
    if (child.distance < parent.distance + weight) {
        return false
    }
    child.distance = parent.distance + weight
    return true
}


/// SHITTY QUICK AND DIRTY PQ
function PQ() {
    this.store = []
}

PQ.prototype.peek = function () {
    return this.store.length > 0
}

PQ.prototype.top = function () {
    return this.store.shift()
}

PQ.prototype.insert = function(node) {
    this.store.push(node)
    this.store.sort(compareNodes)    
}

PQ.prototype.update = function() {
    this.store.sort(compareNodes)
}

PQ.prototype.delete = function (node) {
    idx = this.store.indexOf(node)
    var last = this.store.length - 1
    swap(this.store, idx, last)
    this.store.pop()
    if (this.store.length > 1) {
        this.store.sort(compareNodes)
    }
}

function compareNodes(A, B) {
    if (A.distance <= B.distance) {
        return -1
    } else {
        return 1
    }
}

function swap(A, i, j) {
    var temp = A[i]
    A[i] = A[j]
    A[j] = temp
}