Ask HN: What's your favorite elegant/beautiful algorithm?

Post by Izkata » Wed, Oct 17, 2018, 5:51 PM UTC

gwbas1c wrote: post #225

Exponential backoff: I don't know if this is a published algorithm. Basically, background processes need to keep retrying an operation until it succeeds. (Make an API call to a server, upload a file, ect, ect.) If the retry interval is too small, you can DOS the remote server. (Server returns a 5xx error because there's a corner case that hits a defect.) But, if the retry interval is too large, your background proces…

Post by api_or_ipa » Wed, Oct 17, 2018, 6:01 PM UTC

gyrgtyn wrote: post #342

netgusto wrote: post #20

Binary search. Very simple, incredibly powerful; can search on data or math function. It's the basis for other CS concepts. JS implementation: https://gist.github.com/netgusto/90c8e0e7019a832cbf95eac58e1...

A cool thing about binary search is you can also use it in real life. It's great for troubleshooting.

Post by teddyh » Wed, Oct 17, 2018, 6:08 PM UTC

mtreis86 wrote: post #186

My favorite is the FLAC algorithm. It's fairly simple to explain - take a signal input, pattern match a generative signal that closely matches the original or part of it, and the output is a combination of that generative code and the difference between it and it and the input. Second favorite is the LISP REPL. Specifically the Eval function, thanks to this classic video of Sussman https://www.youtube.com/watch?v=0m6…

Post by DonaldPShimoda » Wed, Oct 17, 2018, 6:13 PM UTC

jansan wrote: post #242

The Euclidean algorithm to compute the greatest common divisor of two numbers. In Javascript, if you have two numbers x and y that are both greater than zero, you compute the greatest common divisor xyGcd in one beautiful line of code: var xyGcd = function gcd(a,b){ return b ? gcd(b, a%b) : a; }(x, y); In my opinion this is the greatest one-liner ever.

    > let fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
    > take 7 fibs
    [1,1,2,3,5,8,13]
    > fibs !! 1000
    70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501

Post by DonaldPShimoda » Wed, Oct 17, 2018, 6:16 PM UTC

tomp wrote: post #201

mattyw wrote: post #158

Earlier quoted context omitted.

I like implementing type systems Could you expand on this? This is something I've just started reading about. I'd be interested in good resources to use to get started. At the moment I've just started reading TAPL.

Check out https://github.com/tomprimozic/type-systems there's been a few HN threads about it as well. I can also answer any specific questions you have, or if you want further resources I can try and find them... (there's a good online book I have in mind, but I've no idea how to find it right now!)