All,
I need a clever way to implement this algorithm (for work) as quickly and cleanly as possible: I think I've removed all the language specific issues and boiled it down to this:
I have two arrays: A and B.
A has a list of names in it {Apple, Apple, Banana, Banana, Banana, Carrot, ...} each i-th value has no upper limit on the number of times it can appear in A. There can be just one "Apple" or a zillion.
Each entry in A has a matching entry in B. (many to many mapping). For example:
A[0] = "Apple" B[0] = "0027"
A[1] = "Apple" B[1] = "0028"
A[2] = "Banana" B[2] = "0073"
A[3] = "Banana" B[3] = "0041"
A[4] = "Banana" B[4] = "0069"
If there are 100 or fewer instances of an entry in A, (if there are <= 100 Bananas) then they must all share the same initial "B" value. If there are more than 100, then the first 100 must share the same B values, but the next 100 will have the B[i + 100] th value.
Example if there are 102 apples
A[0] = "Apple" B[0] = "0027"
A[1] = "Apple" B[1] = "0028"
...
A[99] = "Apple" B[99] = "0073"
A[100] = "Apple" B[100] = "0041"
A[101] = "Apple" B[101] = "0069"
A[102] = "Banana" B[102] = "0123"
Then the result that I want is this:
A[0] = "Apple" B[0] = "0027"
A[1] = "Apple" B[1] = "0027"
...
A[99] = "Apple" B[99] = "0027"
A[100] = "Apple" B[100] = "0041"
A[101] = "Apple" B[101] = "0041"
A[102] = "Banana" B[102] = "0123"
I'm sure there are some super brains out there that can come up with the crappy algorithm I've devised, so let's see it!
Edit: Guess I should point out that this was for work. I thought this was a fun challenge that someone might want to look at and possibly come up with a better solution than the one I came up with.
Edit: thanks to daniel for pointing out my dumb mistakes.
My solution just for comparison:
(pseudo code)
first make a hash/dictionary of B, called d where d[ "Apple" ] = number of instances of Apple in A.
while (i < A.count)
{
string cmp = A[i];
int v = d[cmp];
int j=i;
while (v--) {
B[j++] = B[i];
if (j %100 == 0)
i += j
}
i+= d[cmp];
}
doing this from memory, hope I didn't screw up an indexes...