Wrap-up and resources
Final recap
- 1. Pascal's Triangle: Build incrementally on what you already computed:
row[i] = prev[i-1] + prev[i]. Both edges are fixed, the inner loop isrange(1, row_index), and the answer forn <= 0is[]. TheO(n²)lower bound is set by the output size, not the algorithm's cleverness. - 2. Lockboxes: Translate the story into a structure: a box is a node, a key is an arrow, and the question is reachability. The
openedset prevents cycles and does the counting, the0 <= key < nguard protects you from box-less keys, and the answer islen(opened) == n. - 3. Minimum Operations: Paste multiplies rather than adds, multiplying by
kcosts exactlykoperations, and splitting into primes is never worse becausea+b <= a·b. So the answer is the sum of the prime factors, and0forn <= 1. - 4. Log Parsing: A stream is read line by line in constant memory, indexing from the end steps over variable-length fields, the counter rises only for valid lines, and
except KeyboardInterruptrather thanfinallyhandles the interruption, whilesorted(counts)guarantees ascending order. - 5. UTF-8 Validation: The number of leading 1s in the first byte is the character's length, a continuation is always
10xxxxxx,num & 0xFFbecause we handle only the low 8 bits, check shortest pattern first, andcontinuation == 0at the end is what rejects a truncated sequence. - 6. N Queens: One queen per row removes half the problem, and the
row-colandrow+coldiagonal invariants make the check instant. Backtracking cuts the impossible branch early: 15,720 placements instead of 16.7 million arrangements atN=8. And never forget the cleanup after each call.
The thread connecting all fiveEvery one of these five got easier after being reframed: a table, a graph, a factorisation, a stream, a state machine. The code came last and was always short. Thinking before typing is not moral advice, it decides how long and how correct your solution is.
Complete glossary
| Term | Definition | Part |
|---|---|---|
| Incremental build | Building the result step by step from previously computed results, instead of recomputing from scratch | 1 |
| Off-by-one error | A loop bound or index that is one too high or too low, the most common bug in array work | 1 |
Combinations C(n,k) | The number of ways to pick k items from n without ordering; exactly the value of a cell in Pascal's triangle | 1 |
| Directed graph | A set of nodes joined by one-way arrows; a box is a node, a key is an arrow | 2 |
| Reachability | Is there a chain of arrows from the entry node to a given node? | 2 |
| Depth-first search (DFS) | Exploring one branch to its end before backtracking; implemented with a stack or recursion | 2 |
| Breadth-first search (BFS) | Exploring all near neighbours first; implemented with a deque, and the one that yields shortest paths | 2 |
The set | A structure with roughly constant-time membership; choosing it over a list turns O(n²) into O(n) | 2 |
| Prime factor | A prime that divides the number; a number's prime factorisation is unique | 3 |
| Closed form | A formula that computes the result directly, with no search and no iteration, like "the sum of the prime factors" here | 3 |
| Brute force | Trying every possibility; always correct, usually slow, and useful as a reference for verification | 3 |
| Stream | A data source whose length you do not know in advance and which is read incrementally; sys.stdin is one | 4 |
| Accumulator | A variable holding the running result during a single pass over the data | 4 |
KeyboardInterrupt | The exception Python raises on Ctrl+C; caught with except and re-raised with raise | 4 |
The __main__ guard | The if __name__ == "__main__" condition that stops code running on import | 4 |
| Bit and byte | A bit is a binary digit (0 or 1); a byte is eight bits, a value from 0 to 255 | 5 |
The shift >> | Pushing bits right to discard what you are not inspecting; byte >> 7 keeps the first bit | 5 |
The mask & 0xFF | An operation keeping the low 8 bits and discarding the rest, so 256 becomes 0 | 5 |
| Variable-length encoding | An encoding that uses a different number of bytes per character depending on how common it is, what UTF-8 does | 5 |
| Continuation byte | A byte completing a character begun by an earlier one; its pattern is always 10xxxxxx | 5 |
| Self-synchronisation | The property of an encoding that lets you find the next character's start from any position, without reading from the beginning | 5 |
| State machine | One variable holding "where am I in the processing", plus rules for moving between states | 5 |
| Backtracking | Building a solution step by step and returning the moment the current piece becomes impossible, cutting off a whole branch of possibilities | 6 |
| Pruning | Discarding a branch of the search tree before exploring it, because a constraint has proved it cannot lead to a solution | 6 |
| Search tree | Representing possibilities as a tree: each level a decision and each branch a choice; backtracking walks it depth-first | 6 |
The row-col diagonal invariant | A value that stays constant along a ↘ diagonal, identifying it by one number instead of walking its squares | 6 |
The row+col diagonal invariant | Its counterpart for the ↙ diagonal: the sum is constant along it | 6 |
| Cleanup after the call | Undoing the step's effect (removing from the sets and lifting the queen) before returning, the thing that makes backtracking correct | 6 |
| Transpose | Swapping rows with columns: m[r][c] ↔ m[c][r]. | 7 |
| In place | Changing the same data without a new copy. | 7 |
| zip(*m) | Python's shortcut for taking a grid's columns. | 7 |
| Dynamic programming | Saving answers to smaller problems and building on them. | 8 |
| Base case | The smallest problem with a known answer, like amount 0. | 8 |
| Greedy | Taking the locally best choice at each step. | 8 |
| Promise | A promise of a value that arrives later, or an error. | 9 |
| Promise.all | Waits for all and keeps the input order. | 9 |
| allSettled | Waits for all and returns each one's success or failure. | 9 |
| DIRS | The list of four directions, to avoid repeated code. | 10 |
| Bounds check | 0 <= nr < rows and 0 <= nc < cols before reading. | 10 |
| DFS | Depth-first search: go as far as you can, then back up. | 10 |
| Prime | A number above 1 divisible only by 1 and itself. | 11 |
| Sieve | Crossing out each prime's multiples, leaving the primes. | 11 |
| Prefix sum | prefix[i] = the sum of elements up to i, for O(1) range questions. | 11 |
Sources
The best outside resources for these lessons, classified by kind and level. All are open to everyone and need no account on any platform. Use the filters to narrow the list.
0 resources
Video (2)
Interactive tools (8)
Interactive toolBig-O Cheat SheetOne colour-coded board: access, search, insert and delete complexity for every data structure, plus the sorting algorithms. Keep it in front of you.bigocheatsheet.comBeginnerInteractive toolComprehensive Python CheatsheetA single page covering all of Python in short examples: lists, dicts, sets, slicing, functions. Search it with Ctrl+F instead of navigating the docs.github.comBeginnerInteractive toolTheAlgorithms/Python"All algorithms implemented in Python": read an alternative implementation of your problem after you have solved it yourself, not before.github.comIntermediateInteractive toolPython TutorRuns your code step by step and draws the memory: ideal for tracing the Pascal build or the growing set in lockboxes.pythontutor.comIntermediateInteractive toolVisuAlgo, DFS and BFSA live animation of both searches on a graph you draw yourself: see the visit-order difference with your own eyes.visualgo.netIntermediateInteractive toolOnline PythonA browser Python editor with nothing to install: paste any solution from this guide and run it immediately.online-python.comIntermediateInteractive toolVisuAlgo, animated data structures and algorithmsTwenty-four interactive modules from the National University of Singapore, including the recursion tree that shows the shape of a depth-first search.visualgo.netIntermediateInteractive toolBig-O Cheat SheetOne table collecting the complexity of every operation on every data structure, with a colour-coded chart ranking growth rates from excellent to horrible.bigocheatsheet.comBeginner
Official documentation (10)
Official docsPython Docs, Data StructuresThe official reference for lists, nested lists and the negative indexing the Pascal's triangle solution rests on.docs.python.orgBeginnerOfficial docsPython Docs, range()range() and its bounds in detail: inclusive start, exclusive stop, exactly where off-by-one bugs originate.docs.python.orgBeginnerOfficial docsPython Docs, SetsThe set and its operations, the structure that turns the lockboxes solution from quadratic to linear.docs.python.orgBeginnerOfficial docsPython Docs, dequeThe right structure for BFS: constant-time appends and pops at both ends, unlike pop(0) on a list.docs.python.orgBeginnerOfficial docsPython Docs, sys.stdinThe official reference for standard input: how it reads as a stream, and when it is buffered.docs.python.orgIntermediateOfficial docsPython Docs, Errors and ExceptionsThe precise execution order of try/except/else/finally, which explains why finally double-prints here.docs.python.orgIntermediateOfficial docsPython Docs, CounterA cleaner alternative to a dict as a counter, with most_common and arithmetic between counters.docs.python.orgIntermediateOfficial docsPython Docs, Unicode HOWTOHow Python separates text from bytes, and exactly what encode and decode do.docs.python.orgAdvancedOfficial docsPython Docs, Bitwise operationsThe official reference for >>, & and | on integers, this part's entire toolkit.docs.python.orgAdvancedOfficial docsPython Docs, sysThe official reference for sys.argv and sys.exit, the only import the project allows.docs.python.orgBeginner
Articles and explainers (16)
ArticlePascal's Triangle, the mathematicsThe triangle's properties and its links to combinations and binomial expansion, with the proofs behind the rule.en.wikipedia.orgBeginnerArticlePython Time ComplexityA table of the cost of every list, set and dict operation, read it once and it changes how you pick structures.wiki.python.orgBeginnerArticleDepth-first searchThe algorithm you wrote in this project, in its general form and in both iterative and recursive versions.en.wikipedia.orgBeginnerArticleBreadth-first searchThe alternative that gives the same answer here and shortest paths elsewhere, the whole difference is the waiting structure.en.wikipedia.orgBeginnerArticleThe fundamental theorem of arithmeticWhy every number has exactly one prime factorisation, which is what guarantees your answer is unique.en.wikipedia.orgIntermediateArticleTrial divisionExactly the method you used, and why stopping at the square root suffices instead of going to n.en.wikipedia.orgIntermediateArticleReal Python, The modulo operatorA long-form explanation of % and // including their behaviour with negatives, the trap that catches most people.realpython.comIntermediateArticleReal Python, The __main__ guardThe clearest explanation available of this guard, which the project explicitly requires.realpython.comIntermediateArticleUTF-8, the full standardThe same pattern table as in this part, plus the overlong encodings and surrogate ranges the project skips.en.wikipedia.orgAdvancedArticleJoel Spolsky, The absolute minimum about UnicodeThe classic article explaining why UTF-8 exists at all, and where the mojibake on broken pages comes from.joelonsoftware.comAdvancedArticleUTF-8 EverywhereA long-form argument for using UTF-8 everywhere, with a frank comparison against UTF-16 and its problems.utf8everywhere.orgAdvancedArticleWikipedia, Eight queens puzzleThe history of the puzzle and a table of solution counts per N, which lets you confirm your solution prints 2, 10, 4 and 92 in the right places.en.wikipedia.orgIntermediateArticleWikipedia, BacktrackingThe general definition of backtracking as a class of algorithms, with the queens puzzle as its classic textbook example.en.wikipedia.orgIntermediateArticleEmory CS171, The N-Queens Problem & BacktrackingAn academic walkthrough that counts the search space in numbers, builds the solution with a stack, and gives a general backtracking template.mathcenter.oxford.emory.eduIntermediateArticleGeeksforGeeks, N Queen ProblemThree graded approaches: plain backtracking, then tracking columns and diagonals with arrays, then bit-masking.geeksforgeeks.orgBeginnerArticleWikipedia, Queen in chessThe queen's movement along rank, file and diagonal, which is exactly the three checks your solution rests on.en.wikipedia.orgBeginner
- Every piece of code and every output in this guide was executed on Python 3 while it was written; the outputs are copied from real runs, not written from expectation.
Resources for this lesson
Grouped by type. Start with the official docs for precision, or an article or video for the explanation.
Tools2
Done with this lesson?
Sign in to save your progress.