Diogo Peralta Cordeiro

SoulMate Roulette

· competitive programming, problem setting, hausdorff distance, CC3036, university of porto

For Competitive Programming (CC3036) at the University of Porto I got to write a few problems, and this one — SoulMate Roulette — is my favourite.

It started from Randall Munroe's ninth What If? post, where he works out that if everyone really had a single soul mate somewhere in the world, the odds of ever bumping into them would be hopeless. The premise of the problem runs with that, tongue firmly in cheek: society decides to brute-force romance by photographing everyone's eyes, and asks you — a competent computer scientist — to write the program that scores how likely any two people are to be soul mates. Every time a camera fills up you receive its memory card, each holding 1337 eyes stored as 42×42 BMP edge images stitched back to back.

Underneath the silliness it's a clean all-pairs similarity problem. You parse the raw BMPs (each is exactly 398 bytes, so you don't even need the magic bytes to find where one photo ends and the next begins), measure how alike two eye shapes are with the Hausdorff distance, and output every pairing sorted by likelihood — breaking ties by input order, because of course people are born with two eyes. And, since government data is government data, some of the photos turn out to be of closed eyelids: on invalid input you bail out and print a few lines of Tim Minchin instead of a result.

That is the kind of problem I most enjoy setting: a daft premise wrapped around a genuine algorithmic core, with a sneaky amount of careful byte-level I/O hiding in the corners.

The full statement, a reference solution, an input generator and example I/O are all here:

There's now a companion problem in the same place — Notas Emoji — which I finally got around to finishing: a grade sheet accidentally run through an emoji encoder that you have to decode back to plain text in C.