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

Post by [deleted] » Wed, Oct 17, 2018, 5:01 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.

Post by Sharlin » Wed, Oct 17, 2018, 5:03 PM UTC

jjnoakes wrote: post #283

rodovich wrote: post #227

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…

This is cool. I never actually realized that magic squares exhausted all of the sums to 15; in other words, there is no triplet which sums to 15 and is not already a row, column, or diagonal. No false positives, so to speak. I wonder if this is true of larger magic squares.

  from collections import Counter
  from itertools import combinations

  def number_of_sums(n, M):
    combs = combinations(range(1,n**2+1), n)
    sums = (sum(c) for c in combs)
    return Counter(sums)[M]

  print(number_of_sums(3, 15))
  print(number_of_sums(4, 34))

Post by neoncontrails » Wed, Oct 17, 2018, 5:08 PM UTC

rodovich wrote: post #227

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…

Post by nimonian » Wed, Oct 17, 2018, 5:08 PM UTC

xrd wrote: post #332

Sieve of Eratosthenes, visualized here: http://xrd.github.io/angular-algorithms/web/index.html#/algo... Spelling eratosthenes is harder than this elegant little algorithm.

Post by nimonian » Wed, Oct 17, 2018, 5:13 PM UTC

toomuchtodo wrote: post #323

sizzzzlerz wrote: post #321

The FFT algorithm is perhaps the most elegant and useful work of the 20th century. Modern communications would probably not be possible with out it but it's utility isn't limited to electronics It is used across the list of scientific disciplines and even in finance and economics. Next time you make a call on your smart phone, hoist a beer to Cooley, Tukey, and Carl Gauss

It's also critical for factoring prime numbers and SETI signal intelligence processing. Truly a gem.