Skip to main content

Code Katas

Code katas turn problem-solving heuristics into running implementations. Each kata is a small, timed implementation exercise. Repeat until the code flows without reference.

How To Use This Page​

  1. For each kata, begin with a Polya block (understand, plan) in comments before writing code.
  2. Implement from scratch in a language of your choice; do not copy from a reference.
  3. Include a small test harness: one tiny case, one boundary case, one adversarial case.
  4. After finishing, write a one-line transfer note in the comments: "this kata also applies to ..."
  5. Repeat any kata you could not finish in under 20 minutes until you can.

Kata 1: Polya-Driven Equation Solver​

Write a program that reads an equation of the form <expr> = <expr> over a single variable x, and reports either the solution, "no solution", or "infinitely many".

Requirements:

  • comment block at the top showing the Polya understanding phase
  • support at minimum: linear expressions with integer coefficients (3x + 2 = 7 - x)
  • handle edge cases: 0 = 0, 0 = 1, x = x
  • unit tests covering at least 6 cases, including all three answer types

Transfer note prompt: where else does "extract-variable-from-equation" logic appear in systems you have worked with?

Kata 2: Backward-Search Puzzle Solver​

Implement BFS that explores a state graph backward from the goal for this problem: given jug capacities (a, b), starting empty, determine the shortest sequence of pour/empty/fill moves to measure exactly c liters, or report impossible.

Requirements:

  • represent states as (jug1_level, jug2_level)
  • BFS from (any, c) or (c, any) backwards using inverse moves
  • if found, output the forward-written sequence
  • if unreachable, report "impossible" with a one-line reason

Transfer note prompt: what real-world problems have the same "reachable-state graph" shape?

Kata 3: Invariant-Aware Grid Checker​

Given a grid of 0/1 values and a list of moves (flip-row, flip-column, flip-diagonal), determine whether a target grid is reachable from a starting grid under the allowed moves.

Requirements:

  • design and document the invariant your check uses
  • return reachable / unreachable with a one-line explanation
  • include a test case where the naive "search every path" would be infeasible but the invariant gives an instant answer

Transfer note prompt: where does "parity of a configuration" appear in distributed systems or combinatorics?

Kata 4: Special-Cases Property Tester​

Given a function f: int -> int, probe it with n = 1, 2, 3, ... up to a bound, tabulate f(n), and report the strongest pattern hypothesis it is consistent with from this set:

  • constant
  • linear in n
  • polynomial of degree up to 4
  • exponential (e.g., 2^n)
  • Fibonacci-like recurrence
  • no pattern detected

Requirements:

  • implement a difference table and a ratio table
  • return the most parsimonious model consistent with the first N observations
  • include a falsification check: a new n where the model disagrees

Transfer note prompt: how is this kata related to model selection in machine learning?

Kata 5: Recursive Divide-and-Conquer​

Implement mergesort from scratch. Then extend it:

  1. write a linear-time merge step and prove correctness with a loop invariant in comments
  2. implement the merge step iteratively and recursively, and compare stack depth on large inputs
  3. modify mergesort to count the number of inversions during the merge; return (sorted_array, inversion_count) in one pass

Transfer note prompt: inversion counting generalizes to what two-dimensional geometric problems?

Kata 6: Dynamic Programming from Scratch​

Solve the classic edit-distance problem (Levenshtein) with a DP table, then:

  1. reconstruct one optimal edit sequence using backpointer tracking
  2. reduce memory from O(mn) to O(min(m, n))
  3. extend to weighted edits where insertions cost 2 and substitutions cost 3

Requirements:

  • show the recurrence in comments before writing code
  • write a visual printer for the DP table (helpful for debugging)
  • unit tests that include identical strings, completely different strings, and a short string vs a long one

Transfer note prompt: where does edit-distance logic appear in git diff, spellcheckers, or DNA alignment?

Kata 7: Reasoning Debugger​

Implement a tiny proof-checker for arithmetic identities of the form step1; step2; ...; stepK where each step is annotated with a justification "algebra", "IH", "def", or "lemma".

Requirements:

  • given a list of annotated equalities, flag the first unjustified or arithmetically wrong step
  • distinguish syntactic errors from semantic errors
  • include a test case where the answer is correct but the argument has a hole

Transfer note prompt: how does this relate to loop invariants or Coq-style proof assistants (which you will meet later)?

Completion Checklist​

  • Each kata solved from scratch, not copied
  • Polya comments at the top of each file
  • Unit tests covering small, boundary, and adversarial cases
  • Transfer note at the bottom of each file
  • Mistake log updated with any bug that took more than 15 minutes to find

Read This Only If Stuck​