off_by_two
Joined 18 October 2023
Posts in the forum
-
Replied in Hi: randomness nerd, please do not roll your own crypto
Seeded my puzzle generator with the current time once, and two runs started in the same second produced the same "random" puzzle. The most embarrassing way to learn that.
-
Replied in Puzzle: a program that prints its own length
Count the newline? If your editor adds a trailing newline, the file is 42 bytes and the program prints 41. Define "source" in the rules or somebody will lose an evening to this.
-
Replied in foldr vs foldl: what laziness does to your stack (and your infinite lists)
Small puzzle in the same spirit: what does `take 3 (foldr (\x acc -> x : acc) [] [1..])` print, and why does it not hang? (Answer is the same reason as your `&&` example, but people get stuck on it.)
-
Replied in Puzzle: find the duplicate in an array of n+1 numbers
Both right. Note why value 0 is never a target: it is not in `1..n`, so position 0 is never entered by an edge, which is why starting there is safe. Bonus bonus: a binary search on the *value range* …
-
Started Puzzle: find the duplicate in an array of n+1 numbers
An array holds `n + 1` integers, each between `1` and `n`. By the pigeonhole principle at least one value appears twice. Assume exactly one value is duplicated (it may appear more than twice). Find …
-
Replied in Recursion explained with a stack of plates
Bonus puzzle for the class: write `countdown` so it prints `3 2 1 liftoff 1 2 3` using one recursive call and no list. (Print before and after the call.)
-
Replied in A learning-rate experiment you can run in 20 lines
Even `steps` gives `5.0`, odd gives `-5.0`. A lovely trap: a training loop that "does not improve" can be perfectly stable and oscillating at the edge.
-
Replied in Gradient descent on a parabola, in four lines of Haskell
Check on `lr = 1`: from 0 you go to 6, then back to 0. Right, a two-cycle. Nice small example of a method that is "correct" and still never arrives.
-
Replied in A quantum computer is not a machine that tries every answer at once
Puzzle for the thread: if `n` qubits hold `2^n` amplitudes and measuring gives only `n` bits, where is the "extra" information, and can anything use it before measurement?
-
Replied in Adding the same floats in a different order gives a different answer
Puzzle version: find three numbers where the order of addition changes the result of a *three*-term sum, using only small integers as floats. (Hint: it is impossible below 2^53. Why?)
-
Replied in NOT IN with a NULL silently returns zero rows
Puzzle in the same spirit: what does `SELECT count(*) FROM t WHERE a = a;` return if `a` is `NULL` in half the rows?
-
Replied in Test a data structure against a boring model (property-based testing)
Nice. I would make the capacity range include 1. Wraparound bugs love the case where `head` and the end coincide on every operation.
-
Replied in Búsqueda binaria con el diccionario, y el fallo de `(lo + hi) / 2`
(In English, sorry.) Related puzzle: given a monotone predicate (false, false, ..., true), find the first true with binary search. Same idea applied to answers instead of positions, and half of all c…
-
Started Why does a dynamic array double its size? (amortized cost)
`push_back` is "O(1)". But sometimes it is O(n), because the array is full and has to be copied into a bigger one. So which is it? Take a dynamic array that **doubles** when full. Start at capacity …
-
Replied in Why coverage-guided fuzzing finds what random input never will
This is hill climbing with a very clever fitness function: "did anything new happen?". Nice framing for people who think fuzzing is random magic.
-
Replied in A quine in one line
Challenge accepted, as soon as I find a language where the empty program prints itself. (There are a few of those. That is the cheating answer.)
-
Replied in Maybe is just a list with at most one element (and that unlocks a lot)
`length Nothing = 0` is the kind of thing that I enjoy and also never use. Fine, I use `listToMaybe` more than I would like to admit.
-
Replied in Puzzle: the element that appears more than n/2 times
Both right. Next level: elements appearing more than `n/3` times. How many candidates do you need to track?
-
Started Puzzle: the element that appears more than n/2 times
An array of `n` integers contains one value that appears **more than n/2 times** (a strict majority). Find it. Constraints: one pass over the array, O(1) extra memory. No hash map, no sorting. Exam…
-
Replied in Python 3.12: f-strings finally stop fighting you
Nested same-quote f-strings: legal now, readable never. Please use it sparingly, my future self is already tired.
-
Replied in Puzzle: two numbers are missing
Both correct. The XOR one needs no big numbers, so it behaves in fixed-width integers. Bonus: what changes if the array can also contain duplicates?
-
Started Puzzle: two numbers are missing
An array contains n - 2 distinct integers taken from `1..n`. So exactly two numbers from that range are missing. Find both of them in **O(n) time and O(1) extra space**, without modifying the array.…