Ask HN: What's your favorite elegant/beautiful algorithm? • Hacker News Board

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

#461

Post by jules » Thu, Oct 18, 2018, 9:59 AM UTC

raymond_goo wrote: post #449

jules wrote: post #444

Earlier quoted context omitted.

Perhaps instead of being mean, you could be helpful and post a link to said answer.

With 64 bit variables it probably works. But for less here is the correct implementation: https://ai.googleblog.com/2006/06/extra-extra-read-all-about...

This implementation:

    mid = ((unsigned int)low + (unsigned int)high)) >> 1;

essentially extends the bit width from 31 bit to 32 bit by going from signed to unsigned, and is thus correct up to array lengths of order 2^31 rather than 2^30. Using an even larger bit width should classify as at least as correct as this.

In summary,

(low + high)/2 or (low + high) >> 1 is correct up to 2^30 for 32 bit signed and up to 2^62 for 64 bit signed, up to 2^31 for 32 bit unsigned, and up to 2^63 for 64 bit unsigned.

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

#462

Post by n4r9 » Thu, Oct 18, 2018, 10:36 AM UTC

another-cuppa wrote: post #364

mindcrime wrote: post #319

Earlier quoted context omitted.

This isn't a classroom, and your pedantry isn't adding anything useful to the conversation. We all understand these pedantic quibbles you're arguing about... and what the community is more or less collectively saying is "in this context, we don't care about the distinction between an 'algorithm' in the textbook sense, and a 'heuristic' in the textbook sense".

Nah. Most of them don't understand the difference. If you did you wouldn't can it pedantry. I personally don't find heuristics beautiful. That's why I commented.

To be fair, you haven't explained at all clearly why you don't think k-means adheres to Knuth's notion of an algorithm.

Your objection seems to be

> You can find pathological cases for k-means such that it will never converge on anything useful

As has been pointed out more than once, a good implementation of k-means is guaranteed to terminate in a finite time. And whatever you mean by "useful" doesn't seem to appear in Knuth's definition of an algorithm.

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

#463

Post by GautamGoel » Thu, Oct 18, 2018, 10:40 AM UTC

chaoxu wrote: post #432

GautamGoel wrote: post #101

Earlier quoted context omitted.

I actually read some of this paper! I liked your FFT trick.

Thanks! Do you use that algorithm for anything in your research?

Not directly. I briefly thought that a certain computational number theory problem might involve subset sums, but alas, it turned out to be the wrong approach.

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

#464

Post by jules » Thu, Oct 18, 2018, 11:35 AM UTC

wizeman wrote: post #456

karakot wrote: post #307

Earlier quoted context omitted.

and it's also a broken version.

Actually, I can definitely say that this version is not broken, i.e. I've formally proven it to be mathematically correct assuming that: 1. high and low are bigints (such as when using Python, for example) 2. the input array is sorted (needed for any binary search algorithm) 3. this missing code at the bottom is added: if (0 You can find the formal proof in WhyML below. This includes proofs that: 1. all array accesse…

Awesome! Interesting that it can prove that given only the loop invariant.

The inner loop could be factored to a subroutine with the following contract: let P be a predicate on the integers such that (i (P(i) => P(j)), and let low be such that P(low) = false and high such that P(high) = true. The subroutine returns i such that P(i) = false and P(i+1) = true. The subroutine further promises to only call P(k) on low This may be applied to the predicate P(k) = (x Is it possible to do this with WhyML?

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

#465

Post by karmakaze » Thu, Oct 18, 2018, 12:48 PM UTC

DarkWiiPlayer wrote: post #457

_pastel wrote: post #431

Earlier quoted context omitted.

I have a pet implementation of the frequency map that I'm overly fond of, for ascii strings: (1) keep an array of length 127 that you re-use and set to 0 between calls (2) for each character in the first string, increment the array at the character's index (3) for each character in the second string, decrement the array at the character's index If you end up with all 0s, it's an anagram.

Doesn't that mean in the end you have to check 127 values for if they are 0? Or 64, if you store numbers as 32-bit integers and compare them as 64-bit using a union type.

You could also keep a counter of the number of non-zero entries and update on zero/non-zero transitions.

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

#466

Post by alive2007 » Thu, Oct 18, 2018, 1:23 PM UTC

calciphus wrote: post #56

The Gale-Shapley Algorithm to solve the "Stable Marriage" problem. 2012 Nobel Prize in Economic Sciences for its wide-ranging use in medicine, education, and resource allocation. It's fairly easy to implement a basic version of it, feels intuitively obvious once explained, and has been applied to everything from organ transplants to student placement in elementary schools. Really, any place you have two groups where…

The real shocker is that it took until 2012 for this pivotal algorithm to win a Nobel Prize. David Gale had passed by then! The Nobel committee must be backlogged to Hell and back.

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

#467

Post by Doxin » Thu, Oct 18, 2018, 1:46 PM UTC

ishi wrote: post #164

Levenshtein distance, a dynamic programming algorithm for determining the edit distance between two sequences - the number of insertions, deletions or substitutions required to convert one sequence to the other. https://en.wikipedia.org/wiki/Levenshtein_distance

Interestingly enough Levenshtein can also be implemented as an A* variation iirc.

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

#468

Post by brlewis » Thu, Oct 18, 2018, 3:40 PM UTC

amelius wrote: post #326

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…

Nice in theory, but in practice you wouldn't implement it like that, especially if the words can be longer than your machine integer allows. Sorting and comparing is more elegant than invoking a BigNum library, imho (and has smaller footprint). This shows that theoretical elegance != implementation elegance.

One might also choose not to bring in a BigNum library if you don't need to find every anagram. Here's an exhaustive list of anagrams I found with sorting and comparing that a quick Fundamental Theorem implementation missed:

   [ 'basiparachromatin', 'Marsipobranchiata' ]
   [ 'configurationism', 'misconfiguration' ]
   [ 'constructionism', 'misconstruction' ]
   [ 'pericardiacophrenic', 'phrenicopericardiac' ]
   [ 'anatomicophysiologic', 'physiologicoanatomic' ]
   [ 'petrographically', 'pterylographical' ]

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

#469

Post by wizeman » Thu, Oct 18, 2018, 3:47 PM UTC

jules wrote: post #464

wizeman wrote: post #456

Earlier quoted context omitted.

Actually, I can definitely say that this version is not broken, i.e. I've formally proven it to be mathematically correct assuming that: 1. high and low are bigints (such as when using Python, for example) 2. the input array is sorted (needed for any binary search algorithm) 3. this missing code at the bottom is added: if (0 You can find the formal proof in WhyML below. This includes proofs that: 1. all array accesse…

Awesome! Interesting that it can prove that given only the loop invariant. The inner loop could be factored to a subroutine with the following contract: let P be a predicate on the integers such that (i (P(i) => P(j)), and let low be such that P(low) = false and high such that P(high) = true. The subroutine returns i such that P(i) = false and P(i+1) = true. The subroutine further promises to only call P(k) on low Th…

Actually, my loop invariant was unnecessarily confusing (I was sleep deprived), here's a better version: https://clbin.com/OhyJ3

Your question is very interesting and I think the answer is 'yes'. I will try to implement it and report back.

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

#470

Post by vram22 » Thu, Oct 18, 2018, 4:04 PM UTC

Mildly amusing anecdote:

I was on the panel for interviewing software engineer candidates at a large software company where I worked earlier. I asked one junior candidate (having a few years of experience) to tell me how she would solve the set cover problem [1].

I illustrated the problem with a concrete example: a project needing to fill roles with different tech skills; there is a pool of candidates, each of whom had one or more of those skills; and the goal is to find the minimum set (i.e. number) of candidates, the union of whose skills matches the total set of skills needed for the project. (Contrived problem, of course, since just having multiple skills might not mean a candidate would have the bandwidth to use all of them in the project.)

She started out by making up an example set of skills, an example pool of candidate names and their skills, thought for a bit, and then started describing how she would solve the problem.

I asked her to stop, and then, using an OOP analogy, said something like: You are giving a solution for an instance of the problem. Can you give me a solution for the class of the problem? :) That is, give a solution in generic terms, without using a specific input data set. Don't remember whether she could do that or not. But she was quite good at all the other areas tested on, and got the job.