This project aims to capture my notes for studying various programming problems (data structures and algorithms). Have a look at the problems in Section <a href=”* Problems”>* Problems.
For those curious about how these notes were created, check out Section <a href=”* Literate Programming Build System”>* Literate Programming Build System.
As for why this project is named Codex, I just think it’s a cool word that has the word “code” in it as a substring.
Please do not use the GitHub-rendered view of this file, as many things like links and citations simply do not work. Instead go to https://funloop.org/codex for the best experience, on a desktop or laptop screen (mobile devices don’t work very well, not to mention the missing Table of Contents sidebar).
Every problem gets its own README.org file in its own subfolder. The solutions
are all in Python. All solutions are “standalone” in that none of them use any
libraries other than what’s provided by Python’s standard libraries.
The problems are drawn mainly from [cite:@epip]. Other reference materials are cited where applicable. Below is a table of every problem, with tags that give a brief description of each one, and references.
| Name | Tags | References |
|---|---|---|
| Parity | bitwise | [cite:@epip 27; @hd 96] |
| Rectangle overlap | geometry | [cite:@epip 39] |
| Rearrange list | array, partitioning | [cite:@epip 41] |
| Dutch national flag | array, partitioning | [cite:@epip 43; @levitin 200; @sedgewick 296-301; @pearls 123; @cormen 186; @skiena 125-126] |
| Buy and sell stock once | array | [cite:@epip 51; @cormen 69] |
| Buy and sell stock twice | array | [cite:@epip 53] |
| Interconvert strings and integers | array, string | [cite:@epip 75] |
| Merge sorted linked lists | linked list | [cite:@epip 92] |
| Height-balanced binary trees | binary tree | [cite:@epip 124] |
| Merge monotonically increasing streams | priority queue | [cite:@epip 144] |
| Find first occurrence from sorted array | binary search | [cite:@epip 155] |
| Anonymous message from magazine | hash table | [cite:@epip 175] |
| Intersection of two sorted arrays | sorting | [cite:@epip 194] |
| Validate binary tree as BST | binary tree | [cite:@epip 213] |
| Tower of Hanoi | recursion, binary tree | [cite:@epip 233] |
| Maximum Subarray | divide and conquer, dynamic programming | [cite:@epip 250; @pearls 77] |
| Making Change | dynamic programming | [cite:@epip 253; @taocp1 sec. 1.2.9]] |
Some problems can only be solved in an elegant way if we use particular data structures. See below for introductory discussions about some of these.
| Name | Tags | References |
|---|---|---|
| Linked list | linked list | [cite:@epip 91] |
| Stack (with “max” method) | stack | [cite:@epip 106] |
| Binary tree | tree | [cite:@epip 123] |
| Binary search tree | tree | [cite:@sedgewick 396] |
| Heap | tree, heap, priority queue | [cite:@sedgewick 308] |
- Python tricks
- There are some Python-language-specific tricks available for programming problems. You might want to skim over this if your Python skills are rusty.
- Mathematics
- Some (some would argue all) topics in programming have mathematical underpinnings.
| Dependency | Why |
|---|---|
| Ruff | for linting |
| Mypy | for enforcing type hints |
| Hypothesis | for property-based tests |
All solutions to the problems are implemented in Python, and tested with basic unit tests and the Hyothesis property-based testing framework. Each problem’s discussion comes with its own test suite. All source code samples are linted as well with ruff and mypy. Testing has been extremely valuable in checking the correctness of the puzzle solutions collected in this work.