Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

news.ycombinator.com

Post reply on HN
Print view View original

421–430 of 507 posts

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

#421

Post by TN1ck »

muzzio wrote: post #303

Extremely simple one, but my favorite is an algorithm for determining if two words are anagrams of each other: The Fundamental Theorem of Arithmetic states: "every integer greater than 1 either is a prime number itself or can be represented as the product of prime numbers and that, moreover, this representation is unique, up to (except for) the order of the factors."[1] So to determine that two words are anagrams of…

This one came up a lot when I was researching the most efficient way to generate anagrams, but the numbers are growing way too fast. In the end, a frequency map and comparing the frequencies worked best. My use case is a bit special, as I'm creating anagram sentences, so a Trie or similar things wouldn't work. Check out https://anagrams.io if you're interested.

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

#422

Post by make3 »

BPE (byte pair encoding) as used in state of the art neural translation models , maximize the information per token by greedy iterative merging of the most common (lowest information) tokens, until a predefined max number of tokens is reached https://en.m.wikipedia.org/wiki/Byte_pair_encoding

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

#423

Post by make3 »

keithnz wrote: post #420

Xor Swap.... https://en.wikipedia.org/wiki/XOR_swap_algorithm not because it's super practical ( and there are other variations using other operators ) I like it because it is super simple and when I first encountered it early on in my learning, it was really not immediately obvious why it worked. It's probably been the simplest piece of code that's surprised me.

I was asked this in an interview. I was a bit pissed

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

#424

Post by make3 »

btilly wrote: post #405

The rsync algorithm. There is a theorem that it is impossible in general to remotely compare two files with less network traffic than it requires to simply send one file over the wire. But rsync does it. How? By accepting a theoretical but unlikely possibility of coming up with the wrong answer. What rsync does is compare hashes of ranges of stuff. If the hash comes out the same, the two are assumed to be identical w…

rsync also checks modification dates. you would have to be extremely unlucky for both the checksums and the modification dates to be ok but for the files to be different

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

#425

Post by gorb314 »

Constructive Solid Geometry using BSP trees.

There is a javascript implementation [0] which is where I saw it the first time, it is about 500 lines of fully commented code. The algorithm is so simple, I absolutely love it.

Basically, when performing a union on two meshes, we determine the 3d BSP trees from both meshes, then simply clip each mesh using the other's tree. The output is the union of the two leftover meshes.

And since both intersection and difference can be written as a combination of inversion and union, they are simply composed from those.

I can't find a good paper on the algorithm though, not sure where exactly it originated.

[0] https://github.com/evanw/csg.js/blob/master/csg.js

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

#426

Post by __turbobrew__ »

HereBeBeasties wrote: post #396
api_or_ipa wrote: post #353

Earlier quoted context omitted.

`git bisect` is an indispensible git trick. You give it commit where you know the bug exists, and one where you know it doesn't and it'll use binary search to help you find where the bug came from. It's absolutely wonderful.

I always struggle to see why people bang on about git bisect. You need tests to make it work. If you have tests, why aren't you running them continuously? If you're running them continuously, why do you need git bisect?

It's useful for projects where maintaining tests is impractical such as the linux kernel. When someone tries to find a regression in the kernel they are probably going to write a test which grep's dmesg for a certain output, or sometimes the regression is a kernel panic and you are basically checking if your system crashes or not on each bisect step.

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

#427

Post by gavanwoolery »

In terms of physical beauty, my favorite algorithm is the voronoi diagram. The 2D variant is rather boring, but the 3D version looks great and is capable of representing many natural phenomena from cellular division to material fragmentation (a common use is procedural generation of rocks).

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

#428

Post by QML »

make3 wrote: post #423
keithnz wrote: post #420

Xor Swap.... https://en.wikipedia.org/wiki/XOR_swap_algorithm not because it's super practical ( and there are other variations using other operators ) I like it because it is super simple and when I first encountered it early on in my learning, it was really not immediately obvious why it worked. It's probably been the simplest piece of code that's surprised me.

I was asked this in an interview. I was a bit pissed

Doesn't sound too bad; a basic property of XOR is that two of them cancel out, so y ⊕ x ⊕ x is just y.

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

#430

Post by QML »

joker3 wrote: post #325
Juminuvi wrote: post #202

Earlier quoted context omitted.

Interesting! I knew that med school applicants were accepted on some sort of ranking and matching process but didn't realize there was a real algorithm behind it. This, or one similar, seems to be what's behind it.

There's no matching process at the beginning of medical school, but there is for assigning med school graduates to residencies. This variant of the problem is NP-hard, so there's no exact solution, but matching still works pretty well. https://web.stanford.edu/~alroth/papers/rothperansonaer.PDF has all the details.

When you are referring to this "variant", are you referring to maximal matching, or bipartite matching when the number of people and schools don't equal?
Post reply on HN