Tasks

00 What a program can do

• How many steps for 97? start-collatz

01 First program, first bug

• The quote fix-quote
• A typo in a name fix-name
• The year of publication fix-type
• An extra indent fix-indent
• Minutes in a day fix-logic

02 Names and values

• How many seconds have you lived? seconds-lived
• Splitting the bill tip-split
• The swap swap
• Dollars into cents float-trap

03 Forks in the road

• Leap year leap-year
• What kind of triangle triangle-kind
• Rock, paper, scissors rps-judge
• The troll bridge quest-room

04 Again and again

• Multiplication table times-table
• Sum of digits digit-sum
• All the primes up to n primes-upto
• Cross-stitch weave-pattern
• The Collatz record holder collatz-record

05 Words of your own

• Is it prime? is-prime
• Greatest common divisor gcd
• Roman numerals to-roman
• Checking a card number luhn

06 Lists

• The strongest quake-strongest
• The average quake quake-mean
• Top k top-k
• Rotating the roster rotate-list
• Silver second-largest

07 A conversation made of strings

• A mirror for ELIZA eliza-reflect
• Palindrome is-palindrome
• Initials and surname capitalize-names
• How many times a word word-count
• A signed quine my-quine

08 Dictionaries and the telegraph

• The type case char-freq
• The reverse alphabet invert-dict
• Anagrams group-anagrams
• Common words common-words

09 A problem inside a problem

• A power in twenty steps power
• Flatten a list flatten
• The Brahmins’ moves hanoi-moves
• Permutations permutations
• Sierpiński in asterisks sierpinski

10 Functions as values

• Quakes by country sort-by-key
• Beads of functions compose
• A word tally that remembers make-counter
• Endless primes primes-gen
• A MapReduce of your own word-count-mr

11 The inquiry report

• Division with a fallback safe-divide
• Reading an age parse-age
• A sixteen-bit register int16-overflow
• Tests that catch mutants write-tests

12 The island of rabbits and foxes

• A rabbit rabbit-class
• A vector vector2
• A bank account bank-account
• A family of shapes shape-hierarchy

13 What a program costs

• Count without running count-ops
• A catalog without duplicates dedupe-fast
• A pair with a given sum pair-sum-fast
• A patch for the catalog gta-catalog

14 How a list lives in memory

• The law of growth find-growth
• A dynamic array of your own dyn-array
• A linked list with a tail linked-list
• Reverse the chain reverse-linked

15 Stacks, queues and a calculator

• A strict RPN calculator eval-rpn
• Where the brackets broke balanced
• A yard with powers shunting-yard
• A queue from two stacks queue-two-stacks

16 Hash tables: attack and defense

• A card index of your own hashmap
• An attack on PHP collide
• The robot vacuum came back first-repeat
• A card index of card numbers luhn-bucket

17 A garden of search trees

• Planting bst-insert
• How many levels bst-height
• In order, without recursion inorder
• An honest tree is-bst
• From here to there range-query

18 Who is next

• A priority queue of your own heap-push-pop
• The ten quietest k-smallest
• Merging sorted lists merge-sorted
• A running median running-median

19 Six handshakes

• The shortest chain bfs-path
• Islands islands
• A loop in the dependencies has-cycle
• Reading order topo-order
• The center of the metro metro-hops

20 The sorting tournament

• Binary search without bugs binary-search
• How many in a range count-in-range
• Insertion with a key insertion-sort
• The sorting machine radix-sort

21 Divide and conquer

• Merge sort merge-sort
• The k-th smallest quickselect
• How much disorder count-inversions
• Karatsuba multiplication karatsuba

22 Remember instead of recomputing

• A staircase with rotten steps stairs
• A till with empty slots coin-change
• Damerau’s amendment edit-distance
• What two versions share lcs
• The burglar’s rucksack knapsack

23 Greed and electricity

• One crew activity-select
• Who is connected to whom union-find
• Kruskal’s network kruskal
• Huffman code huffman

24 The navigator

• Dijkstra’s wave dijkstra
• Bellman–Ford bellman-ford
• A* on a grid grid-astar
• A route across the metro metro-route

25 Flows and matchings

• How much the network carries max-flow
• The bottleneck min-cut-edges
• Seat as many as you can bipartite-match
• A stable matching gale-shapley

26 Let's flip a coin

• The area of a blot mc-area
• The reservoir reservoir
• A primality test miller-rabin
• A Bloom filter bloom

27 A needle in a haystack

• A tune in the notes kmp
• The rolling window rabin-karp
• Keyboard suggestions trie-complete
• The longest repeat longest-repeat

28 Everything is bits

• Binary and hexadecimal to-binary
• Two’s complement twos-complement
• UTF-8 by hand utf8-encode
• The automatic detective fix-mojibake

29 Logic from switches

• Three more parts from NAND gates-from-nand
• The full adder and its mirror image full-adder
• A switchman without if mux
• The vote majority

30 The machine does arithmetic

• Addition without plus add-bits
• The Iskra-8 ALU alu
• The fourth flag overflow-flag
• Multiplication by shifting shift-multiply

31 Memory and the clock

• A latch and a flip-flop, tick by tick d-flipflop
• A counter without plus counter
• A traffic light with a button traffic-fsm
• Weave a word rope-encode

32 You are the processor

• Sum up to zero iskra-sum
• Multiply fast iskra-mul
• A histogram on the screen iskra-draw
• Your own assembler assembler

33 An X-ray of Python

• A machine with jumps stack-vm
• Working back from the X-ray predict-dis
• A sum in C c-sum

34 Near and far

• An LRU cache lru-cache
• Cache simulator cache-sim
• Transposing in tight quarters matrix-order

35 The pipeline and the fortune-teller

• A table of fortune-tellers predictor-sim
• The loud parts vectorize
• How many cores to buy amdahl

36 A tour of a living system

• sort | uniq -c in Python pipeline
• Your own wc count-lines
• One-liners shell-basics

37 Mission control

• A round-robin schedule round-robin
• Shortest job first, for real avg-wait
• A spider on asyncio async-crawl

38 The hotel of addresses

• Counting the moves page-faults
• An anomaly to order find-belady
• A book in two volumes translate

39 Races

• The view counter fix-race
• A transfer without deadlock bank-transfer
• A belt of your own producer-consumer
• Dinner without deadlock deadlock-free

40 The rescue operation

• Parity xor-parity
• The disk is dead, the data lives rebuild-disk
• A sum with a memory checksum
• A git of your own content-store

41 A day in the life of a packet

• The longest prefix longest-prefix
• How long a file takes transfer-time
• Cutting up and putting together packetize

42 Inventing a protocol

• Stop and wait stop-and-wait
• Echo echo-server
• An address plan for an office subnet

43 Anatomy of this page

• Parse a request parse-request
• A server of your own mini-http
• The server log status-codes

44 The parliament of Paxos

• The island’s clocks lamport-clock
• The chair’s quorum quorum
• Electing the elder leader-election

45 The archivist

• The deepest sql-top-quakes
• Long words and short words sql-group
• Airports in the shaking zone sql-join
• One-airport cities sql-null

46 The library and the bank

• Weather stations create-index
• A transfer without losses atomic-transfer
• From here to there btree-search

47 The packing contest

• Fax rle
• LZ77 there and back lz77
• Entropy with context entropy
• The inverse transform bwt

48 A search engine for our textbooks

• The index inverted-index
• TF-IDF tf-idf
• PageRank pagerank

49 The museum of languages

• The Brainfuck machine brainfuck
• A translator from Brainfuck bf-compile
• FizzBuzz in three styles fizzbuzz-styles

50 The field linguist

• A lexer with quotes tokenize
• The tree of a formula calc-parser
• A JSON of your own json-parser
• A mini linter unused-names

51 The nesting doll

• A lexer for parentheses lisp-tokenize
• A tree from tokens lisp-parse
• A calculator on parentheses lisp-eval-arith
• Names and branches lisp-define
• Closures lisp-lambda
• Recursion with no bottom lisp-recursion

52 Closing the circle

• Fold it in advance const-fold
• An expression in machine code codegen-expr
• Loops and branches codegen-while

53 Null on trial

• Getting past mypy annotate
• Digging without a fall option-chain
• Units under control units-checker
• A type checker type-check

54 Automata and regular expressions

• A date, American style re-date
• A phone number on one line re-phone
• Email without backtracking re-email
• Run an automaton dfa-run
• The subset construction nfa-to-dfa

55 The Turing machine

• A counter tm-increment
• A palindrome, without erasing tm-palindrome
• A simulator of your own tm-simulator

56 A conversation with the Oracle

• The contrarian contrarian
• The reduction halt-to-hello
• The beaver racer bb-run

57 Gödel’s letter

• Check the seating verify-hamilton
• Coloring as a formula coloring-to-sat
• A SAT solver of your own dpll

58 The salesman’s expedition

• Untangle the route two-opt
• The wedding table annealing
• Greedy cover set-cover-greedy

59 The cipher bureau

• A day’s intercepts break-caesar
• The key length vigenere-key-length
• The pad twice otp-xor
• A little bombe enigma-crib

60 A secret in plain sight

• The paint exchange in numbers dh-exchange
• RSA, the whole thing rsa-toy
• Eve and the short key crack-small-rsa
• Passwords for a website salted-hash

61 The training range

• Close the login against injection sqli-fix
• Check the bound bounds-check
• A password estimator password-strength

62 The bot tournament

• The unbeatable X minimax-ttt
• Prune the waste alphabeta
• A Connect Four fighter connect4-bot

63 The machine learns

• A line by descent linear-gd
• Rosenblatt’s perceptron perceptron
• Nearest neighbors knn-digits
• A network for any gate xor-net

64 The qubit lab

• A two-qubit simulator qsim-2
• The four Bell states bell-state
• Grover: from four to sixty-five thousand grover-4

65 The blank spots

• Check a renaming iso-check
• Check a multiplication scheme strassen-check
• A guide to the course capstone