OddThinking

That one is trivial: you just use Bresenham’s algorithm.

Ok, I’ll bite. How?

[For the Google-challenged: Bresenham’s algorithm is a used for calculating how to draw straight lines (and in advanced versions, curved lines) on a bitmap grid.]

When you say wine-gums above, I assume you mean a jelly baby or gummi bear equivalent (having never seen anything called wine-gums in my travels, but then I might just not have seen the label).

Once you’ve constructed your grid, rather than top to bottom, left to right, you could just go with a long chain, rather like a snake. After all, snakes are tastier than jelly babies.

However, when it comes to music, I’d be as worried about hearing too many saccharine sweet songs in a row as I would be about hearing them interspersed with metal or the cure/radiohead (although now I’m morbidly curious what this might sound like – “Groove is in the Heart” back to back with “Creep”. *shudder*). Frankly, wide ranging musical tastes makes shuffle play an instrument of torture.

Julian:

Divide the number of items in each pile by the number of items in the smallest pile. For each pile, take as many items as the integer part of the ratio is, and keep an error counter where you accumulate the fractional part of the ratio. Whenever the error counter crosses an integer boundary you take an extra item.

Say the ratio turns out to be 2.7 for one of the piles. Since you can’t take 2.7 gums, you take 2 gums and add 0.7 to the error counter on the first pass. On the second, you take 2 gums, add 0.7 to the error counter for a total of 1.4, so you take a third gum and decrease the error counter by one to 0.4. Then you take 2+1 on the third pass (error: 0.1), 2 on the fourth (error: 0.8), 2+1 on the fifth (error: 0.5), 2+1 on the sixth (error: 0.2), etc.

Richard,

having never seen anything called wine-gums in my travels

Drats! I originally was going to say Fruit Pastilles, but I was afraid they might not be widely known, so I changed to to, what I thought, was a more generic confectionery that everyone would know: Wine Gums!

I would have chosen Jelly Babies, but I have never been able to distinguish more than three flavours in jelly babies (black=licorice, purple=blackcurrant, and red/yellow/orange/green=citrus) so I don’t much care what order I eat them once the black ones have been thrown away.

After all, snakes are tastier than jelly babies.

Agreed, it is metaphorically better, but it actually invalidates the algorithm. If the same number of two flavours is present, it snaking doesn’t maximise the distance between them. You have to go to the top and start again.

Your point about the applicability of this optimised-shuffle on an mp3 player to wide-ranging music tastes is well taken.

Aristotle,

Thank you for explaining and putting me out of my misery! I’ve been lying awake in bed, imagining grids of wine-gums flavours, and lines curling through them, trying to minimise errors.

I think I understand what you are describing. I don’t think that algorithm is optimal, and I blame myself.

Bresenham is optimising the run-length of colours to spread them evenly over a limited number of colour-changes. However, in this puzzle there is no limit on the number of colour-changes. I’ll demonstrate with an example of 6 x Red, 6 x Orange and 2 x Yellow. Bresenham’s will give us: R-R-R-O-O-O-Y-R-R-R-O-O-O-Y. That’s a lot of boring runs of Red (and of Orange) in a row.

One better solution would be: R-O-R-O-Y-R-O-R-O-Y-R-O-R-O. Is that the optimal solution? I don’t know. I don’t know whether it is better than, for example, Y-R-O-R-O-R-O-R-O-R-O-R-O-Y.

The reason I don’t know, and the reason I blame myself for leading you astray with Bresenham’s, is that, in the original problem, I failed to define sufficiently what the property is that we are trying to maximise. Sorry.

I am still working on that definition. (I was thinking that it involves products of distances between instances per colour.) Until I/we can define that, I don’t think we can prove any solution to be optimal.

I think I have now defined the metric I want to optimise.

Given that I have no decent maths rendering system easily available, I will show it in Pythonesque pseudocode.

result = 1
for pile in colourPiles:
	for item in range(1,len(pile)): # Skips the first item in the pile - at position 0

		# itemDistance is (a count of the number of items distance between 
		# two items of the same colour) + 1
		itemDistance = pile[item].position - pile[item-1].position
		result = result * itemDistance

I am, of course, open to counter-suggestions that you think better match the original wine gum problem.

Let’s see how it works:

R-O-R-O-Y-R-O-R-O-Y-R-O-R-O = 72 * 72 * 5 = 25920
Y-R-O-R-O-R-O-R-O-R-O-R-O-Y = 32 * 32 * 13 = 13312

That’s good, because the original algorithm for a solution would have produced the former.

But wait up:

R-O-Y-R-O-R-O-R-O-R-O-Y-R-O = 72 * 72 * 9 = 46656

My original algorithm is sub-optimal. 🙁 The search continues.

Let’s do this directly. What you want is to not get bored of a colour. Let’s give each colour an interestingness. When you eat anything of a particular colour, it’s interestingness goes down. How far down? Well, the more of a particular colour you’ve had recently, the less interesting a colour becomes. why not just take the sum of the reciprocal of the offsets of the colours you’ve eaten. eg:

Take: RYOYR. (you’ve already eaten these, from left to right).

To figure out the interestingness of yellow, you do a 1 – (1/3 + 1/5) because you had a yellow lolly 3 & 5 lollies ago including the one you’re about to eat.

You can change the scaling in case you don’t get bored of lollies quickly, or if you get bored really quick but can remember being bored of a colour for a long time. You can even change scaling for individual lolly colours, in case you have a million orange and one black, it may even mean you want to eat the black one eventually.

So the steps are:
1) pick the maximum interestingness
2) enjoy
3) destroy teeth.

Let me get a few things straight…

The “problem” was originally with randomised podcast playlists, but you “disguised” it as a problem with lollies, for “no particular reason”.

Upon opening the packet/playlist, you sorted the lollies/authors and immediately disposed of the “black” ones.

I think the real issue here is your (only thinly disguised) racism.

I’m also concerned about your search for a system that allows for the total exclusion of some ethnic groups (in what way I am unsure, but it sounds very sinister), while dispersing others as much as possible. All this among rumours that you are planning to run for the position of President of Australia/orchestrating some sort of coup d’état.

Cassie,

You have opened my eyes, thank you.

As careful reading of those links will show, my political advisers will not permit me to comment on my plans. However, rest assured that I will be adding the eradication of racism in confectionery to my campaign.

I had no idea until now that I was being fooled by a conspiracy of candy makers. Like many other children, I was being trained to make decisions with subconscious racial overtones – all achieved through the simple mechanism of infiltrating the supply of yummy jelly babies with disgusting ones, dyed black.

I note that it is not just the blacks being conspired against. Native Americans and Hispanics are having their traditional cultures lampooned and attacked by the manufacturers of an inedible parody.

I hope to make bold new steps against this conspiracy, just as soon as I have solved this algorithmic puzzle (oh, and Australia becomes a republic.)

Sunny,

I am still pondering the change in metric: from products of distances to sums of reciprocals of distances. I’ll sit down later and try to find an example where it would make a difference to the optimal order, and see which looks more right.

I believe that the first wine gum that you eat should be from the biggest pile. However, your basic algorithm (eat the colour with the lowest metric) does not guarantee that.

Consider the fairly degenerate case of one Yellow and two Orange. This algorithm will have a fifty-fifty chance of generating Y-O-O, which is sub-optimal compared to O-Y-O.

You spoke about a modification that would give an initial scaling for the million orange to one black case – that might help solve this problem. Would you care to elaborate how that might would work?

If you had to use all the gums, I would propose the following:

1. Take the biggest pile, and sort them randomly.
2. Take the next biggest pile, and distribute evenly throughout the bigger pile.
3. Proceed like this until all gums have been added.

Jumping back to a playlist, this gets trickier if you want a limited number of items, or a time limit on the playlist. To keep songs fresh, I propose stamping each song (directly or in a separate database) with the last played time, and not playlisting those within a day or two of the last play time, if possible.

Windows Media Player has a frustratingly predictable pseudo random routine, that seems to love some songs, and never play others. The time stamp would almost certainly help here.

Bork,

I have already given this approach some thought.

Note that, with wine gums, there is no need to “sort them randomly” in step 1, because they are indistinguishable.

In step 2, the best way to distribute them evenly is to use Bresenham’s algorithm, that Aristotle introduced before.

In step 3, you are effectively making the assumption that all of the colours that have been merged into a line so far, are to be treated the same from now on.

I got quite excited by this idea; it is simple and breaks down the complexity well, but there was something missing.

Imagine your colours are 3 x Red, 1 x Orange and 1 x Yellow.

Step i: RRR

Step ii: Combine RRR and O, with Bresenham’s. Either RORR or RROR. Both are equally correct – let’s just assume we choose the former.

Step iii: Treat the RORR line as a single colour: e.g. xxxx. Combine xxxx with Y, with Bresenham’s. The result should be xxYxx.

Unfortunately, the result of this algorithm is ROYRR, which isn’t as good as RORYR.

I am not touching the Random Number Generator comment; the human brain is notoriously hungry to find patterns when presented with randomness, so proving an application isn’t random takes quite a bit of evidence.

Just because I haven’t posted on this subject for over a month, doesn’t mean it hasn’t been bugging me continuously for most of that month. I have been giving this puzzle a lot of thought, and I am starting to fear that it is NP-complete or something.

I have never worked out how to prove a problem is NP-complete. Is it enough to simply declare that because I can’t find a polynomial-time solution, it must be non-polynomial?

In the last 24 hours, I actually managed to put this puzzle behind me, but only because I have been tackling the practice puzzles in the CISRA Puzzle Competition (via Anotherblog) I was in the lead of ranking table for a few hours! I was the first and second submitter of correct answers! Now, I have started to fall behind and I am staring uselessly at one of the puzzles at the moment.

A property of NP-complete problems is that they can all be restated in terms of one another. NP-completeness is therefore usually proven by showing that a particular problem is exactly equivalent to some other known NP-complete problem. Another property of NP-complete problems is that a proposed solution to a particular instance of the problem can be readily verified in polynomial time. See this nice page of lecture notes on class NP problems for more detail.

(For a very fun read on the subject and a bunch of related ones, check out Dominus’ “You Can’t Get There From Here” talk.)

Hi Julian.

I don’t know if I am misinterpreting you when you say “In the last 24 hours, I actually managed to put this puzzle behind me”, in thinking that you are no longer interested in solving this. If this is the case, I apologise for adding more thoughts on it 🙂 Seriously, if you are done with this one, I’ll no longer post thoughts on it, but it has got my interest now, and it’s like a song that I can’t get out of my head!!

Also, forgive me if I constantly mix metaphors, I’ll try and keep the analogy separate from the implementation, but I make no guarantees.

Anyway, I have had a couple of flashes of lightning in my brain over this one.

I think it is easier to think about optimal distribution if you imagine the final result as a circle, or permanently repeating playlist, which you can tune into or out of at any point. I imagine a wire circle with coloured beads, with a “switch” that allows extra beads to be added to the circle.

Imagine the scenario of two reds to one yellow: If you look at these three in a line, R-Y-R looks different to R-R-Y, but on a circle that endlessly repeats, both have the identical result, namely two reds next to each other, and a yellow. The point at which you “tune in” to this ever repeating channel determines whether you will hear the two “red” artists one after the other or not. In this case it is impossible to optimise colour randomness any further without another yellow or alternate colour.

This flash in my brain also gave me a solution to optimising for shorter time periods, where you are playing a subset of your total library – namely, the only way to get the same optimal distribution is to populate all the beads onto the circle, as if you want to play the entire library, and then grab a subset of that which fits the required time.

Now I haven’t pushed my formula all the way to a guaranteed infallible solution, but thinking of it this way may help:

1. Add all the beads onto the circle from the pile with the most beads, and if there is a tie, pick any one. That’s right, I’ve totally hijacked your gums analogy.

2. Since the circle is all one colour, it doesn’t matter where you start adding the next colour. Starting anywhere, evenly distribute the next biggest colour.

If there was a tie, you now have perfect alternating colours. More likely, you will have runs of the same colour.

3. From the third colour on, start at this step and repeat until all colours are exhausted.

4. Calculate the number of beads you need to skip each time to distribute this colour evenly through the remainder.

5. Find the longest continuous run of colour possible. Calculate the max number of beads you can place into this run, maintaining the proper distribution. If it is just one, find the middle of the run, add a bead in there, and distribute evenly from there. If it is more than one, try to maximise the number of “splits” you can perform to the run, then distribute evenly. E.g. if you can get 2 beads into the run, try to position them so you have 3 splits in the run, with the end two being equal length.

As far as I can imagine, this is the best possible way to distribute the different colours so you get maximum distance between ALL artists.

At first I thought of finding all the runs, and trying to split them all for each colour, but this would end up with some artists being close to each other on occasions, then long gaps between them in others.

Caveats:

I just noticed that point 5 above is really open to misinterpretation. I said “find the longest continuous run of colour possible”. What I should have said is “find the longest continuous run of a colour”. Any colour. It may have implied trying to calculate the largest possible run length, when really I only meant search the circle and find the longest run of any particular colour on the circle.

Hope this is clear.