Huffman Encoding.
Ask HN: What's your favorite elegant/beautiful algorithm?
361–370 of 507 posts
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#362The first time I implemented the backtracking algorithm it felt really special. I was struggling to solve 8 queen problems for a couple of nights, banging my head around it. And then when it worked, I knew my love for programming was not going anywhere any time soon. It was ugly, I had used 8 for loops, each running for 8 iterations, but, I still felt awesome when it worked. Before this, I had written only lab progra…
> I know it's just one form of brute force algorithm, maybe doesn't even count as one, and is not that elegant, but, it will always remain my favorite.
Backtracking is really a depth-first search over the search tree, so it's definitely an algorithm and I would say it's "elegant" in some sense (like simplicity).
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#363Rock, Scissors, Paper in a circular array.
All you have to do to test for win condition is check if the other player has the next item in the array.
Equality is a tie.
Base case is a loss.
It's also my favorite case of structuring data in a way that makes the algorithm self-evident.
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#364Earlier quoted context omitted.
It's one of the most fundamental concepts in computer science and underpins decades of research. You can decide if it's useful.
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.
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#365Earlier quoted context omitted.
Check out https://github.com/tomprimozic/type-systems there's been a few HN threads about it as well. I can also answer any specific questions you have, or if you want further resources I can try and find them... (there's a good online book I have in mind, but I've no idea how to find it right now!)
Have you read TAPL? I'm curious how you think that stacks up to readily-available online resources.
No, I've just skimmed over some of its chapters to clarify some concepts. I've mostly learned by reading code and then trying to implement my own type systems. Algorithm W is really quite simple and basic.
Another good resource could be Programming Language Zoo http://plzoo.andrej.com/ that covers different evaluation techniques as well.
In general, I've been "involved" in PL design for quite some time, so I've no idea where I've gained all the knowledge I have... but in recent years, there have been quite a few modern resources, even a few on HN IIRC!
e.g.
http://craftinginterpreters.com/
http://createyourproglang.com/
(disclaimer: I haven't read them)
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#366Earlier quoted context omitted.
I like this version: low = -1 high = arr.length while(high - low > 1){ mid = (high + low)/2 if(arr[mid] This eliminates all branches from the body of the loop (gets compiled to conditional move). It's also more general because it can be used to find the right position to insert a new element in a sorted array.
and it's also a broken version.
How so? Are you talking about (high + low)/2? Whether that is correct depends on the language. With 64 bit arithmetic it's correct in practice, and with arbitrary size arithmetic it's correct in practice and in theory. It only really causes problems if you're using 32 bit arithmetic on a 64 bit machine.
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#367I'm by no means a Haskell evangelist, but I believe it's a great educational tool for devs. You've made a Fibonacci number algorithm. Recursive it's slow, iterative it's nasty. There's another way > let fib = 0 : 1 : zipWith (+) fib (tail fib) Then to get the 10kth Fibonacci number you can > fib !! 10000 It's fast. It's tiny. It has no risk of stack overflow because it's not a recursive function. It illustrates how a…
Or the even more succinct fibs = 0 : scanl (+) 1 fibs scanl is similar to a fold, but returns a list of successive reduced values from the left.
That's fantastic!
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#368The Euclidean algorithm to compute the greatest common divisor of two numbers. In Javascript, if you have two numbers x and y that are both greater than zero, you compute the greatest common divisor xyGcd in one beautiful line of code: var xyGcd = function gcd(a,b){ return b ? gcd(b, a%b) : a; }(x, y); In my opinion this is the greatest one-liner ever.
Isn't it a-b instead of a%b?
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#369Earlier quoted context omitted.
...wait, how? I’ve never heard of a use like this.
If f is monotonic and continuous, you can solve f(x) = y for x by successively narrowing an interval [a, b] where f(a) <= y <= f(b) (or vice versa for decreasing functions). In the case that the range of f spans the entire real numbers, the initial range can be determined as the smallest range [-2^k, 2^k] where k is an integer (a strategy often used for open-ended binary search).
Interestingly, with floats you can also binary search on the binary representation. That narrows down the answer to the most precise answer representable in floating point in at most 64 steps for 64 bit floats. If you bisect the interval in the middle at each step, then it could take more steps (possibly more than 1000).
It turns out that doing this is pretty much equivalent to what you suggest, if you narrow down the initial range [-2^k, 2^k] by binary searching on k, because that's just binary searching on the exponent in the binary representation.
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#370The Gilbert-Johnson-Keerthi convex shape intersection algorithm. It can take any two convex sets and tell you if they overlap, while converging on a separating axis or a penetration point, if it exists. All you need is a support function that returns a point in the set that is furthest along a given direction vector. The algorithm works in an arbitrary number of dimensions. Basically, it operates on a new shape which…
Wow. I'm surprised to see this on here. I used to work Johnson, he's is a super nice guy and always made time to have long conversations with me about optimization.
I believe this algorithm is widely used in the video game industry?