Re:Ask HN: What's your favorite elegant/beautiful algorithm?
by 0-_-0 on Wednesday October 17, 2018 @06:01AM
(#18237627)
> Probably the most language agnostic algorithm
Are you sure about this point? I'd like to see a purely functional implementation of this, e.g. in Haskell without monoids. I believe it's significantly harder than a C implementation (which is indeed a few lines)
Re:Ask HN: What's your favorite elegant/beautiful algorithm?
by jaspervdj on Wednesday October 17, 2018 @08:14AM
(#18238192)
Not really, if you wanted to do a version using only immutable arrays:
import Data.Array
fw :: Int -> Array (Int, Int) Int -> Array (Int, Int) Int
fw 0 graph0 = graph0
fw k graph0 =
let fw' = fw (k - 1) graph0 in array (bounds graph0)
[ ((i, j), min (fw' ! (i, j)) ((fw' ! (i, k)) + (fw' ! (k, j))))
| (i, j) <- range (bounds graph0)
]
The only difference with a mutable implementation is that you use a new array for every k, whereas in a mutable version you would reuse these.
Re:Ask HN: What's your favorite elegant/beautiful algorithm?
by andrewflnr on Wednesday October 17, 2018 @08:23AM
(#18238240)
IIRC you can express it with matrix multiplication, but there might be some big caveats on that.
- Very non-trivial problem
- Just 5 lines of code
- Probably the most language agnostic algorithm
- Outrageously fast if graph fits in cache
- You can explain it to even non-programmers
- You can wear it on T-Shirt
- Doesn't require any fancy sub-algorithms, libraries or whatever