Have you seen any code that you think came from "The Book"?

Chat / Discussions
1

If you’re not familiar with this fun bit of math lore,

Paul Erdős, the famously eccentric, peripatetic and prolific 20th-century mathematician, was fond of the idea that God has a celestial volume containing the perfect proof of every mathematical theorem. “This one is from The Book,” he would declare when he wanted to bestow his highest praise on a beautiful proof.

Have you come across any Elixir code that you think could’ve come from our version of “The Book”?

6 Likes
2

I’ll nominate the following way to generate all permutations:

def permutations([]), do: [[]]
def permutations(list), do: for x <- list, rest <- permutations(list -- [x]), do: [x | rest]

I expected it to be so much more complicated than it was!

5 Likes
3

Quick sort comes to mind. It’s beautiful. Bisecting stuff just feels like magic; an universal algorithm to look for problems and zero in on them.

6 Likes
4

One-dimensional line intersection. It’s one of those things that sounds simple and has a solution that looks simple, but actually coming up with the solution is less obvious.

I actually got to use this one in database code not too long ago to intersect key ranges, so it’s not only for graphics!

def intersects?({a1, a2}, {b1, b2}) do
  a2 >= b1 and b2 >= a1
end

Incidentally I messed around with game engine/physics engine stuff a while ago and I was absolutely traumatized to learn that basically all 2D (and 3D) graphics stuff looks like this. I don’t know what I was actually expecting but somehow I thought there would be a more elegant solution for collision detection than “check if every single point is on the other side of every single line” and so on. But there isn’t!

We’re lucky computers are so fast.

2 Likes
5

It’s one of those things that sounds simple and has a solution that looks simple, but actually coming up with the solution is less obvious.

Yes! This is actually 100% analogous to a problem that I deal with frequently at work: do two time ranges overlap? So our codebase is littered with this kind of check.

This is also (partially) why I wrote CompareChain. This kind of bounds checking is so much more annoying when you can’t use the infix structural operators like >=.

While I’m at it, have you come across the Allen's interval algebra - Wikipedia? It’s a generalization of the Law of trichotomy - Wikipedia to 1D intervals. In interval-land, two intervals fall into one of 13 specific cases (or 26 if you allow 0-width intervals) instead of just 3. This isn’t from The Book per se, but the number 13 always struck me as surprising for some reason.

3 Likes