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

BogoSort is an algorithm. Not a very good algorithm, but an algorithm nevertheless.

The backpropagation algorithm is at once simple and incredible. It enables automatic parameter optimization for millions of parameters for extremely complex, nonlinear functions, all with just a basic knowledge of calculus.

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 process can run too slowly when it encounters transient errors. (Temporary network glitch, database under high load because of a cache flush.)

So, we pick an ideal small retry interval, and the maximum tolerable interval. (In my case, it's usually 30 seconds and 15 minutes.) Then, when errors happen, the retry interval keeps doubling until it hits the largest interval. So, the operation is retried at 30 seconds, 1 minute, 2 minutes, 4 minutes, 8 minutes, and then every 15 minutes until it succeeds.

The result is that transient errors don't cause large delays. Situations where a defect prevents a request from submitting don't DOS, because the retry interval throttles itself longer and longer.

My first programming project was a tic-tac-toe game with a computer opponent. I painstakingly copy-pasted about a hundred nested `if` statements to check for a winner & decide the computer’s next move.

Several years later I saw a Matlab demo that did this by indexing the grid using values from a 3x3 magic square[1]. In a magic square, every row, column, and diagonal has the same sum. So checking for a winner was just checking if a player’s three moves added up to 15. Finding a space that would make the computer win, or block the human opponent from winning, was subtracting two moves from 15 and checking if that spot was available.

[1]: https://en.wikipedia.org/wiki/Magic_square

Hashcash, a proof-of-work system adapted by Bitcoin:

https://bitcoinmagazine.com/articles/genesis-files-hashcash-...

1. It solves an extremely practical problem (spam) using a very simple idea (provide a value that when appended to a message gives a hash value within an acceptable target range).

2. It can be understood by non-experts who simply understand (or accept) the one-way nature of cryptographic hash functions.

3. It can be implemented manually, given a working hash function.

4. It sat around for a decade in obscurity until someone dusted it off to build a system most thought was impossible.