TypeScript exercises

function greet(name: string): string {
  return `Hello, ${name}`;
}
console.log(greet("Ada"));

type Id = number | string;

function format(id: Id): string {
  if (typeof id === "number") {
    return `#${id.toFixed(0)}`;
  }
  return id.toUpperCase();
}

console.log(format(42));
console.log(format("ab7"));

const Direction = { Up: "UP", Down: "DOWN", Left: "LEFT", Right: "RIGHT" } as const;
type Direction = (typeof Direction)[keyof typeof Direction];

function turnRight(d: Direction): Direction {
  switch (d) {
    case "UP":
      return "RIGHT";
    case "RIGHT":
      return "DOWN";
    case "DOWN":
      return "LEFT";
    case "LEFT":
      return "UP";
    default: {
      const unreachable: never = d;
      return unreachable;
    }
  }
}

let heading: Direction = Direction.Up;
const path: string[] = [heading];
for (let i = 0; i < 4; i++) {
  heading = turnRight(heading);
  path.push(heading);
}
console.log(path.join(" -> "));

const levels = ["debug", "info", "warn", "error"] as const;
type Level = (typeof levels)[number];

function isLevel(text: string): text is Level {
  return (levels as readonly string[]).includes(text);
}

for (const text of ["warn", "verbose"]) {
  console.log(text + ": " + (isLevel(text) ? "valid level" : "not a level"));
}

interface User {
  name: string;
  age: number;
}

function isUser(value: unknown): value is User {
  if (typeof value !== "object" || value === null) {
    return false;
  }
  const record = value as Record<string, unknown>;
  return typeof record.name === "string" && typeof record.age === "number";
}

function describe(json: string): string {
  let parsed: unknown;
  try {
    parsed = JSON.parse(json);
  } catch {
    return "invalid JSON";
  }
  return isUser(parsed) ? parsed.name + " is " + parsed.age : "invalid shape";
}

console.log(describe('{"name":"Ada","age":36}'));
console.log(describe('{"name":"Bo"}'));
console.log(describe("not json"));
console.log(describe("null"));

function minMax(values: readonly number[]): [number, number] {
  return [Math.min(...values), Math.max(...values)];
}

const [low, high] = minMax([4, 9, 2, 7]);
console.log(low, high);

interface Address {
  city?: string;
}
interface Person {
  name: string;
  address?: Address;
  nickname?: string;
  visits: number;
}

const people: Person[] = [
  { name: "Ada", address: { city: "London" }, nickname: "A", visits: 0 },
  { name: "Bo", visits: 3 },
];

for (const person of people) {
  const city = person.address?.city ?? "unknown";
  const label = person.nickname ?? person.name;
  const visits = person.visits || 10;
  const visitsKept = person.visits ?? 10;
  console.log(label + " / " + city + " / " + visits + " / " + visitsKept);
}

interface Student {
  name: string;
  score: number;
  email?: string;
}

function describe(student: Student): string {
  const contact = student.email ?? "no email";
  return `${student.name}: ${student.score} (${contact})`;
}

const ada: Student = { name: "Ada", score: 91 };
const grace: Student = { name: "Grace", score: 88, email: "grace@example.com" };
console.log(describe(ada));
console.log(describe(grace));

interface Describable {
  describe(): string;
}

abstract class Shape implements Describable {
  readonly name: string;
  private static count = 0;

  constructor(name: string) {
    this.name = name;
    Shape.count++;
  }

  abstract area(): number;

  describe(): string {
    return this.name + " with area " + this.area().toFixed(2);
  }

  static total(): number {
    return Shape.count;
  }
}

class Circle extends Shape {
  private radius: number;

  constructor(radius: number) {
    super("circle");
    this.radius = radius;
  }

  area(): number {
    return Math.PI * this.radius ** 2;
  }
}

class Rectangle extends Shape {
  private width: number;
  private height: number;

  constructor(width: number, height: number) {
    super("rectangle");
    this.width = width;
    this.height = height;
  }

  area(): number {
    return this.width * this.height;
  }
}

const shapes: Shape[] = [new Circle(1.5), new Rectangle(2, 3.5)];
for (const shape of shapes) {
  console.log(shape.describe());
}
console.log("shapes created: " + Shape.total());

function first<T>(items: T[]): T | undefined {
  return items[0];
}

const n = first([10, 20, 30]);
const s = first(["a", "b"]);
const none = first<number>([]);
console.log(n, s, none);

class Stack<T> {
  private items: T[] = [];

  push(item: T): void {
    this.items.push(item);
  }

  pop(): T | undefined {
    return this.items.pop();
  }

  peek(): T | undefined {
    return this.items[this.items.length - 1];
  }

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

class Queue<T> {
  private items: T[] = [];
  private head = 0;

  enqueue(item: T): void {
    this.items.push(item);
  }

  dequeue(): T | undefined {
    if (this.head >= this.items.length) {
      return undefined;
    }
    return this.items[this.head++];
  }

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

const history = new Stack<string>();
history.push("home");
history.push("search");
history.push("results");
console.log(history.pop(), history.peek(), history.size);

const jobs = new Queue<number>();
[10, 20, 30].forEach((job) => jobs.enqueue(job));
console.log(jobs.dequeue(), jobs.dequeue(), jobs.size);
console.log(jobs.dequeue(), jobs.dequeue());

type Compare<T> = (a: T, b: T) => number;

interface TreeNode<T> {
  value: T;
  left?: TreeNode<T>;
  right?: TreeNode<T>;
}

class SortedTree<T> {
  private root?: TreeNode<T>;
  private compare: Compare<T>;

  constructor(compare: Compare<T>) {
    this.compare = compare;
  }

  insert(value: T): void {
    const node: TreeNode<T> = { value };
    if (!this.root) {
      this.root = node;
      return;
    }
    let current = this.root;
    for (;;) {
      const order = this.compare(value, current.value);
      if (order === 0) {
        return;
      }
      const side = order < 0 ? "left" : "right";
      const child = current[side];
      if (!child) {
        current[side] = node;
        return;
      }
      current = child;
    }
  }

  has(value: T): boolean {
    let current = this.root;
    while (current) {
      const order = this.compare(value, current.value);
      if (order === 0) {
        return true;
      }
      current = order < 0 ? current.left : current.right;
    }
    return false;
  }

  toArray(): T[] {
    const out: T[] = [];
    const walk = (node?: TreeNode<T>): void => {
      if (!node) return;
      walk(node.left);
      out.push(node.value);
      walk(node.right);
    };
    walk(this.root);
    return out;
  }
}

const numbers = new SortedTree<number>((a, b) => a - b);
[50, 30, 70, 20, 40, 60, 80, 40].forEach((n) => numbers.insert(n));
console.log(numbers.toArray().join(" "));
console.log(numbers.has(60), numbers.has(65));

const byLength = new SortedTree<string>((a, b) => a.length - b.length || a.localeCompare(b));
["pear", "fig", "apple", "kiwi", "fig"].forEach((w) => byLength.insert(w));
console.log(byLength.toArray().join(" "));

interface Employee {
  name: string;
  dept: string;
  salary: number;
}

type Comparator<T> = (a: T, b: T) => number;

function by<T, K extends keyof T>(key: K, direction: "asc" | "desc" = "asc"): Comparator<T> {
  const sign = direction === "asc" ? 1 : -1;
  return (a, b) => (a[key] < b[key] ? -sign : a[key] > b[key] ? sign : 0);
}

function thenBy<T>(...comparators: Comparator<T>[]): Comparator<T> {
  return (a, b) => {
    for (const compare of comparators) {
      const result = compare(a, b);
      if (result !== 0) {
        return result;
      }
    }
    return 0;
  };
}

const staff: Employee[] = [
  { name: "Ada", dept: "Eng", salary: 120 },
  { name: "Bo", dept: "Ops", salary: 90 },
  { name: "Cy", dept: "Eng", salary: 100 },
  { name: "Di", dept: "Ops", salary: 90 },
];

const sorted = [...staff].sort(thenBy<Employee>(by("dept"), by("salary", "desc"), by("name")));
console.log(sorted.map((e) => e.dept + ":" + e.name + ":" + e.salary).join(" "));
console.log(staff.map((e) => e.name).join(" "));

let bodyRuns = 0;

function memoize<T extends string | number, R>(fn: (arg: T) => R): (arg: T) => R {
  const cache = new Map<T, R>();
  return (arg: T): R => {
    if (cache.has(arg)) {
      return cache.get(arg) as R;
    }
    const value = fn(arg);
    cache.set(arg, value);
    return value;
  };
}

const fib: (n: number) => number = memoize((n: number): number => {
  bodyRuns++;
  return n < 2 ? n : fib(n - 1) + fib(n - 2);
});

console.log("fib(25) = " + fib(25) + ", body ran " + bodyRuns + " times");
const before = bodyRuns;
fib(25);
console.log("repeat call: " + (bodyRuns - before) + " more runs");
const mark = bodyRuns;
console.log("fib(30) = " + fib(30) + ", " + (bodyRuns - mark) + " more runs");

type Row = { id: number; name: string; dept: string; salary: number };

const table: Row[] = [
  { id: 1, name: "Ada", dept: "Eng", salary: 120 },
  { id: 2, name: "Bo", dept: "Ops", salary: 90 },
  { id: 3, name: "Cy", dept: "Eng", salary: 100 },
  { id: 4, name: "Di", dept: "Ops", salary: 80 },
];

function where<T>(rows: T[], predicate: (row: T) => boolean): T[] {
  return rows.filter(predicate);
}

function orderBy<T, K extends keyof T>(rows: T[], key: K): T[] {
  return [...rows].sort((a, b) => (a[key] < b[key] ? -1 : a[key] > b[key] ? 1 : 0));
}

function select<T, K extends keyof T>(rows: T[], ...keys: K[]): Pick<T, K>[] {
  return rows.map((row) => {
    const picked = {} as Pick<T, K>;
    for (const key of keys) {
      picked[key] = row[key];
    }
    return picked;
  });
}

const wellPaid = where(table, (row) => row.salary >= 100);
const sorted = orderBy(wellPaid, "name");
console.log(JSON.stringify(select(sorted, "name", "salary")));
console.log(JSON.stringify(select(orderBy(table, "salary"), "name")));

type State = "new" | "ready" | "running" | "waiting" | "terminated";

const transitions: Record<State, State[]> = {
  new: ["ready"],
  ready: ["running"],
  running: ["ready", "waiting", "terminated"],
  waiting: ["ready"],
  terminated: [],
};

function move(from: State, to: State): State {
  if (!transitions[from].includes(to)) {
    throw new Error("illegal transition: " + from + " -> " + to);
  }
  return to;
}

let state: State = "new";
for (const next of ["ready", "running", "waiting", "ready", "running", "terminated"] as State[]) {
  const before = state;
  state = move(state, next);
  console.log(before + " -> " + state);
}

try {
  move("waiting", "running");
} catch (error) {
  console.log((error as Error).message);
}

interface HttpRequest {
  method: string;
  path: string;
  version: string;
  headers: Record<string, string>;
  body: string;
}

function parse(raw: string): HttpRequest {
  const split = raw.indexOf("\r\n\r\n");
  const head = split === -1 ? raw : raw.slice(0, split);
  const body = split === -1 ? "" : raw.slice(split + 4);
  const [requestLine, ...headerLines] = head.split("\r\n");
  const [method, path, version] = requestLine.split(" ");
  const headers: Record<string, string> = {};
  for (const line of headerLines) {
    const colon = line.indexOf(":");
    headers[line.slice(0, colon).trim().toLowerCase()] = line.slice(colon + 1).trim();
  }
  return { method, path, version, headers, body };
}

const raw = "POST /search?q=tcp&page=2 HTTP/1.1\r\nHost: example.com\r\nContent-Length: 5\r\n\r\nhello";
const request = parse(raw);
console.log(request.method + " " + request.path + " " + request.version);
console.log("host: " + request.headers["host"]);
const url = new URL(request.path, "http://" + request.headers["host"]);
console.log("q=" + url.searchParams.get("q") + " page=" + url.searchParams.get("page"));
console.log("body (" + request.headers["content-length"] + " bytes): " + request.body);

type Result<T, E> = { ok: true; value: T } | { ok: false; error: E };

function parseAge(text: string): Result<number, string> {
  const n = Number(text);
  if (text.trim() === "" || Number.isNaN(n)) {
    return { ok: false, error: "not a number" };
  }
  if (!Number.isInteger(n) || n < 0 || n > 150) {
    return { ok: false, error: "out of range" };
  }
  return { ok: true, value: n };
}

for (const input of ["42", "abc", "200", ""]) {
  const result = parseAge(input);
  if (result.ok) {
    console.log("age " + result.value);
  } else {
    console.log("error: " + result.error);
  }
}

type Brand<T, B extends string> = T & { readonly __brand: B };
type Email = Brand<string, "Email">;
type SafeHtml = Brand<string, "SafeHtml">;

function parseEmail(text: string): Email | null {
  return /^[^@\s]+@[^@\s]+\.[^@\s]+$/.test(text) ? (text as Email) : null;
}

function escapeHtml(text: string): SafeHtml {
  const map: Record<string, string> = { "&": "&amp;", "<": "&lt;", ">": "&gt;", '"': "&quot;", "'": "&#39;" };
  return text.replace(/[&<>"']/g, (ch) => map[ch]) as SafeHtml;
}

function sendTo(address: Email): string {
  return "sending to " + address;
}

function paragraph(html: SafeHtml): string {
  return "<p>" + html + "</p>";
}

for (const input of ["ada@example.com", "not-an-email"]) {
  const email = parseEmail(input);
  console.log(email === null ? "rejected: " + input : sendTo(email));
}
console.log(paragraph(escapeHtml("<b>bold</b> & more")));

async function tick(times: number): Promise<void> {
  for (let i = 0; i < times; i++) {
    await null;
  }
}

async function pool<T>(tasks: (() => Promise<T>)[], limit: number): Promise<T[]> {
  const results: T[] = new Array(tasks.length);
  let next = 0;
  async function worker(): Promise<void> {
    while (next < tasks.length) {
      const index = next++;
      results[index] = await tasks[index]();
    }
  }
  await Promise.all(Array.from({ length: limit }, () => worker()));
  return results;
}

let running = 0;
let peak = 0;
const finished: string[] = [];

function task(name: string, ticks: number): () => Promise<string> {
  return async () => {
    running++;
    peak = Math.max(peak, running);
    await tick(ticks);
    running--;
    finished.push(name);
    return name.toUpperCase();
  };
}

const tasks = [task("a", 10), task("b", 1), task("c", 2), task("d", 1)];
pool(tasks, 2).then((results) => {
  console.log("results in input order: " + results.join(","));
  console.log("finished order: " + finished.join(","));
  console.log("peak concurrency: " + peak);
});

function bfs<S>(start: S, isGoal: (s: S) => boolean, next: (s: S) => S[], key: (s: S) => string): S[] | null {
  const queue: S[][] = [[start]];
  const seen = new Set<string>([key(start)]);
  while (queue.length > 0) {
    const path = queue.shift()!;
    const state = path[path.length - 1];
    if (isGoal(state)) {
      return path;
    }
    for (const candidate of next(state)) {
      if (!seen.has(key(candidate))) {
        seen.add(key(candidate));
        queue.push([...path, candidate]);
      }
    }
  }
  return null;
}

type Jugs = [number, number];
const capacity: Jugs = [3, 5];

function moves([a, b]: Jugs): Jugs[] {
  const pourAB = Math.min(a, capacity[1] - b);
  const pourBA = Math.min(b, capacity[0] - a);
  return [
    [capacity[0], b],
    [a, capacity[1]],
    [0, b],
    [a, 0],
    [a - pourAB, b + pourAB],
    [a + pourBA, b - pourBA],
  ];
}

const path = bfs<Jugs>([0, 0], ([a, b]) => a === 4 || b === 4, moves, ([a, b]) => a + "," + b);
console.log(path!.map(([a, b]) => "(" + a + "," + b + ")").join(" "));
console.log("moves: " + (path!.length - 1));

type Expr =
  | { kind: "var"; name: string }
  | { kind: "not"; arg: Expr }
  | { kind: "and"; left: Expr; right: Expr }
  | { kind: "or"; left: Expr; right: Expr }
  | { kind: "implies"; left: Expr; right: Expr };

const v = (name: string): Expr => ({ kind: "var", name });
const implies = (left: Expr, right: Expr): Expr => ({ kind: "implies", left, right });
const and = (left: Expr, right: Expr): Expr => ({ kind: "and", left, right });

function evaluate(e: Expr, env: Record<string, boolean>): boolean {
  switch (e.kind) {
    case "var":
      return env[e.name];
    case "not":
      return !evaluate(e.arg, env);
    case "and":
      return evaluate(e.left, env) && evaluate(e.right, env);
    case "or":
      return evaluate(e.left, env) || evaluate(e.right, env);
    case "implies":
      return !evaluate(e.left, env) || evaluate(e.right, env);
    default: {
      const unreachable: never = e;
      return unreachable;
    }
  }
}

const P = v("P");
const Q = v("Q");
const rule = implies(P, Q);
for (const p of [false, true]) {
  for (const q of [false, true]) {
    console.log("P=" + p + " Q=" + q + ": " + evaluate(rule, { P: p, Q: q }));
  }
}

const modusPonens = implies(and(P, rule), Q);
let tautology = true;
for (const p of [false, true]) {
  for (const q of [false, true]) {
    tautology = tautology && evaluate(modusPonens, { P: p, Q: q });
  }
}
console.log("modus ponens is a tautology: " + tautology);

interface Confusion {
  tp: number;
  fp: number;
  fn: number;
  tn: number;
}

function confusion(actual: number[], predicted: number[]): Confusion {
  const c: Confusion = { tp: 0, fp: 0, fn: 0, tn: 0 };
  for (let i = 0; i < actual.length; i++) {
    if (actual[i] === 1 && predicted[i] === 1) c.tp++;
    else if (actual[i] === 0 && predicted[i] === 1) c.fp++;
    else if (actual[i] === 1 && predicted[i] === 0) c.fn++;
    else c.tn++;
  }
  return c;
}

const actual = [1, 1, 1, 1, 0, 0, 0, 0, 0, 0];
const predicted = [1, 1, 1, 0, 1, 1, 0, 0, 0, 0];
const c = confusion(actual, predicted);

const precision = c.tp / (c.tp + c.fp);
const recall = c.tp / (c.tp + c.fn);
const f1 = (2 * precision * recall) / (precision + recall);
const accuracy = (c.tp + c.tn) / actual.length;

console.log("tp=" + c.tp + " fp=" + c.fp + " fn=" + c.fn + " tn=" + c.tn);
console.log("precision " + precision.toFixed(3) + ", recall " + recall.toFixed(3));
console.log("F1 " + f1.toFixed(3) + ", accuracy " + accuracy.toFixed(3));

interface Layer {
  forward(input: number[]): number[];
}

class Dense implements Layer {
  private weights: number[][];
  private biases: number[];

  constructor(weights: number[][], biases: number[]) {
    this.weights = weights;
    this.biases = biases;
  }

  forward(input: number[]): number[] {
    return this.weights.map((row, j) => row.reduce((sum, w, i) => sum + w * input[i], this.biases[j]));
  }
}

class Sigmoid implements Layer {
  forward(input: number[]): number[] {
    return input.map((z) => 1 / (1 + Math.exp(-z)));
  }
}

class Sequential implements Layer {
  private layers: Layer[];

  constructor(layers: Layer[]) {
    this.layers = layers;
  }

  forward(input: number[]): number[] {
    return this.layers.reduce((value, layer) => layer.forward(value), input);
  }
}

const network = new Sequential([
  new Dense([[20, 20], [20, 20]], [-10, -30]),
  new Sigmoid(),
  new Dense([[20, -20]], [-10]),
  new Sigmoid(),
]);

for (const input of [[0, 0], [0, 1], [1, 0], [1, 1]]) {
  console.log(input[0] + " XOR " + input[1] + " = " + network.forward(input)[0].toFixed(3));
}

class GrayImage {
  readonly width: number;
  readonly height: number;
  private data: Uint8Array;

  constructor(width: number, height: number, data?: Uint8Array) {
    this.width = width;
    this.height = height;
    this.data = data ?? new Uint8Array(width * height);
  }

  static fromRows(rows: number[][]): GrayImage {
    const image = new GrayImage(rows[0].length, rows.length);
    rows.forEach((row, y) => row.forEach((value, x) => image.set(x, y, value)));
    return image;
  }

  get(x: number, y: number): number {
    if (x < 0 || y < 0 || x >= this.width || y >= this.height) {
      throw new RangeError("pixel (" + x + "," + y + ") is outside the image");
    }
    return this.data[y * this.width + x];
  }

  set(x: number, y: number, value: number): void {
    this.get(x, y);
    this.data[y * this.width + x] = value;
  }

  threshold(cutoff: number): GrayImage {
    return new GrayImage(this.width, this.height, this.data.map((v) => (v > cutoff ? 255 : 0)));
  }

  flipHorizontal(): GrayImage {
    const out = new GrayImage(this.width, this.height);
    for (let y = 0; y < this.height; y++) {
      for (let x = 0; x < this.width; x++) {
        out.set(this.width - 1 - x, y, this.get(x, y));
      }
    }
    return out;
  }

  toText(): string {
    const lines: string[] = [];
    for (let y = 0; y < this.height; y++) {
      let line = "";
      for (let x = 0; x < this.width; x++) {
        line += this.get(x, y) > 127 ? "#" : ".";
      }
      lines.push(line);
    }
    return lines.join("\n");
  }
}

const image = GrayImage.fromRows([
  [10, 200, 30, 220],
  [240, 20, 250, 40],
  [60, 180, 70, 190],
]);
console.log(image.threshold(128).toText());
console.log("--");
console.log(image.threshold(128).flipHorizontal().toText());
try {
  image.get(4, 0);
} catch (error) {
  console.log((error as Error).message);
}