More Tests

More Tests.carbide.md

More Tests

This Gist was automatically created by Carbide, a free online programming environment.

You can view a live, interactive version of this Gist here.

algorithm.js

export function mergeSort(array) {
    let scratch = new Array(array.length);
    _mergeSortImpl(array, 0, array.length-1, scratch);
    return array;
}

function _mergeSortImpl(array, start, end, scratch) {
    if(start >= end) { return; }
    let middle = Math.floor((start + end) / 2);
    _mergeSortImpl(array, start, middle, scratch);
    _mergeSortImpl(array, middle+1, end, scratch);
    _merge(array, start, middle, end, scratch);
}

function _merge(array, start, middle, end, scratch) {
    for(let i = start; i <= end; ++i) {
        scratch[i] = array[i];
    }
    let leftIdx = start;
    let rightIdx = middle + 1;
    let destIdx = start;
    while(leftIdx <= middle && rightIdx <= end) {
        if(scratch[leftIdx] < scratch[rightIdx]) {
            array[destIdx] = scratch[leftIdx];
            ++leftIdx;
        } else {
            array[destIdx] = scratch[rightIdx];
            ++rightIdx;
        }
        ++destIdx;
    }
    while(leftIdx <= middle) {
        array[destIdx] = scratch[leftIdx];
        ++leftIdx;
        ++destIdx;
    }
}

cell0.js

class Graph {
    static Node = class Node {
        constructor(weight, neighbors) {
            this.weight = weight;
            this.neighbors = neighbors;
        }
    }
        
    // nodes is a map from node to a list of neighboring nodes.
	constructor(nodes) { this.nodes = nodes; }
}

class PriorityQueue {
    queue = [];

    static Entry = class Entry {
        constructor(item, priority) {
            this.item = item;
            this.priority = priority;
        }
    }

    insert(item, priority) {
        let i = 0;
        while(this.queue[i] != null && this.queue[i].priority >= priority) {
            ++i;
        }
        this.queue.splice(i, 0, new PriorityQueue.Entry(item, priority));
        return this.queue;
    }

	pop() {
        return this.queue.pop();
    }

	toString() {
        return `[${this.queue.map((x) => `(${x.priority}, ${x.item})`).join(', ')}]`;
    }
}

let queue = new PriorityQueue();
queue.insert('A', 1);
queue.insert('B', 0);
queue.insert('C', 2);
queue.insert('D', 1);
queue.toString();

class PathFinder {
	static walkBack(start, destination, visitedMap) {
        let path = [];
        let current = destination;
        while (current != start) {
            path.push(current);
            current = visitedMap[current];
        }
        path.push(start);
        return path.reverse();
    }
    
    static findPathBreadthFirst(graph, start, destination) {
        let visitedToParent = {};
        let frontier = [start];
        let current;
        while(frontier.length) {
            current = frontier.shift();
            if(current === destination) { break; }
            for(let neighbor of graph.nodes[current].neighbors) {
                if(visitedToParent[neighbor] == null) {
                    frontier.push(neighbor);
                    visitedToParent[neighbor] = current;
                }
            }
        }
        if(current != destination) { 
            return [];
        } else {
            return PathFinder.walkBack(start, destination, visitedToParent);
        }
    }
}

let graph = new Graph({
    'A': new Graph.Node(1, ['B']),
    'B': new Graph.Node(2, ['A', 'C', 'D']),
    'C': new Graph.Node(3, ['A']),
    'D': new Graph.Node(1, ['E', 'A']),
    'E': new Graph.Node(2, ['B'])
});
let path = PathFinder.findPathBreadthFirst(graph, 'A', 'E');

cell1.js

import {mergeSort} from './algorithm.js'

console.log('-- START');

const SIZE = 10;
let array = new Array(SIZE);
for(let i = 0; i < SIZE; ++i) {
    array[i] = Math.floor(Math.random() * 10);
}

array.slice(0)
mergeSort(array);