Originally Posted by
Ben17 Hi there,
I've been challenged to find an algorithm that evenly (or as evenly as possible) spreads varying difficulty between varying number of rounds for a hypothetical Quiz game. So you could have:
Maximum difficulty = 4 (always between 1 and x)
Number of rounds = 8
I can then evenly distribute the difficulty across the number of rounds like so:
round 1: 1
round 2: 1
round 3: 2
round 4: 2
round 5: 3
round 6: 3
round 7: 4
round 8: 4
This is fine when the number of rounds is a multiple of the maximum difficulty, but I can't get my head around how to do this when it's not:
Maximum difficulty = 5
Number of rounds = 8
round 1: 1
round 2: 1
round 3: 2
round 4: 3
round 5: 3
round 6: 4
round 7: 5
round 8: 5
This is the result I am looking for when the maximum difficulty is not a multiple of the number of rounds. I can't work out how to process the numbers so there is an even difficulty at each end of the scale where possible (in this example it works out by having only one 2 and one 4 - they are in the same position at each end).
If anyone could help me out I would greatly appreciate it.
Thanks for your time,
-Ben
Hi Ben,
The trick on distribution problems like this is to proceed in a stepwise fashion--in your case, one round at a time-- and maintain two variables: (1) the amount of (whatever) that you have actually distributed thus far ("ndone" below), and (2) the amount that you would like to have distributed if you could distribute non-integer amounts ("goal") below. The difference between ndone and goal gives you how much you would like to distribute at the next step. Since the amount must be integer, you must somehow convert to an integer, which can be done is several ways-- round up, round down, or round to nearest integer are all possibilities.
If all this is too vague to follow, here is a concrete realization of an algorithm in C. What we are "distributing" in this case is the omitted rounds; for example, when you have 8 rounds and 5 levels of difficulty, you wish you could have 10 rounds (easy), but you must omit 2. The number of omitted rounds is called "nshort".
The code does not give exactly what you asked for: in the example case it results in rounds of difficulty 1, 1, 2, 3, 3, 4, 4, 5. (The notion of distributing "as evenly as possible" is not well-defined.) But maybe it will give you ideas.
Code:
void distribute(int nrounds, int maxdiff)
{
int q, nshort, ndone, round, diff, delta, i;
float goal;
q = (nrounds + maxdiff -1) / maxdiff; /* note integer division */
nshort = q * maxdiff - nrounds;
ndone = 0;
round = 0;
diff = 0;
while (round < nrounds) {
diff = diff + 1;
for (i = 1; i <= q; i = i+1) {
/* note floating point division on next line: */
goal = ((float)(round+1) / nrounds) * nshort;
delta = goal - ndone; /* note truncation to integer here */
ndone = ndone + delta;
if (delta < 1) {
round = round + 1;
printf("round %d: %d\n", round, diff);
}
}
}
}