Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

news.ycombinator.com

Post reply on HN
Print view View original

281–290 of 507 posts

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

#281

Post by mattyw »

tomp wrote: post #201
mattyw wrote: post #158

Earlier quoted context omitted.

I like implementing type systems Could you expand on this? This is something I've just started reading about. I'd be interested in good resources to use to get started. At the moment I've just started reading TAPL.

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!)

Some great stuff in this repo thanks. I'm particularly interested in resources that build a type system up step by step, from very simple and working towards Hindley-Milner

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

#283

Post by jjnoakes »

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.

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

#284

Post by yboris »

jhallenworld wrote: post #274
yboris wrote: post #273

A better voting algorithm for a better democracy: allow more than one vote per person. This eliminates numerous problems with today's one-vote-per-person. It's simple (no voter confusion) and results in better outcomes. https://80000hours.org/podcast/episodes/aaron-hamlin-voting-...

No you should get just one vote, but dole out any number of fractions of it to whomever you wish as long as the total is 1. If only the general population understood fractions :-)

The whole point of the alternative I link to is that it's simple. If you like the Democrats _and_ the Green Party, you can now vote for both. This prevents the Green Party from "stealing" Democratic votes.

Because of our the current poorly-designed system, we have an artificially low number of votes for non-Democrat and non-Republican parties.

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

#285

Post by bradstewart »

0n34n7 wrote: post #58

Kalman Filter - Smoothed out all the outliers on a location tracking project I worked on - https://en.m.wikipedia.org/wiki/Kalman_filter

This. Kalman filters have proved to be very good at finding a signal in noise. A-GPS is one of the most common use cases, but I've used it in forecasting and HVAC control among others.

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

#287

Post by tomp »

mattyw wrote: post #281
tomp wrote: post #201

Earlier 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!)

Some great stuff in this repo thanks. I'm particularly interested in resources that build a type system up step by step, from very simple and working towards Hindley-Milner

Hm... I'm not sure it works that way. Type systems are quite fragile beasts, if you change one thing you can easily break the rest. Especially when it comes to type inference! Although I'd say that HM is quite simple, especially if you don't consider polymorphism (i.e. if you require that every function parameter has a concrete type like int or bool).

In fact, that might be a good starting point - first implement something with the above 2 types, and where every variable and function parameter has a type annotation. From then, you could (1) add more complex types, like function types, tuples or lists, (2) implement type propagation where each variable has the type of the value it's assigned (like auto in modern C++), and then (3) go full HM type inference.

TAPL definitely sounds like a good resource. The next book might be this one: Advanced Topics in Types and Programming Languages https://www.cis.upenn.edu/~bcpierce/attapl/frontmatter.pdf

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

#289

Post by Const-me »

geoah wrote: post #29

Fast inverse square root, sometimes referred to as Fast InvSqrt() or by the hexadecimal constant 0x5F3759DF, is an algorithm that estimates 1/√x, the reciprocal (or multiplicative inverse) of the square root of a 32-bit floating-point number x in IEEE 754 floating-point format. https://en.m.wikipedia.org/wiki/Fast_inverse_square_root I especially love the story around it.

It’s nice but it’s deprecated, we now have hardware support for that in CPUs.

PC: https://software.intel.com/sites/landingpage/IntrinsicsGuide...

ARM: http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc....

Post reply on HN