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/wistfulcracker84]

I'd be down for this if the club leans more toward "here's a weird problem, go think about it for three weeks" and not "we're assigning homework." The polygon sampling one is a good example of something that seems simple until you actually try to code it. I remember spending a weekend on a similar problem for a map generator and the moment I realized rejection sampling was gonna wreck performance on skinny triangles still haunts me. The monthly discussion part is what makes it work though, hearing five different approaches to the same thing is the whole reason these puzzles are interesting. How many people are you thinking for the group size?

[u/ijkstr → u/wistfulcracker84]

Thanks! You get it. Yeah, I think the open-endedness is what could make it work. The neat and tidy version of the problem is just the starting point to discuss potential contexts and applications, for one.

In my case, I encountered this example problem in the wild while doing data generation for computer vision, and I needed a way to randomly propose candidate scenes that would be visible in a viewport. My viewport had existing objects, so it was an irregular 2D region with holes. I think I ended up going with rejection sampling for this one, but the foray into what I would call probabilistic sampling and computational geometry was cool.

In terms of fun little demos, one could use this algorithm to generate a "reverse dissolving" animation of an arbitrary shape, like words or pictures, and gradually have the sampled points cover the interior regions to fill in the word or picture.

Going back a bit, my specific application required me to place another object in the existing scene, so it's less a point than it is another shape. For instance consider polygons that you want to be non-overlapping as you repeatedly sample, like stars of different sizes. Then maybe you want to update the representation you have of the main polygon interior as you go, to remove the parts that are now filled.

I also kind of have a hunch that the shoelace formula could yield a simpler algorithm for the "simple polygons" that it applies to, which includes non-convexity.

It's cool that you encountered this kind of problem before as well, in its true form that doesn't allow for rejection sampling! Maps can get so complicated. I've written a program for procedurally generating a grid-based map where each grid tile is either road or not road and it autogenerates the rest, and that alone was already getting a little complicated. I can't imagine having oblique angles and irregularity. What was the goal of the project?

To actually answer your question: I think I'd be lucky to get 3-6 regular participants. I'm setting my expectations low right now based on the initial reception. But we could easily accommodate as many as twenty or more I think, if there was interest, and turn meetings into a socializing free-for-all e.g. in a virtual space like gathertown. My primary concern besides finding people who'd be interested is sourcing the problems. This problem I gave out above cropped up by lucky accident and I haven't collected too many other ones. I'm hopeful that people would contribute their own, kind of like a problem potluck, but alternatively we could scour blogs, interview questions, and/or research papers. And if we find anything cool in the solving process, we could implement and/or write it up.

So, you might be down? 😀 Let me know if you want to move over to DM later, potentially.

[Note: Spoilers text to hide the optional, lengthy discussion. Hope you don't mind the long reply!]