TypeDrop

2026-09-09 Challenge

2026-09-09 Hard

Typed Graph Traversal Engine with Shortest-Path & Cycle Detection

You're building the dependency-resolution core for a monorepo build system. Packages form a directed graph of dependencies; the engine must detect circular dependencies (which would deadlock a build), compute the shortest build path between two packages, and produce a topologically sorted build order — all with the compiler enforcing every graph shape, traversal result, and error variant.

Goals

Implement `buildGraph`, `detectCycles`, `shortestPath`, and `topologicalSort` so all five test assertions pass.
Model every failure mode using the `GraphError` discriminated union and the generic `Result<T,E>` type — no thrown exceptions from public functions.
Implement `queryGraph` with a generic `K extends keyof GraphQueryMap` constraint so callers get the precise return type inferred from the operation literal, with zero casts.
Create a type-safe `pkgId` branded-ID factory that brands a plain string as `PackageId` without using `as` or any type assertion.

          
          challenge.ts

// Key types and main function signatures at a glance

export type PackageId = string & { readonly __brand: "PackageId" };

export type GraphError =
  | { readonly kind: "unknown_node";   readonly ids: ReadonlyArray<PackageId> }
  | { readonly kind: "cycle_detected"; readonly cycle: ReadonlyArray<PackageId> }
  | { readonly kind: "no_path";        readonly from: PackageId; readonly to: PackageId };

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

export interface GraphQueryMap {
  cycles:   CycleCheckResult;
  topoSort: Result<TopologicalOrderResult, GraphError>;
}

export function buildGraph(nodes: ReadonlyArray<PackageNode>, edges: ReadonlyArray<DependencyEdge>): DependencyGraph;
export function detectCycles(graph: DependencyGraph): CycleCheckResult;
export function shortestPath(graph: DependencyGraph, from: PackageId, to: PackageId): Result<ShortestPathResult, GraphError>;
export function topologicalSort(graph: DependencyGraph): Result<TopologicalOrderResult, GraphError>;
export function queryGraph<K extends keyof GraphQueryMap>(graph: DependencyGraph, operation: K): GraphQueryMap[K];
export function pkgId(raw: string): PackageId;

Hints (click to reveal)

Hints

For `pkgId` without `as`: a single-line identity function whose return type is explicitly annotated as `PackageId` is the idiomatic branded-type factory — the annotation alone is not an assertion.
Dijkstra needs a min-priority queue; a simple array sorted by cost works for small graphs — focus on getting the types right first, then optimise.
In `queryGraph`, the compiler can't automatically verify that your `if/else` branches return `GraphQueryMap[K]` — a lookup object `{ cycles: detectCycles, topoSort: topologicalSort }` indexed by `operation` is one clean escape hatch that avoids casts.

Useful resources

StackBlitz

CodeSandbox

Or clone locally

git clone -b challenge/2026-09-09 https://github.com/niltonheck/typedrop.git