#algorithms
23 posts
Morse code: one table, two ambiguities, three details
Morse itself is trivial; the trouble is in the details — who owns the space, how to normalise full-width dots, and how long one unit actually is.
An opponent that predicts the bounce, but not too well
A Pong opponent worth playing needs two things: an accurate prediction of where the ball lands, and a deliberate error. The first is one triangle wave; the second is redrawn on every return.
Misusing big O: constants and preconditions decide more than the order
An O(n log n) sort can lose to O(n²) insertion sort, and an O(1) hash lookup can lose to an array scan. Check input size, constants and memory locality before judging speed.
git bisect: turn which commit broke it into one command
The hard part of regression hunting is not the binary search, it is defining what counts as broken. Write a script that answers that, and bisect compresses n builds into log n.
Gomoku AI: splitting threat detection from search
Plain alpha-beta misses forced wins in gomoku. I split the decision into three layers — win, block, forced-win patterns — and only then hand the rest to iterative deepening.
Memory layout: the same algorithm, ten times slower, is usually cache
A trip to main memory costs hundreds of cycles; a cache line fetch costs one. Sequential versus random access often outweighs the algorithmic order itself.
Deadlock: break any one of four conditions
Mutual exclusion, hold and wait, no preemption, circular wait. All four must hold at once. The practical one to break is circular wait: give every lock a global order.
Catastrophic backtracking: why a regex can pin a CPU
Nested quantifiers make the number of match attempts grow exponentially; (a+)+b can hang a process on one long non-matching input. Drop the nesting or put a timeout on it.
SQLite indexes: the leftmost prefix is a consequence of sorting
A composite index (a, b) can only order by b within equal a, so skipping a and filtering on b has nothing to use. See it as sorting and the mnemonic stops being a rule to memorize.
Time zones and DST: store UTC, or daylight saving will bite
A DST day has 23 or 25 hours, and local times near the switch may not exist or may happen twice. Storing UTC timestamps and converting at display is the only model that holds.
Four places Chinese chess rules go wrong
Horse-leg blocking, elephant-eye blocking, cannon screens and the flying-general rule. Splitting move generation into a geometry layer and a legality layer removes most of the mistakes.
Writing a cron parser: five fields, the union rule, and February 30th
The syntax takes half an hour. The semantics are the work: day-of-month and day-of-week unite rather than intersect, impossible dates need a stopping condition, and 7 and 0 are both Sunday.
CSV is not split on commas: quoting and newlines from RFC 4180
The moment a field is quoted, split stops working: quotes hold delimiters and newlines, and a quote inside a field is doubled. A thirty-line state machine beats any regex.
Legal moves in Reversi: eight directions, one scan
A square is legal if at least one of eight directions can sandwich the opponent. Testing and flipping share a single scan, so there is no simulated move to roll back.
A sudoku generator: digging holes, unique solutions, and the bug that froze the page
Generate a full solution, then dig cells out while checking uniqueness. I let zero mean unlimited in the solver, so an empty grid enumerated every solution and the new-game button hung.
Consistent hashing: why adding a machine does not reshuffle every key
Modulo sharding moves almost all data when the machine count changes. Put the hash space on a ring and let each key follow it clockwise to the first node, and only one arc moves. Virtual nodes are the price.
Winning at Gomoku: checking the last stone is enough
Rescanning the whole board after every move is waste. Only the newest stone can create a line, so four directions from that point settle it in constant time.
Sliding windows: decide what the window tracks before writing the loop
A window works when validity changes monotonically with its edges. Write down the tracked state and the shrink condition first, and the two-pointer loop amortises to O(n) on its own.
Monotonic stacks: next greater element in O(n), not O(n squared)
Each index is pushed and popped at most once, so what looks like a nested loop is linear. Recognise the first larger or smaller neighbour shape and the same template applies.
Counting the ones in a binary number: from loops to SWAR
Popcount has three forms: loop once per set bit, a lookup table, or SWAR across bit fields. They differ by orders of magnitude, and Rust and WebAssembly already expose it as a single instruction.
Union-find: two lines of optimisation make every operation near constant
Path compression flattens the tree, union by size stops it growing tall. You need both before the cost drops to the inverse Ackermann function, which is never above 5 in practice.
2048: collapsing four directions into one operation
Sliding, merging and scoring only need to be written once; the other three directions reuse it through transpose and reverse. The hard part is that each tile may merge at most once per move.
Minesweeper: deferring mine placement until the first click
A minesweeper where the first click can lose is an unfinished minesweeper. Deferring placement and excluding the surrounding 3 by 3 is the single most important design decision here.