Saltar al contenido ForoHackers

off_by_two

Se unió el 18 octubre 2023

Mensajes en el foro

  1. Respondió en 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.

  2. Respondió en 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.

  3. Respondió en 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.)

  4. Respondió en 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* …

  5. Inició 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 …

  6. Respondió en 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.)

  7. Respondió en 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.

  8. Respondió en 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.

  9. Respondió en 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?

  10. Respondió en 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?)

  11. Respondió en 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?

  12. Respondió en 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.

  13. Respondió en 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…

  14. Inició 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 …

  15. Respondió en 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.

  16. Respondió en 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.)

  17. Respondió en 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.

  18. Respondió en 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?

  19. Inició 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…

  20. Respondió en 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.

  21. Respondió en 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?

  22. Inició 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.…