Algorithm Competitions
Two 1st places and one 2nd/3rd place across three timed MSc algorithm competitions
Overview
Three timed algorithm competitions from the MSc Algorithms course at University of Ljubljana. Each required both algorithmic correctness and raw performance under time pressure. The problems span AI search (progressive chess checkmate solver), linear optimization (simplex-based portfolio optimizer), and computational geometry (convex hull line-crossing matcher). Two first-place finishes came from identifying the actual performance bottleneck in each problem rather than reaching for more complex algorithms.
Key Concepts
Progressive Chess Solver (1st Place)
Problem: find a checkmate sequence in progressive chess where turn length increases each turn (1, 2, 3, ...). Key optimizations: (1) g=0 converts A* to greedy best-first — cost-so-far is meaningless when turn length varies, only checkmate existence matters; (2) Zobrist hashing with incremental XOR updates including moves-left counter as state; (3) composable per-piece heuristic calculators (mobility, Manhattan distance, covering, promotion distance) dispatched via Map<Integer, Calculator>; (4) pawn promotion pruning — returns MAX_VALUE when promotion is impossible within remaining moves, eliminating hopeless subtrees; (5) move caching by Zobrist hash to avoid recomputation.
Code Highlights
private static double[] powers = { 1, 10, 100, 1000, 10000, 100000 };
private static double[] powers2 = { 1, 0.1, 0.01, 0.001, 0.0001, 0.00001, 0.000001 };
public double parseDouble() {
var res = 0d;
var pos = start;
for (; pos < end; pos++)
if (data[pos] == '.') break;
for (int i = start; i < end; i++) {
if (i < pos)
res += (data[i] - '0') * powers[pos - i - 1];
else if (i == pos) continue;
else if (i < pos + 5)
res += (data[i] - '0') * powers2[i - pos];
else break;
}
return res;
}Highlights
- 1st place — Progressive Chess: A* converted to greedy best-first (g=0), Zobrist hashing with incremental XOR, composable per-piece heuristic dispatch, pawn promotion pruning
- 1st place — Simplex Portfolio: byte-level CSV parsing replacing BufferedReader + String.split, lookup-table parseDouble, comma-counting column skip, character-level date comparison, Welford's single-pass variance
- 2nd/3rd place — Graham Scan Convex Hull: bounding quadrilateral interior point elimination in O(n) before O(n log n) polar sort, custom unsynchronized Stack (2x over java.util.Stack), soft deletion with partial hull reuse
- Common thread: winning came from identifying the actual bottleneck — not fancier algorithms, but the right optimization at the lever point
Related Projects
PromiseKit
Production Promise library built from algebraic first principles, shipped to ~50K DAU across multiple iOS apps
Designed and built a production Promise library from algebraic first principles -- map derives from flatMap, reduce from fold, operators match Haskell's typeclass precedence hierarchy
fluent-html
Zero-dependency, type-safe HTML builder for TypeScript with compile-time Tailwind CSS and HTMX safety
Designed a mixin architecture using TypeScript declaration merging + prototype assignment that splits a 1,100-line Tag class into focused modules with zero API changes
Redis Server (Zig)
From-scratch Redis-compatible server in Zig with RESP parsing, RDB persistence, and master-replica replication
Implemented a complete Redis-compatible server from scratch in 915 lines of zero-dependency Zig with RESP protocol parser, key-value store with TTL, and RDB binary format codec