Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Project Euler Discussion
New Posts  All Forums:Forum Nav:

Project Euler Discussion - Page 2

post #11 of 15
Quote:
Originally Posted by hajile View Post

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.
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.

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.

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
Death Star
(21 items)
 
Darksaber
(11 items)
 
 
CPUMotherboardGraphicsRAM
Athlon II x2 245 Asus M3A78 Radeon HD6570 1GB Mushkin Silverline 2GB DDR2  
Hard DriveOptical DriveOSMonitor
OCZ Vertex 2 120GB Samsung Blu-Ray Windows 7 Samsung 46" DLP 
PowerCaseOther
Silverstone Strider Essentials 400W Silverstone Milo ML03B Hauppage WinTV 1250 
  hide details  
Reply
Death Star
(21 items)
 
Darksaber
(11 items)
 
 
CPUMotherboardGraphicsRAM
Athlon II x2 245 Asus M3A78 Radeon HD6570 1GB Mushkin Silverline 2GB DDR2  
Hard DriveOptical DriveOSMonitor
OCZ Vertex 2 120GB Samsung Blu-Ray Windows 7 Samsung 46" DLP 
PowerCaseOther
Silverstone Strider Essentials 400W Silverstone Milo ML03B Hauppage WinTV 1250 
  hide details  
Reply
post #12 of 15
Quote:
Originally Posted by wedge View Post


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.
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 sequence. 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.

I wouldn't express it recursively; it will break. The way to solve it recursively is to start with the last ball (N). N goes on the stack and forces the solution of (N-1) which forces the solution of (N-2) and so on until you get to ball ( 0 ) and start returning functions. Since this isn't tail recursion, the memory requirements for large sets will overflow the stack.

post #13 of 15
Quote:
Originally Posted by hajile View Post

The way to solve it recursively is to start with the last ball (N). N goes on the stack and forces the solution of (N-1) which forces the solution of (N-2) and so on until you get to ball ( 0 ) and start returning functions. Since this isn't tail recursion, the memory requirements for large sets will overflow the stack.

I don't think so. That's not how I'm doing it. I'm not making any individual calculations on each ball like that. I'm calculating each group as a whole. So the maximum theoretical value for N in the recursive stack will be 64, same as the max value for T. That would happen if one group had the max value of 64, and it was followed by nothing but single gaps. The sequence would look like this:
64,1,x,1,y,1,z,1,....
Edited by wedge - 5/23/13 at 8:06am
Death Star
(21 items)
 
Darksaber
(11 items)
 
 
CPUMotherboardGraphicsRAM
Athlon II x2 245 Asus M3A78 Radeon HD6570 1GB Mushkin Silverline 2GB DDR2  
Hard DriveOptical DriveOSMonitor
OCZ Vertex 2 120GB Samsung Blu-Ray Windows 7 Samsung 46" DLP 
PowerCaseOther
Silverstone Strider Essentials 400W Silverstone Milo ML03B Hauppage WinTV 1250 
  hide details  
Reply
Death Star
(21 items)
 
Darksaber
(11 items)
 
 
CPUMotherboardGraphicsRAM
Athlon II x2 245 Asus M3A78 Radeon HD6570 1GB Mushkin Silverline 2GB DDR2  
Hard DriveOptical DriveOSMonitor
OCZ Vertex 2 120GB Samsung Blu-Ray Windows 7 Samsung 46" DLP 
PowerCaseOther
Silverstone Strider Essentials 400W Silverstone Milo ML03B Hauppage WinTV 1250 
  hide details  
Reply
post #14 of 15
Oh, and one other observation I had, is that the final state no matter what the starting sequence is, will always be sorted from smallest to largest. Sometimes when working through the cycles, the same numbers will be reached, but out of order. Continue running cycles and they will sort themselves out.
This makes perfect sense, simply because the larger the group is, the 'faster' it will be moving. So it will eventually overtake any/all smaller 'slower' groups ahead of it.
Death Star
(21 items)
 
Darksaber
(11 items)
 
 
CPUMotherboardGraphicsRAM
Athlon II x2 245 Asus M3A78 Radeon HD6570 1GB Mushkin Silverline 2GB DDR2  
Hard DriveOptical DriveOSMonitor
OCZ Vertex 2 120GB Samsung Blu-Ray Windows 7 Samsung 46" DLP 
PowerCaseOther
Silverstone Strider Essentials 400W Silverstone Milo ML03B Hauppage WinTV 1250 
  hide details  
Reply
Death Star
(21 items)
 
Darksaber
(11 items)
 
 
CPUMotherboardGraphicsRAM
Athlon II x2 245 Asus M3A78 Radeon HD6570 1GB Mushkin Silverline 2GB DDR2  
Hard DriveOptical DriveOSMonitor
OCZ Vertex 2 120GB Samsung Blu-Ray Windows 7 Samsung 46" DLP 
PowerCaseOther
Silverstone Strider Essentials 400W Silverstone Milo ML03B Hauppage WinTV 1250 
  hide details  
Reply
post #15 of 15
Thread Starter 
Working on problem 12 today:
Quote:
Originally Posted by http://projecteuler.net/problem=12 
The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

Obviously a 'brute force' solution here is not ideal. I'm going to try to implement a sort of stepping brute force, basically count up in intervals >1 until it finds a number with >500 divisors, then start counting back one by one until the first is found. There must be an easier way to go about this, but I have not figured that out yet.
New Posts  All Forums:Forum Nav:
  Return Home
  Back to Forum: Coding and Programming
Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Project Euler Discussion