Quote:

That is the point at which it has reached the 'final state' and the size of the groups will no longer change. Determining if we have reached the final state is easy, the hard part is reaching it.Originally Posted by

At this point, the first, second, and third groups become independent of each other (in this specific case). As a result, for each cycle, the group with one dot will move one space, the group with 2 dots will move 2 spaces, and the last group with 3 dots will move 3 spaces.

**hajile**At this point, the first, second, and third groups become independent of each other (in this specific case). As a result, for each cycle, the group with one dot will move one space, the group with 2 dots will move 2 spaces, and the last group with 3 dots will move 3 spaces.

Quote:

@wedge

Keep in mind that you don't need very much variation in array size. If you have N dots, then the maximum array size (assuming space, ball, space, ball, ... ball, space) would be (2*N + 1). Since empty spaces before the first ball are not being used, nor are spaces after, the actual formula is (2*n - 1). In this case, six balls means that the maximum size is 11. All you need to do is keep track of the numbers in each array spot so if you had [3,3,2,4,1], the next cycle would be [3,2,2,3,1] and the size of the array would not change.

Keep in mind that you don't need very much variation in array size. If you have N dots, then the maximum array size (assuming space, ball, space, ball, ... ball, space) would be (2*N + 1). Since empty spaces before the first ball are not being used, nor are spaces after, the actual formula is (2*n - 1). In this case, six balls means that the maximum size is 11. All you need to do is keep track of the numbers in each array spot so if you had [3,3,2,4,1], the next cycle would be [3,2,2,3,1] and the size of the array would not change.

I've made several realizations yesterday. First, that it is a waste of time to try to simulate the box system directly. That method is actually rather easy, that's what I did in my first attempt, and it works very nicely for small sequences. But it's completely inefficient for large sequences, which is what we need. I let it run for half an hour and it didn't even finish a single cycle. So the only way to do this well is to calculate the effect of each complete cycle on the sequence itself. Which is what you're describing above. This way we are working with a much smaller array, which does not change in size, and we are only dealing with small numbers. Making this method more efficient before we even start it.

Using the t1...t10 example they give, and using the working simulator I created, I mapped out in excel what each of the completed cycles look like, and there are obvious patterns of course. But I had to look at it that way to see them. That gave me the insight I need to write a function that calculates the next completed sequence using nothing but the current sequence. What I wrote works, but only for the first cycle or two then it breaks down. The reason it breaks down, is because the groups interact with each other, and the more cycles that run, the more interaction there will be.

The conclusion I've come to, is that I need to write a recursive function (something I suspected from the very beginning) to solve this one. I could continue to extend the new algorithm I have, but it would have to be extended to a queue depth of 64 (the maximum value of t). It would be much less work to just do it properly.

Something else I noticed when working with a few examples, is that the result of the first cycle is constant. After cycle 1, all numbers simply shift over. The first group gets discarded, and the last group becomes the difference of the sum of the groups in the new sequence and the total sum that there is supposed to be. The last group then remains constant for the entire life of the program. This trend may break down with larger sequences, but I haven't seen that happen yet, so for now I've got the first cycle hardcoded. All other cycles are calculated, except for the last number which I just carry forward.

This is a snip of my quasi-working code, up to a queue depth of 4. Forgive the mess, it's a work in progress.

You can see the pattern in the code. Once I figure out exactly how to solve it recursively, it will be greatly simplified and should work for all cases.

**Warning: Spoiler!**(Click to show)

Code:

```
int sum = 0;
int i = 0;
while (i <= t.Length)
{
if (i % 2 == 0)
sum += t[i];
i++;
}
for (int k = 0; k < size; k++)
{
nextLine[k] = t[k + 1];
}
i = 0;
int newSum = 0;
while (i <= nextLine.Length)
{
if (i % 2 == 0)
newSum += nextLine[i];
i++;
}
nextLine[size] = sum - newSum;
///
for (int r = 0; r < 10; r++)
{
////
t = nextLine.ToArray();
t[size] = sum - newSum;
Array.Clear(nextLine, 0, nextLine.Length);
////
int j = 0;
while (j <= size - 1)
{
if (j % 2 == 0)
if (t[j] >= t[j + 1])
{
nextLine[j] = t[j + 1];
}
else
{
nextLine[j] = t[j];
}
else
{
if (t[j - 1] >= t[j])
{
if (j + 2 >= t.Length)
{
}
else
{
if (t[j - 1] > t[j] + t[j + 2])
{
nextLine[j] = t[j + 1];
nextLine[j + 1] = t[j + 2];
nextLine[j + 2] = t[j + 3];
nextLine[j + 3] = t[j - 1] - t[j] + t[j + 1] - t[j + 2] + t[j + 3];
j += 3;
}
else
{
if (t[j - 1] + t[j + 1] > t[j] + t[j + 2])
{
nextLine[j] = t[j + 1];
nextLine[j + 1] = t[j + 2];
nextLine[j + 2] = t[j + 3];
nextLine[j + 3] = t[j - 1] + t[j + 1] + t[j + 3] - t[j] - t[j + 2];
j += 3;
}
else
{
nextLine[j] = t[j + 1];
nextLine[j + 1] = t[j - 1] - t[j] + t[j + 1];
nextLine[j + 2] = (t[j + 2] - nextLine[j + 1]) + t[j + 3];
j += 2;
}
}
}
}
else
{
nextLine[j] = t[j] - t[j - 1] + t[j + 1];
}
}
j++;
}
}
t = nextLine.ToArray();
t[size] = sum - newSum;
Console.Out.WriteLine(finalCalc(t));
```

Edit: Also of interest, I've tested the performance of this code up to t10000000, it gives the wrong answer of course. But it does run very fast. It completed 10 cycles in a few seconds.

Edited by wedge - 5/23/13 at 7:25am