Ask HN: What is the most beautiful piece of code you've ever read? • Hacker News Board

Re: Ask HN: What is the most beautiful piece of code you've ever read?

#131

Post by ivalm » Mon, Oct 28, 2019, 6:50 AM UTC

kccqzy wrote: post #90

nwallin wrote: post #82

Earlier quoted context omitted.

Quick sort comes with a steep penalty. Worst case is O(n^(2)). The reason quicksort is good is because it's in place. Once you throw away the in place aspect of quick sort, it's straight up bad. This implementation of quicksort is actually a great example of why functional programming sucks. It silently transforms an O(1) space algorithm into an O(n) space one, and adds an enormous constant time overhead. Algorithms…

> It silently transforms an O(1) space algorithm into an O(n) space one, and adds an enormous constant time overhead. Please tell me what imperative quicksort algorithm has O(1) space. All versions I've seen and could recall use recursion; although each recursive call uses O(1) space, in the worst case of bad pivot element selection each recursive call would only really sort one element resulting in a worst-case O(n)…

For non recursive quicksorts see code at bottom of this link: https://www.geeksforgeeks.org/iterative-quick-sort/

Re: Ask HN: What is the most beautiful piece of code you've ever read?

#132

Post by flukus » Mon, Oct 28, 2019, 6:50 AM UTC

known wrote: post #122

awk '!seen[$0]++' awk 'NR==FNR{A[$0]; next} $0 in A' file1.txt file2.txt

Thanks, was trying to remember that first trick just last week. For log files I had to make a slight adjustment to filter the time at the front:

  !seen[gensub($1, "", "g", $0)]++

For anyone wondering, it filters out duplicates by storing the first occurrence of the line and skipping subsequent ones.

Re: Ask HN: What is the most beautiful piece of code you've ever read?

#133

Post by fulafel » Mon, Oct 28, 2019, 6:55 AM UTC

ridiculous_fish wrote: post #103

switz wrote: post #24

The one that blew my mind when I was in college was a simplified version of quicksort in Haskell. It's just so elegant and clean. quicksort :: Ord a => [a] -> [a] quicksort [] = [] quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater) where lesser = filter ( = p) xs Now surely someone may come along and point out how this isn't a true quicksort[0] because it doesn't partition the elements in place, but…

Unfortunately it's also incorrect! It discards NaNs, as they are neither =.

I would argue that this is better than most alternatives.

Re: Ask HN: What is the most beautiful piece of code you've ever read?

#134

Post by endymi0n » Mon, Oct 28, 2019, 6:56 AM UTC

Considering the magnitude of its impact on science, engineering and culture (as well as the tremendous force released), this line from the IGNITION subroutine in the BURN_BABY_BURN module of the Apollo AGG source code does it for me:

https://github.com/chrislgarry/Apollo-11/blob/master/Luminar...

Re: Ask HN: What is the most beautiful piece of code you've ever read?

#135

Post by maweki » Mon, Oct 28, 2019, 7:02 AM UTC

ridiculous_fish wrote: post #103

switz wrote: post #24

The one that blew my mind when I was in college was a simplified version of quicksort in Haskell. It's just so elegant and clean. quicksort :: Ord a => [a] -> [a] quicksort [] = [] quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater) where lesser = filter ( = p) xs Now surely someone may come along and point out how this isn't a true quicksort[0] because it doesn't partition the elements in place, but…

Unfortunately it's also incorrect! It discards NaNs, as they are neither =.

In the example there was no talking about floating point numbers. The ordered type _has_ a total ordering as shown by the Ord typeclass restriction.

Re: Ask HN: What is the most beautiful piece of code you've ever read?

#136

Post by Const-me » Mon, Oct 28, 2019, 7:04 AM UTC

scrollaway wrote: post #77

symplee wrote: post #56

Earlier quoted context omitted.

What is the probability that it prints a completable[0] maze? Expressed in terms of line width (w) and number of lines (n). [0] Where there's a valid path from the first line to the last.

1/2^n, I believe (where n is the number of lines after the first one, otherwise 1/2^n+1). So halved every time: 100% with 1 line, 50% with 2 lines, 25% with 3 lines, and so on. Width is irrelevant (you can do this in your head comparing w=1 n=2 to w=2 n=2 for example). Edited for clarity and accuracy.

One line, not completable:

    /\/\/\/\

Also, I don't believe it doesn't depend on width. I think with constant height, the probability of completable one should increase with width, and become almost 1 for very large widths.

Re: Ask HN: What is the most beautiful piece of code you've ever read?

#137

Post by p4bl0 » Mon, Oct 28, 2019, 7:06 AM UTC

Gregory Chaitin discusses elegance of programs in his book The limits of mathematics, which is a very good read. I wrote a review almost ten years ago here: https://p4bl0.net/shebang/the-limits-of-mathematics.html

Re: Ask HN: What is the most beautiful piece of code you've ever read?

#138

Post by saagarjha » Mon, Oct 28, 2019, 7:09 AM UTC

jjnoakes wrote: post #110

jancsika wrote: post #83

Earlier quoted context omitted.

I've got a better code snippet: your exact same code snippet but for a language which will short circuit based on the lvalue of the assignment expression. Then t would never be able to overflow s (nor even eat its null terminator)

The size of the buffer pointed to by s may be larger than the current string it holds. It may also be uninitialized.

Or point to the wrong thing, or point to unmapped memory, or be const, or…there's a lot of things that can go wrong with this function.

Re: Ask HN: What is the most beautiful piece of code you've ever read?

#139

Post by scrollaway » Mon, Oct 28, 2019, 7:13 AM UTC

Const-me wrote: post #136

scrollaway wrote: post #77

Earlier quoted context omitted.

1/2^n, I believe (where n is the number of lines after the first one, otherwise 1/2^n+1). So halved every time: 100% with 1 line, 50% with 2 lines, 25% with 3 lines, and so on. Width is irrelevant (you can do this in your head comparing w=1 n=2 to w=2 n=2 for example). Edited for clarity and accuracy.

One line, not completable: /\/\/\/\ Also, I don't believe it doesn't depend on width. I think with constant height, the probability of completable one should increase with width, and become almost 1 for very large widths.

Hm, good points, looks like I need more sleep. Looking at the video again, a path is valid if two slashes follow each other, with the same pattern shifted by 1 the line below.

But I wasn't treating /\ as an invalid on the first line. Eg thinking of:

    /\/\/\/\
    \\//////
    /\\\\\\\ … and so on

(Using the /\ pattern, paths can go back up and come back down, so this requires a lot more thought than I instinctively put into it)

Re: Ask HN: What is the most beautiful piece of code you've ever read?

#140

Post by kccqzy » Mon, Oct 28, 2019, 7:15 AM UTC

ivalm wrote: post #131

kccqzy wrote: post #90

Earlier quoted context omitted.

> It silently transforms an O(1) space algorithm into an O(n) space one, and adds an enormous constant time overhead. Please tell me what imperative quicksort algorithm has O(1) space. All versions I've seen and could recall use recursion; although each recursive call uses O(1) space, in the worst case of bad pivot element selection each recursive call would only really sort one element resulting in a worst-case O(n)…

For non recursive quicksorts see code at bottom of this link: https://www.geeksforgeeks.org/iterative-quick-sort/

That link basically just simulates recursion by defining a stack in the function. It recognizes that in the recursive version among the stack variables only the two indexes need to be stored so it stores them. It is even less space efficient than the recursive version because it always allocates O(n) space.