Here’s a real life puzzle that I haven’t solved yet; but nor have I put much time into it yet. It was originally a problem related to randomised podcast playlists, but I have disguised it as a problem with lollies (candy) for no particular reason.
So, I opened a packet of wine gums, sorted them into piles by colour and counted the pile sizes. There were 3 x raspberry, 3 x lemon, 6 x orange and 2 x lime (I threw the black licorice ones straight in the bin. Ugh!)
I started eating them in that order, but I found I got bored of raspberry flavour very quickly. To maximise my pleasure, I wanted to consume them in the order that maximises the distance between eating two of the same flavour.
So I started eating one from each pile, rotating around the piles. It started out great, and I was happy with my simple algorithm, until I had consumed most of the lollies, and had nothing but orange ones left. Boring! My naive algorithm was suboptimal; it just took me a while to notice – it worked well enough when the pile sizes were roughly the same size, but when one pile is much bigger then the others, it fell over.
So what selection algorithm will maximise my wine-gum consuming pleasure, no matter what the flavour distribution?
My thoughts so far involve drawing a set of parallel horizontal line segments, one for each flavour, spreading each pile of wine gum equally across its corresponding line segment, and consuming them left-to-right, top-to-bottom. (Wait, wait! Do I mean top-to-bottom, left-to-right? The one that keeps skipping to the other horizontal lines, prioritising left-ness over top-ness.)
It sounds like a reasonable solution, but I haven’t tried to prove it is optimal yet.