DSA, typed

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72class Heap<T> {
  #items: T[] = [];
  #compare: (a: T, b: T) => number;

  constructor(compare: (a: T, b: T) => number) {
    this.#compare = compare;
  }

  get size(): number {
    return this.#items.length;
  }

  peek(): T | undefined {
    return this.#items[0];
  }

  push(value: T): void {
    this.#items.push(value);
    let i = this.#items.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      // The ! is honest: the loop bounds prove both indices exist, and the
      // compiler cannot see that. Explained below.
      if (this.#compare(this.#items[parent]!, this.#items[i]!) <= 0) break;
      [this.#items[parent], this.#items[i]] = [this.#items[i]!, this.#items[parent]!];
      i = parent;
    }
  }

  pop(): T | undefined {
    if (this.#items.length === 0) return undefined;
    const top = this.#items[0]!;
    const last = this.#items.pop()!;

    if (this.#items.length > 0) {
      this.#items[0] = last;
      let i = 0;
      for (;;) {
        const left = 2 * i + 1;
        const right = left + 1;
        let best = i;
        if (left < this.#items.length && this.#compare(this.#items[left]!, this.#items[best]!) < 0) best = left;
        if (right < this.#items.length && this.#compare(this.#items[right]!, this.#items[best]!) < 0) best = right;
        if (best === i) break;
        [this.#items[best], this.#items[i]] = [this.#items[i]!, this.#items[best]!];
        i = best;
      }
    }
    return top;
  }
}

// Numbers.
const numbers = new Heap<number>((a, b) => a - b);
for (const n of [5, 1, 4, 1, 9, 2]) numbers.push(n);
const drained: number[] = [];
while (numbers.size > 0) drained.push(numbers.pop()!);
console.log('sorted:', drained);

// Objects, with the comparator tied to the contents.
interface Task {
  name: string;
  priority: number;
}

const tasks = new Heap<Task>((a, b) => a.priority - b.priority);
tasks.push({ name: 'deploy', priority: 3 });
tasks.push({ name: 'fix build', priority: 1 });
tasks.push({ name: 'review', priority: 2 });

console.log('most urgent:', tasks.peek()?.name);
console.log('drain order:', [tasks.pop()?.name, tasks.pop()?.name, tasks.pop()?.name]);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68interface TreeNode {
  value: number;
  left: TreeNode | null;
  right: TreeNode | null;
}

const leaf = (value: number): TreeNode => ({ value, left: null, right: null });

// Every one of these needs its null check to compile. That is the whole
// difference from the JavaScript version.
function depth(node: TreeNode | null): number {
  if (node === null) return 0;
  return 1 + Math.max(depth(node.left), depth(node.right));
}

function sum(node: TreeNode | null): number {
  if (node === null) return 0;
  return node.value + sum(node.left) + sum(node.right);
}

function inorder(node: TreeNode | null, out: number[] = []): number[] {
  if (node === null) return out;
  inorder(node.left, out);
  out.push(node.value);
  inorder(node.right, out);
  return out;
}

// The post-order shape: return one value upward, accumulate another outside.
function diameter(root: TreeNode | null): number {
  let best = 0;

  function height(node: TreeNode | null): number {
    if (node === null) return 0;
    const left = height(node.left);
    const right = height(node.right);
    best = Math.max(best, left + right);
    return 1 + Math.max(left, right);
  }

  height(root);
  return best;
}

// Validity needs a range threaded downward, not a local comparison.
function isValidBst(node: TreeNode | null, low = -Infinity, high = Infinity): boolean {
  if (node === null) return true;
  if (node.value <= low || node.value >= high) return false;
  return isValidBst(node.left, low, node.value) && isValidBst(node.right, node.value, high);
}

//        4
//       / \
//      2   6
//     /
//    1
const tree: TreeNode = {
  value: 4,
  left: { value: 2, left: leaf(1), right: null },
  right: leaf(6),
};

console.log('depth:    ', depth(tree));
console.log('sum:      ', sum(tree));
console.log('inorder:  ', inorder(tree));
console.log('diameter: ', diameter(tree));
console.log('valid BST:', isValidBst(tree));
console.log('empty:    ', depth(null), sum(null), inorder(null), isValidBst(null));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61class UnionFind {
  #parent: number[];
  #size: number[];
  #groups: number;

  constructor(n: number) {
    this.#parent = Array.from({ length: n }, (_, i) => i);
    this.#size = new Array<number>(n).fill(1);
    this.#groups = n;
  }

  get groups(): number {
    return this.#groups;
  }

  find(x: number): number {
    while (this.#parent[x] !== x) {
      // Path compression. The ! assertions are the price of
      // noUncheckedIndexedAccess on an array we know is fully populated.
      this.#parent[x] = this.#parent[this.#parent[x]!]!;
      x = this.#parent[x]!;
    }
    return x;
  }

  // Returns false when they were already connected, which is a cycle.
  union(a: number, b: number): boolean {
    let rootA = this.find(a);
    let rootB = this.find(b);
    if (rootA === rootB) return false;

    if (this.#size[rootA]! < this.#size[rootB]!) [rootA, rootB] = [rootB, rootA];
    this.#parent[rootB] = rootA;
    this.#size[rootA] = this.#size[rootA]! + this.#size[rootB]!;
    this.#groups--;
    return true;
  }

  connected(a: number, b: number): boolean {
    return this.find(a) === this.find(b);
  }
}

const uf = new UnionFind(6);
uf.union(0, 1);
uf.union(1, 2);
uf.union(4, 5);

console.log('0 and 2 connected:', uf.connected(0, 2));
console.log('0 and 4 connected:', uf.connected(0, 4));
console.log('components:       ', uf.groups);
console.log('re-union is a no-op:', uf.union(0, 2));

function hasCycle(n: number, edges: readonly (readonly [number, number])[]): boolean {
  const find = new UnionFind(n);
  for (const [a, b] of edges) if (!find.union(a, b)) return true;
  return false;
}

console.log('triangle has a cycle:', hasCycle(3, [[0, 1], [1, 2], [2, 0]]));
console.log('path does not:      ', hasCycle(3, [[0, 1], [1, 2]]));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58// Form 1: exact match.
function search(values: readonly number[], target: number): number {
  let lo = 0;
  let hi = values.length - 1;
  while (lo <= hi) {
    const mid = lo + ((hi - lo) >> 1);
    const value = values[mid]!;
    if (value === target) return mid;
    if (value < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

// Form 2: leftmost position where the predicate becomes true.
function lowerBound(values: readonly number[], target: number): number {
  let lo = 0;
  let hi = values.length;
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (values[mid]! < target) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

// Form 3: search the answer, not the input. The predicate type is the
// interesting part — it documents the monotonicity requirement.
function firstFeasible(lo: number, hi: number, feasible: (candidate: number) => boolean): number {
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (feasible(mid)) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

function shipWithinDays(weights: readonly number[], days: number): number {
  const enough = (capacity: number): boolean => {
    let used = 1;
    let load = 0;
    for (const w of weights) {
      if (load + w > capacity) {
        used++;
        load = 0;
      }
      load += w;
    }
    return used <= days;
  };

  return firstFeasible(Math.max(...weights), weights.reduce((a, b) => a + b, 0), enough);
}

console.log('search 9:      ', search([-1, 0, 3, 5, 9, 12], 9));
console.log('search 2:      ', search([-1, 0, 3, 5, 9, 12], 2));
console.log('lowerBound 2:  ', lowerBound([1, 2, 2, 2, 3], 2));
console.log('ship in 5 days:', shipWithinDays([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42type Graph = ReadonlyMap<string, readonly string[]>;

function buildGraph(edges: readonly (readonly [string, string])[]): Graph {
  const adjacency = new Map<string, string[]>();
  const add = (from: string, to: string): void => {
    const list = adjacency.get(from);
    if (list === undefined) adjacency.set(from, [to]);
    else list.push(to);
  };

  for (const [a, b] of edges) {
    add(a, b);
    add(b, a);
  }
  return adjacency;
}

// The return type says what you get: a distance for every reachable node.
function bfs(graph: Graph, start: string): Map<string, number> {
  const distance = new Map<string, number>([[start, 0]]);
  const queue: string[] = [start];

  // A head index, not shift(), which would make this quadratic.
  for (let head = 0; head < queue.length; head++) {
    const node = queue[head]!;
    const here = distance.get(node)!;

    for (const next of graph.get(node) ?? []) {
      if (distance.has(next)) continue;
      distance.set(next, here + 1);
      queue.push(next);
    }
  }
  return distance;
}

const graph = buildGraph([['a', 'b'], ['a', 'c'], ['b', 'd'], ['c', 'd'], ['d', 'e']]);
const distances = bfs(graph, 'a');

console.log('distances:', [...distances.entries()]);
console.log('to e:     ', distances.get('e'));
console.log('unreached:', distances.get('z') ?? 'not reachable');

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22type Result<T, E = string> =
  | { ok: true; value: T }
  | { ok: false; error: E };

// The JavaScript version returned -1, or null, or NaN, and every caller had to
// remember which. This one cannot be misread.
function parsePositiveInt(input: string): Result<number> {
  const n = Number(input);
  if (Number.isNaN(n)) return { ok: false, error: `not a number: "${input}"` };
  if (!Number.isInteger(n)) return { ok: false, error: 'must be a whole number' };
  if (n <= 0) return { ok: false, error: 'must be positive' };
  return { ok: true, value: n };
}

for (const input of ['42', 'abc', '3.5', '-1', '0']) {
  const parsed = parsePositiveInt(input);
  // The compiler will not let you touch .value without checking .ok.
  console.log(
    input.padEnd(5),
    parsed.ok ? `-> ${parsed.value}` : `-> failed: ${parsed.error}`,
  );
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29// Both of these are correctly typed. One is O(n), the other O(n squared).
// The compiler has no opinion whatsoever about which you should ship.

function sumFast(values: readonly number[]): number {
  let total = 0;
  for (const value of values) total += value;
  return total;
}

function sumSlow(values: readonly number[]): number {
  let total = 0;
  for (let i = 0; i < values.length; i++) {
    // Recomputing a prefix on every iteration. Perfectly type-safe, and wrong.
    total = values.slice(0, i + 1).reduce((a, b) => a + b, 0);
  }
  return total;
}

const data = Array.from({ length: 400 }, (_, i) => i);
console.log('same answer:', sumFast(data) === sumSlow(data));

let fastSteps = 0;
let slowSteps = 0;
for (const value of data) { fastSteps++; void value; }
for (let i = 0; i < data.length; i++) slowSteps += i + 1;

console.log('fast steps:', fastSteps);
console.log('slow steps:', slowSteps);
console.log('The type checker cannot tell you which of these to ship.');