2024-02-21

Rites of Passage

I consider some programming projects to be rites of passage: completing any of these projects gives you …

• hands-on experience on a hard problem;
• deep understanding of a branch of computer science;
• the right to boast.

Below are some examples. This list is not intended as a judging tool for a programmer's strength, nor do I think everyone should try these tasks. But I believe they can be fun challenges for those who aim above and beyond.

Foundations

• Programming language
  • Must have a non-trivial syntax using infixes; think Python or Java, not Lisp or Forth.
  • Must be run in some way, whether interpreted, compiled, or transpiled.
  • Must support at least stdin/stdout and file I/O.
  • Must allow user-defined functions.
  • Must be Turing-complete in ideal conditions.
  • Bonus if it supports HTTP requests, GUI, or FFI.
  • Should be reasonably fast: a typical O(n) algorithm should not become O(n²), but O(n log n) is acceptable.
• Visual programming language
  • Similar to: Scratch or Blender nodes.
• Quine
  • Bonus if it's a quine cycle
• Version control
  • Similar to: Git.
• Operating system
• Proof checker / Proof assistant
  • Must be able to verify formal proofs in first-order logic.
  • Milestone: verify formal proofs for the irrationality of √2 and the infinitude of primes

Sciences

• Scientific calculator
  • Infix or postfix (RPN) notation.
  • Bonus if it displays mathematical notation (for example, fractions written vertically).
• Graphing calculator
  • Should support most mainstream graphs: lin-log, log-log, polar, 3D, cylindrical, spherical, contour, scalar/vector fields, parametric equations, and so on.
  • Bonus if it supports showing 2D/3D slices of higher-dimensional objects.
  • Harder than you think!
• Physics engine
  • “Physics” in a general sense. Support for any subset of physics suffices: rigid body, soft body, fluid, optics, electronics, and so on.

Data / Reasoning

• Chess engine
  • May use either traditional or modern approaches.
  • Bonus if made into a bot on a chess platform.
• Neural network
  • Design and train a neural network to solve a non-trivial problem.
• Compression software
  • Any software that can compress and decompress a collection of files using a well-established or original compression algorithm.
• Encoder and decoder
  • For a common image/audio/video format.

User interfaces

• Text editor
  • May be CLI or GUI.
  • Must support undo/redo.
  • Bonus for good accessibility support.
• Hex editor
• Calendar
  • Supports ICS files.
• Map
  • Similar to: Open Street Map.
• Spreadsheet
• GUI toolkit

Auditory / Visual

• Digital audio workstation
• Audio programming language
  • Similar to: SuperCollider
• Music player
• 3D renderer
• Image processing / creation software
  • May support either raster or vector images.
  • Similar to: GIMP (raster), Inkscape (vector).
• Font-rendering engine / Typesetting engine / Mathematical typesetting engine
• Music engraving engine
  • Converts MusicXML to SVG/PDF/PNG.
  • Bonus if you can edit the source, WYSIWYG!

Network

• Web browser
  • Supports a small portion of the Web.
  • Must at least be able to view text-only, JS-free sites.
• Forum / Bulletin board
• Instant messaging

Other

• Game
  • An original, creative, enjoyable, non-trivial game.
  • See also: Ludum Dare
• Generative art
• Time zone converter
  • Converts time (moments) between time zones.
  • May depend on the tz database.
  • Very hard to get correct!