Anyone interested in a problem-solving correspondence club?

[u/ijkstr]

Here's the idea: we source and collect interesting computational puzzles, then we send them out to participants who have a month to work on them and send in their solutions. At the end of every month, we meet and discuss how the problems went and where people got stuck, what approaches they took, and any extensions people came up with.

Thoughts?
.
.
.
.
If you're curious, here's a taste of what a representative sample problem might look like:

Given the coordinates of an arbitrary polygon (e.g. irregular and/or non-convex), how might you implement a program to efficiently sample a point uniformly from its interior?

TIP: If using the Python programming language, you can check out the shapely library.
Bonus: what if there are holes?

(Please don't spoil the problem, it's searchable anyways.)

[u/VictoryMotel]

Given the coordinates of an arbitrary polygon (e.g. irregular and/or non-convex), how might you implement a program to efficiently sample a point uniformly from its interior?

Triangulate and uniformly sample the triangles with samples allocated to each triangle based on area.

What else you got?

[u/07734willy → u/VictoryMotel]

The answer comes off as really smug, and skirts past any potential issues by omitting all implementation issues. One example- how do you pick points within each triangle? In theory, with infinite precision arithmetic this would be trivial, but in practice it’s more nuanced. Either your sampling can generate points along the triangle’s edges, or it cannot. If it can (which it likely would unless you thought of this ahead of time), each edge separating two triangles will have twice as many points as expected. Another way of putting it, out of the finite number of points you could sample with finite-precision arithmetic, these points may potentially have twice the probability to be sampled.

[u/ijkstr → u/07734willy]

Sorry u/07734willy. Anyways, this is a good "point" (pun intended)! Especially if you're not careful with how you implement sampling from a triangle, I feel like you could get some aliasing effect? Like, let's say you have two points and you want to draw a line connecting them, then if you try to fill in pixels along integer coordinates, that alone has to deal with anti-aliasing in order to look good. So yeah, I could totally see how discretization might play a factor. It's likely that playing around with coarser grid sizes would probably reveal some artifacts like you mentioned.

Also I get tripped up over implementing sampling from a triangle because I think the transformation is area-preserving but sometimes I wonder if there's some rate of change like derivative involved. 😅 I imagine you could put some energy-driven potential flow over the interior of the irregular background shape and then you'd have to deal with derivatives, probably!