News for hackers. Stuff that matters.
Re:Is there an algorithm as beautiful as a poem? by 082349872349872 on Saturday June 15, 2024 @07:01AM (#40688950)
Poetry involves a specific choice of words (perhaps with some thought to metre or rhyme), so if anything, we should expect programs to be as beautiful as poem.

(would there then be algorithms as beautiful as an argument, or functions as beautiful as an idea?)

Re:Is there an algorithm as beautiful as a poem? by deadbabe on Sunday June 16, 2024 @12:25AM (#40694674)
Binary heap
Re:Is there an algorithm as beautiful as a poem? by labster on Sunday June 16, 2024 @12:30AM (#40694700)
Here, have some Perl poetry: https://en.wikipedia.org/wiki/Black_Perl
Re:Is there an algorithm as beautiful as a poem? by bostik on Sunday June 16, 2024 @04:02AM (#40695473)
I remember when Perl poetry was a thing. Mates in university combined it with code golfing, and came up with some pretty wacky results.

Being bad at both poetry and golf, I went with brevity instead:

    require clue;
Re:Is there an algorithm as beautiful as a poem? by adityaathalye on Sunday June 16, 2024 @02:33AM (#40695099)
Also the fact that 93% of paint splatters are valid Perl programs (2019) (mcmillen.dev) https://news.ycombinator.com/item?id=40197013

And riffing off poetry in prog langs, Dylan Beattie's Rockstar comes to mind: https://codewithrockstar.com/

Re:Is there an algorithm as beautiful as a poem? by 082349872349872 on Sunday June 16, 2024 @02:38AM (#40695118)
Difficult to mention Beattie without also mentioning his musical work, eg "Bug in the Javascript" https://www.youtube.com/watch?v=jxi0ETwDvws&list=PLw0jj21rhf...
Re:Is there an algorithm as beautiful as a poem? by adityaathalye on Sunday June 16, 2024 @02:49AM (#40695160)
Oh my, I haven't seen this one before... grinning like silly. I referenced his talk "The Art of Code" in my essay (I'm OP), a personal favourite.

Watching "Dylan Beattie's Tech Parodies" seems like a nice way to goof off this Sunday... brb.

Re:Is there an algorithm as beautiful as a poem? by 082349872349872 on Sunday June 16, 2024 @03:14AM (#40695254)
Cool, speaking of rock stars, "You Give REST a Bad Name" is a bit heavier; since you're OP, maybe the next one could be "Is there a program that rocks as hard as...?"

I still remember a particular moment in the early 1980s. I was working through K&R, and temperature conversion (§1.2) had been mid, but the RPN calculator (§4.3) was lit, and having typed it in, then figured out its principles of operation, I just knew I wanted to become a programmer.

  He heard one guitar, just blew him away
  He saw stars in his eyes, and the very next day *
From then on, I was destined for a life of Hex, Bugs, and Rock&Roll.

* https://www.youtube.com/watch?v=Ic02W1bWeFU

Re:Is there an algorithm as beautiful as a poem? by Turing_Machine on Sunday June 16, 2024 @12:40AM (#40694731)
The Fast Fourier Transform.
Re:Is there an algorithm as beautiful as a poem? by tucnak on Sunday June 16, 2024 @01:17AM (#40694851)
Tedious, inobvious, trickish. Might do it for some people, but not for me. Double for-loop substring search tells so much more! Oh, pain, oh, obscenity.
Re:Is there an algorithm as beautiful as a poem? by creaktive on Sunday June 16, 2024 @02:41AM (#40695132)
The real beauty lies in the SLOW discrete Fourier transform. Such simplicity; but what’s really going on there? Highly recommend grokking DST for the transcendental beauty.
Re:Is there an algorithm as beautiful as a poem? by __loam on Sunday June 16, 2024 @02:32AM (#40695094)
FFT probably prevented a nuclear war.
Re:Is there an algorithm as beautiful as a poem? by avmich on Sunday June 16, 2024 @01:27AM (#40694888)
http://archive.vector.org.uk/art10500390

...Roger Hui: In the year 2033 Earth was discovered by Survey Fleet MCXII of the Galactic Empire. The Emperor ordered Earth to send a representative to the court, with strict instructions to “bring something beautiful”.

Emperor

    What beautiful things does Earth have?
Earth Representative

    Your excellency, our...
Re:Is there an algorithm as beautiful as a poem? by avmich on Sunday June 16, 2024 @12:17PM (#40698130)
Server went down (?), so the full text here:

49. Bring Something Beautiful

+/(1+⍳∞)-s ←→ ×/÷1-(⍭⍳∞)-s

The following e-mail exchange took place on 2010-06-24 during a discussion on numeric representation.

Morten Kromberg: And… I shall fight against adding any form of NaN/Infinity — to the death! They will horribly complicate our implementation and don’t help users do anything useful.

Roger Hui: In the year 2033 Earth was discovered by Survey Fleet MCXII of the Galactic Empire. The Emperor ordered Earth to send a representative to the court, with strict instructions to “bring something beautiful”.

Emperor

  What beautiful things does Earth have?
 
Earth Representative

  Your excellency, our mathematician Euler proved in our year 1737 that +/(1+⍳∞)*-s ←→ ×/÷1-(⍭⍳∞)*-s
 
Emperor

  What is the ⍭ symbol?
 
Earth Rep.

  ⍭i is the i-th prime.
 
Emperor

  And what is ∞? Does it do anything useful?
 
Earth Rep.

  It denotes infinity, your excellency.
 
Emperor

  (ponders equation for a minute or two) Respect!
 
Emperor

  Neat notation you have there. Tell me more.
 
Earth Rep.

  Your excellency, it’s called APL. It was invented by the Canadian Kenneth E. Iverson …
Re:Is there an algorithm as beautiful as a poem? by bee_rider on Sunday June 16, 2024 @01:40AM (#40694930)
Well, I don’t think it is the point of the article, but we might as well list the most beautiful algorithms we can think of, right?

Mergesort is quite beautiful I think. There’s something beautiful in the simplicity of just merging the sorted lists. Stable. No pathological cases. Nice access patterns.

Re:Is there an algorithm as beautiful as a poem? by bjornsing on Sunday June 16, 2024 @04:17AM (#40695523)
Euclid’s algorithm [1] for finding the greatest common divisor of two numbers probably belongs on the list. As the name implies it was first described by Euclid, in 300 BC(!). It’s still widely used today.

1. https://en.m.wikipedia.org/wiki/Euclidean_algorithm

Re:Is there an algorithm as beautiful as a poem? by adastra22 on Sunday June 16, 2024 @02:06AM (#40695002)
Evolution by natural selection is the most beautiful algorithm imho.
Re:Is there an algorithm as beautiful as a poem? by dumpsterdiver on Sunday June 16, 2024 @02:53AM (#40695180)
I was looking for a word earlier that describes when it slowly dawns on a person how profound a thing is that’s been right in front of their eyes most of their life. The word I settled on was revelation, and one of the revelations I revisit as I grow older is the menacing terror presented by evolving lifeforms.

If you press the fast forward button as a theoretical “survivor in the game of life”, the creatures that were benign when they were static now become terrifying, constantly morphing organisms which gain and lose all manner of sharp and venomous appendages.

Like those early Deep Dream videos that always had creepy eyes and teeth everywhere on inanimate objects… that truly is what evolution looks like. It inspires instinctive fear of all the bad things, because that is exactly how it manifests.

When you release the fast forward button though and come back to the present, what was creepy and terrifying before suddenly becomes magnificent. A living representation of localized perfection.

Re:Is there an algorithm as beautiful as a poem? by adastra22 on Sunday June 16, 2024 @11:06AM (#40697608)
Only in niches that get locked in an evolutionary arms race, as does sometimes happen but is not the norm. There’s also prokaryotic life out there chilling and doing the same thing it’s been doing for billions of years.
Re:Is there an algorithm as beautiful as a poem? by tux3 on Sunday June 16, 2024 @03:30AM (#40695332)
We owe everything to it, and yet it is twisted and wrong.

Every day that passes, medicine weakens it. I thank medicine.

Re:Is there an algorithm as beautiful as a poem? by ajuc on Sunday June 16, 2024 @03:42AM (#40695377)
Medicine isn't weakening natural selection any more than birds' nests, bees' hives or beavers' dams are. It's all part of the optimized function.
Re:Is there an algorithm as beautiful as a poem? by 082349872349872 on Sunday June 16, 2024 @05:03AM (#40695694)
You can spot social Darwinists by hand-wringing that the "unfit" might paradoxically be outbreeding the "fit".
Re:Is there an algorithm as beautiful as a poem? by adastra22 on Sunday June 16, 2024 @11:06AM (#40697613)
What a succinct summary of the problem, thank you.
Re:Is there an algorithm as beautiful as a poem? by adastra22 on Sunday June 16, 2024 @11:04AM (#40697596)
Who invented medicine? The product of natural selection, that’s who.
Re:Is there an algorithm as beautiful as a poem? by m463 on Sunday June 16, 2024 @09:22PM (#40701504)
First, do no harm.

actually, it's interesting that not only does the oath not say that, but that doctors take all kinds of different oaths. They differ in all sorts of respects, and keep getting revised (like privacy policies).

https://en.wikipedia.org/wiki/Primum_non_nocere

https://en.wikipedia.org/wiki/Hippocratic_Oath#Modern_versio...

Re:Is there an algorithm as beautiful as a poem? by adastra22 on Monday June 17, 2024 @07:49PM (#40712569)
I don’t understand the relevance?
Re:Is there an algorithm as beautiful as a poem? by octopoc on Sunday June 16, 2024 @11:23AM (#40697733)
> and yet it is twisted and wrong

Have you seen the movie Idiocracy? IMO it's a way more likely dystopia than 1984 or Brave New World, and it's explained here[1]. I would argue that that future is twisted and wrong, and is partly enabled by (mis)use of medicine.

Now I do think that nature's approach, while extremely robust, does result in a lot of collateral damage--e.g. the fit don't always survive (most of us know people who died young due to no genetic conditions and due to no fault of their own), and the unfit don't have to die, they just need to not reproduce.

[1] https://www.youtube.com/watch?v=ZTMybQuRZ6E

Re:Is there an algorithm as beautiful as a poem? by 082349872349872 on Sunday June 16, 2024 @01:43AM (#40694944)
IIRC, Knuth said Tarjan's SCC had a certain beauty in that exactly when each node is visited, the relevant information has just been calculated.
Re:Is there an algorithm as beautiful as a poem? by zem on Sunday June 16, 2024 @05:23PM (#40700221)
the shunting yard algorithm is beautiful. I also love flood fill, especially with a nice visualisation.
Re:Is there an algorithm as beautiful as a poem? by rtheunissen on Sunday June 16, 2024 @07:07PM (#40700853)
I love the various top-down binary search tree partition/split/join algorithms.

https://github.com/rtheunissen/bst/blob/main/trees%2Fbalance...

Re:Is there an algorithm as beautiful as a poem? by andrewflnr on Sunday June 16, 2024 @01:41AM (#40694939)
Speaking of poems, algorithms, and trees: https://courses.cs.washington.edu/courses/cse461/14sp/lectur...
Re:Is there an algorithm as beautiful as a poem? by adityaathalye on Sunday June 16, 2024 @02:27AM (#40695075)
Feels like a riff on "Trees" by Joyce Kilmer https://www.poetryfoundation.org/poetrymagazine/poems/12744/...
Re:Is there an algorithm as beautiful as a poem? by 082349872349872 on Sunday June 16, 2024 @02:36AM (#40695110)
Re:Is there an algorithm as beautiful as a poem? by adityaathalye on Sunday June 16, 2024 @02:52AM (#40695171)
I find it hard to disagree

That only LISP Can Make a Tree

:D

Re:Is there an algorithm as beautiful as a poem? by MrVandemar on Sunday June 16, 2024 @01:42AM (#40694941)
I may be misremembering, but I saw a 'C' strcpy that looked concise and elegant, and seemed like a kind of poetry to me at the time.

    while(*s1++ = *s2++);
Re:Is there an algorithm as beautiful as a poem? by ajuc on Sunday June 16, 2024 @04:15AM (#40695515)
[delayed]
Re:Is there an algorithm as beautiful as a poem? by saghm on Sunday June 16, 2024 @03:20AM (#40695286)
It's certainly concise, but two post-evaluation assignments inside another assignment evaluated as a boolean condition feels more like the code equivalent of an Lovecraftian eldritch horror than a beautiful sunset.
Re:Is there an algorithm as beautiful as a poem? by proc0 on Sunday June 16, 2024 @02:01AM (#40694995)
Haskell (and some other pure FP langs) produces a lot of code that is basically technical poetry, at the cost of performance.

just look at the fib example:

>> fib = 1 : 1 : [a + b | (a, b) <- zip fib (tail fib)]

Re:Is there an algorithm as beautiful as a poem? by Sharlin on Sunday June 16, 2024 @03:28AM (#40695319)
Also the two-line "quicksort":

  qsort [] = []
  qsort pivot : xs = qsort [x <- xs, x < pivot] : pivot : qsort [x <- xs, x >= pivot]
Re:Is there an algorithm as beautiful as a poem? by tromp on Sunday June 16, 2024 @03:48AM (#40695402)
I prefer

    fib = f 0 1 where f a b = a : f b (a+b)
which needs neither zip nor tail.
Re:Is there an algorithm as beautiful as a poem? by fanf2 on Sunday June 16, 2024 @08:02AM (#40696427)
I like this paper on the sieve of Eratosthenes in Haskell https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf by Melissa O’Neill (of PCG fame)
Re:Is there an algorithm as beautiful as a poem? by 082349872349872 on Sunday June 16, 2024 @02:24AM (#40695059)
a moldy oldy (in the tradition of Dijkstra and Euclid):

  proc gcd(n,m): do n>m ⇒ n:=n-m ⫿ m>n ⇒ m:=m-n od; return max(n,m)
EDIT: note the different levels of abstraction: this is a program which implements a particular GCD algorithm, in a manner attempting to reflect the symmetry of the function which that algorithm calculates.
Re:Is there an algorithm as beautiful as a poem? by __loam on Sunday June 16, 2024 @02:31AM (#40695092)
FFT
Re:Is there an algorithm as beautiful as a poem? by creaktive on Sunday June 16, 2024 @02:39AM (#40695119)
Discrete Fourier Transform alone is transcendental, IMHO.
Re:Is there an algorithm as beautiful as a poem? by yazaddaruvala on Sunday June 16, 2024 @02:53AM (#40695174)
Im a huge fan of iterative Quickselect and also iterative dfs.

I find especially all their slight variations to be quite poetic.

Re:Is there an algorithm as beautiful as a poem? by remoquete on Sunday June 16, 2024 @02:54AM (#40695185)
Especially when you're coding poems using english-lang: https://github.com/theletterf/english-lang
Re:Is there an algorithm as beautiful as a poem? by FartyMcFarter on Sunday June 16, 2024 @03:07AM (#40695227)
Minimax search. Such a simple algorithm, but it perfectly solves chess and similar games.
Re:Is there an algorithm as beautiful as a poem? by tromp on Sunday June 16, 2024 @03:58AM (#40695445)
Alpha beta search solves games more efficiently...
Re:Is there an algorithm as beautiful as a poem? by FartyMcFarter on Thursday June 20, 2024 @05:47AM (#40736781)
I was referring to the beauty of the algorithm, not efficiency.
Re:Is there an algorithm as beautiful as a poem? by JohnKemeny on Sunday June 16, 2024 @03:38AM (#40695356)
λx.(λx.f(xx))(λx.f(xx))
Re:Is there an algorithm as beautiful as a poem? by tromp on Sunday June 16, 2024 @03:52AM (#40695422)
That ignores its first argument x.

You mean the fixpoint combinator λf.(λx.f(x x))(λx.f(x x)), or λf.(λx.x x)(λx.f(x x)), or as a lambda diagram:

    ────┬────
    ┬─┬ ┼─┬─┬
    └─┤ │ ├─┘
      │ ├─┘  
      └─┘
Re:Is there an algorithm as beautiful as a poem? by tromp on Sunday June 16, 2024 @06:32AM (#40696017)
I would say the combinator \x\y\z.x z (y (\t.z)) is more poetic than Y, since it forms a basis for combinatory logic all by itself. Not only can you make Y from it, but every other combinator as well. And it's the smallest term with that property.
Re:Is there an algorithm as beautiful as a poem? by Simon_ORourke on Sunday June 16, 2024 @03:42AM (#40695375)
It depends, are you talking about W.B. Years here, or some bozo from a hip-hop outfit not going three words without saying b*ch?
Re:Is there an algorithm as beautiful as a poem? by defrost on Sunday June 16, 2024 @03:47AM (#40695397)
> you talking about W.B. Years here

Oh Simon, we're talking both Yeats as in doesn't rhyme with Keats and the Sleaford Mods et al.

You might need an IRL friend to school you on the good bars.

addendum: Humphrey B. Flaubert covers W.B.'40' Years https://www.youtube.com/watch?v=oGxDVXGRQpY

Re:Is there an algorithm as beautiful as a poem? by 082349872349872 on Sunday June 16, 2024 @04:38AM (#40695611)
Some bozo from a hip-hop outfit not going three words without cutting glass: https://www.youtube.com/watch?v=mG2zN9xuGVw

(it's the XXI, you can type bitch now, but note that apart from a notable hapax, Mr B prefers to refer to ladies)

Re:Is there an algorithm as beautiful as a poem? by ajuc on Sunday June 16, 2024 @04:04AM (#40695482)
Algorithms can certainly be elegant. A greedy algorithm with a lot of special cases added to force it to work feels yucky. A simple algorithm that does the minimal amount of work to get the job done and handles all the special cases without case-specific code feels good. Like a well-crafted, reliable tool. It might not be beauty yet, but it's close.

What makes it beautifull in my mind is the same thing that makes some poems beautifull - the fact that it seems simpler than the problem it solves, and yet it solves it well. If it evokes that surprising feeling of "That's it? That's enough?" - then it's beautifull, like a poem which expresses complex feeling in a few short verses.

For me Floyd-Warshall is one example.

Re:Is there an algorithm as beautiful as a poem? by tromp on Sunday June 16, 2024 @05:31AM (#40695812)
There's a universal algorithm

    (λ 1 1) (λ (λλλ 1 (λ 1 (λ 4 (λλλ 3 1 (2 (λ 2)))) (4 (λ 5 (λ 5 (2 1)))))) (1 1)) (λ 1)
(in de-Bruijn notation) which, given a list of input bits, parses the encoding of an arbitrary algorithm (as a combinator over the minimal single point basis λxλyλz.x z (y (λt.z))) from this bit stream, and runs that algorithm on the remaining input.
Re:Is there an algorithm as beautiful as a poem? by _nalply on Sunday June 16, 2024 @09:23AM (#40696877)
For me, tree traversal is beautiful.

    traverse(node):
      if node:
        [ 
          ...traverse(node.left), 
          ...traverse(node.right), 
          node.value,
        ]
The pseudo-code recursively produces a list of the node values in post-order.
Re:Is there an algorithm as beautiful as a poem? by amomchilov on Sunday June 16, 2024 @12:03PM (#40698018)
Huffman encoding
Re:Is there an algorithm as beautiful as a poem? by gumby on Sunday June 16, 2024 @01:07PM (#40698530)
The author even quoted Sussman but neglected to include Guy Steele’s version:

I think that I shall never see

A matrix lovely as a tree.

Trees are fifty times as fun

As structures a la PL/I

(Which Dijkstra claims are too baroque).

And SNOBOL's strings just can't compare

With all the leaves a tree may bear,

And COMIT strings are just a joke.

Vectors, tuples too, are nice,

But haven't the impressive Hair

Of trees to which a LISP is heir.

A LISPer's life is paradise!

Many people think that JOSS

And others, too, are strictly boss;

And there are many BASIC fans

Who think their favorite language spans

All that would a user please.

Compared to LISP they're all a loss,

For none of them gives all the ease

With which a LISP builds moby trees.

RPG is just a nurd

(As you no doubt have often heard);

The record layouts are absurd,

And numbers packed in decimal form

Will never fit a base-two word

Without a veritable storm

Of gross conversions fro and to

With them arithmetic to do.

And one must allocate the field

Correct arithmetic to yield

And decimal places represent

Truncation loss to circumvent:

Thus RPG is second-rate.

In LISP one needn't allocate

(That boon alone is heaven-sent!)

The scheme is sheer simplicity:

A number's just another tree.

When numbers threaten overflow

LISP makes the number tree to grow,

Extending its significance

With classic tree-like elegance.

A LISP can generate reports,

Create a file, do chains and sorts;

But one thing you will never see

Is moby trees in RPG.

One thing the average language lacks

Is programmed use of push-down stacks.

But LISP provides this feature free:

A stack — you guessed it — is a tree.

An empty stack is simply NIL.

In order, then, the stack to fill

A CONS will push things on the top;

To empty it, a CDR will

Behave exactly like a pop,

A simple CAR will get you back

The last thing you pushed on the stack;

An empty stack's detectable

By testing with the function NULL,

Thus even should a LISPer lose

With PROGs and GOs, RETURNs and DOs,

He need his mind not overtax

To implement recursive hacks:

He'll utilize this clever ruse

Of using trees as moby stacks.

Some claim this method is too slow

Because it uses CONS so much

And thus requires the GC touch;

It has one big advantage, though:

You needn't fear for overflow.

Since LISP allows its trees to grow,

Stacks can to any limits go.

COBOL input is a shame:

The implementors play a game

That no two versions are the same.

And rocky is the FORTRAN road

One's alpha input to decode:

The FORMAT statement is to blame,

But on the user falls the load.

And FOCAL input's just a farce-

But all LISP input comes pre-parsed!

(The input reader gets its fame

By getting storage for each node

From lists of free words scattered sparse.

Its parses all the input strings

With aid of mystic mutterings;

From dots and strange parentheses,

From zeros, sevens, A's and Z's,

Constructs, with magic reckonings,

The pointers needed for its trees.

It builds the trees with complex code

With rubout processing bestowed;

When typing errors do forebode

The rubout makes recovery tame,

And losers then will oft exclaim

Their sanity to LISP is owed —

To help these losers is LISP's aim.)

The flow-control of APL

And OS data sets as well

Are best described as tortured hell.

For LISPers everything's a breeze;

They neatly output all their trees

With format-free parentheses

And see their program logic best

By how their lovely parens nest.

While others are by GOs possessed,

And WHILE-DO, CASE, and all the rest,

The LISPing hackers will prefer

With COND their programs to invest

And let their functions all recur

When searching trees in maddened quest.

Expanding records of fixed size

Will quickly programs paralyze.

Though ISAM claims to be so wise

In allocating overflow,

Its data handling is too slow

And finding it takes many tries.

But any fool can plainly see

Inherent flexibility

In data structured as a tree.

Re:Is there an algorithm as beautiful as a poem? by adityaathalye on Monday June 17, 2024 @06:38AM (#40704181)
I confess to ignorance, not neglect :)
Re:Is there an algorithm as beautiful as a poem? by qazxcvbnm on Sunday June 16, 2024 @01:10PM (#40698552)
On trees - how could we neglect the Succinct trees?

Succinctness - expressing trees with as little bits as entropically possible. The representation is as simple as it could be - simply write down nested parentheses whose abstract syntax tree is your given tree. Practically all tree operations in logarithmic or constant time. How it works - recursively with range-min trees and range-max trees - simple and elegant number theory.

A primer - https://arxiv.org/pdf/0905.0768