Project Euler

AceInfinity · Dec 30, 2012

tom982 said:
If I've worked it out correctly, then the X directly to the right of the point of explosion on your diagram is 40.77471948m away, and the X where the fragments would touch the floor is 87.41807227m away from your centre line. I don't know if it helps though, as the path of the projectile is curved so the volume can't be calculated with any simple calculations, it's going to be some hideously complicated differential equation followed by a lovely bit of integration, and the bottom party is the easy bit

I'll ask my differential equations lecturer about this when I go back to uni, there's got to be an equation to use for this :)

Yeah, I just don't know what the equation would be to calculate that kind of volume, If you did though, you would have to probably end up adding the volume from where it hits the 100m mark for any pieces that fly with an initial velocity helping the fragments move higher from that point after the blast, and then You would have to probably add the Cylinder's volume that gets created from the point where it falls down from the farthest reach at 100m above ground. But for momentum that carries pieces farther than that displacement the last 100m.... I honestly don't know.

I'm assuming that you would need to find the velocity in the horizontal vector for any pieces that keep moving away from the centerpoint of the blast for the last 100m of the fall. Which would be Vmax, and I can get all that, but I don't know anything for volume. I know 2D, not 3D.

Here's my belief though. In theory, i'd assume this is how you would end up getting the result though:

(Image brought to you by Photoshop :thumbsup2:)

Laxer said:
It begs the question to use the Euler method with a really small step size... :lolg: Imagine that

I will pass... lol I'm a programmer not a rocket scientist.

These were fun while I didn't require a mathematician to solve them anyways :)

Laxer · Dec 30, 2012

You were the one who introduced differential calculus into the equation :lolg:

I was just giving an easy way to integrate without taking the derivative by finding the area under the curve in steps... :banghead:

On a mathematical note... The path of the projectiles will be parabolic(you're image shows a semi-circle although you probably already knew this)

if you let the point where the firecracker exploads be the value x=0 and be y=100(m) you will have the path split in half by the y-axis, you could then treat this as a rotated solid around the y axis and solve for the volume...

Been >4 years since I have gone down this road... so might be wise finding someone with more recent math knowledge.

There are many methods to do this, I always preferred shells over disks but this should give you the basic idea

With the example above you could just do the integral from 0 -> x-range instead of going -x-range->x-range and removing the extra...

If you would like I can probably solve it, however I wouldn't touch any programming languages and just do it on paper...

Was thinking about this and the answer above is only partially right, I left out a critical are of the volume... Anything were the projectiles would be launched between 0 and 180 degs (up) wouldn't be covered... You would have to through in variable into it thus making it more of a programming question :banghead:

Latest thought on the approach... Treat everything firstly as if they are launched parallel or lower to the ground thus the volume would be just one parabola rotated around the y axis...

Then take this a tweak the equation to allow different launch angles for anything greater than 0 and less than 180 (0-pi in rad) and throw this into the computer remembering to subtract the first equation so we don't count it a million times... :banghead:

I'm on winter break I don't want to think anymore :sleep2:

tom982 · Dec 30, 2012

lol, I think I'll pass on that one!

Laxer · Dec 30, 2012

If you think about it aces image above is really only a fraction of the answer because they projectiles could be launched say straight up or...

I think the final shape will be somewhat conical but I am not sure :sad:

tom982 · Dec 30, 2012

Oops, I replied to the post on the end of page 1 thinking it was the end of the thread, only to find my post isn't in context any more.

Will it be a semi circle at the top though? That's the bit I can't get my head around, I just can't imagine it being that simple for the upper half.

Laxer · Dec 30, 2012

I think it would be a point... If you treat everything as a particle launched from the same point the particle that reaches the highest point would have been fired straight up (90 deg) anything fired at a different angle would have an x component and a y component less than the max height... I can't think of the exact shape but it would flared out at the bottom and pointed towards the top...

Bugs me now that I cant remember the math to back it up >.<

tom982 · Dec 30, 2012

I'm curious now, and it'll bug me until I find out what it's like. I've got Maple 16 at my uni flat, but not with me at the moment so I'm going to have to plot this line by line until a shape emerges!

y=xtan(θ)-(9.81x^2(1+tan^2(θ)))/800

Laxer · Dec 30, 2012

Perhaps it will still be parabolic...

something similar to this but rotated:

:lolg: sorry for giving you all this extra thought process Tom

tom982 · Dec 30, 2012

Nice job with the graph! It looks great - what did you use to make it?

Are those numbers specific to this problem, or is it just a general idea of the shape for projectiles?

Laxer · Dec 30, 2012

Just a general idea of a projectile launched with a fixed velocity...

I know there is an app at wolframalpha to solve optimal angle that shows the outside curve well but I wasn't able to find it

AceInfinity · Dec 31, 2012

Laxer said:
If you think about it aces image above is really only a fraction of the answer because they projectiles could be launched say straight up or...

I think the final shape will be somewhat conical but I am not sure :sad:

Half?! lol... Look at where that horizontal 100m line is in my drawing, below the top of the semi-circle. I accounted for pieces that fly anywhere above 0 or 180 degrees (depending on how you look at it), but it would be a semi-circle. Take this illustration for example:

Now imagine if I was to draw a line (affected by gravity) for every fraction of a degree in that drawing... Pieces just a fraction of a degree off from 90 degrees, would go just slightly lower than the piece going straight up, because part of the vertical component with it's momentum split into an x and y component is taken away (because part of the energy from the blast propelling that chunk, is being put to make it move to the side, instead of all straight up). Agree?

Thus, It would be a point at the top, but you would hardly be able to tell.

There's just a fraction of the velocity missing for the y component when it's not going directly 90 degrees, and that would affect it's height slightly. Think about it in terms of x and y components. At a 45 degree angle, there's an equal x and y component for velocity, and the acceleration of gravity just so happens to make it result in a curve once it overcomes the force of the blast pushing up against the flow of gravity.

tom982 · Dec 31, 2012

Loving the scientific model Ace

I have to disagree though, I don't think it is a semi circle. Just to clarify, I'm talking about the bit above point of explosion, ie the upper half.

It doesn't need saying that the maximum height reached will be the fragment fired at 90^o from the horizontal. To calculate the distance, I rearranged one of the SUVAT equations:

V² = U² + 2AS

To give:

S = (V² - U²)/2A

Inputting our data, we get:

S = (0² - 20²)/2*-9.81
S = 20.38735984m

I also did it with V=U+AT and S=UT+0.5AT² and got the same result.

Now, calculating how wide the blast radius is:

These are the y-components of the projectile:

V=U+AT => 0=20sin(45)-9.8t => t=1.441604039s

(I worked it out the long way, calculating time first, because I thought it would be useful to know time for other calculations)

Then with the x-components:

s=20cos(45)t (from S=UT+0.5AT² , A=0 as it's the x-component so S=UT)
s=20.38735984m

But this is only to the point where the projectile is at its max height, ie in the middle, so we double it to get:

40.77471968m

If it was a semi circle, then the radius would be the same all around the origin :)

Tom

AceInfinity · Dec 31, 2012

tom982 said:
Loving the scientific model Ace

I have to disagree though, I don't think it is a semi circle. Just to clarify, I'm talking about the bit above point of explosion, ie the upper half.

It doesn't need saying that the maximum height reached will be the fragment fired at 90^o from the horizontal. To calculate the distance, I rearranged one of the SUVAT equations:

V² = U² + 2AS

To give:

S = (V² - U²)/2A

Inputting our data, we get:

S = (0² - 20²)/2*-9.81
S = 20.38735984m

I also did it with V=U+AT and S=UT+0.5AT² and got the same result.

Now, calculating how wide the blast radius is:

These are the y-components of the projectile:

V=U+AT => 0=20sin(45)-9.8t => t=1.441604039s

(I worked it out the long way, calculating time first, because I thought it would be useful to know time for other calculations)

Then with the x-components:

s=20cos(45)t (from S=UT+0.5AT² , A=0 as it's the x-component so S=UT)
s=20.38735984m

But this is only to the point where the projectile is at its max height, ie in the middle, so we double it to get:

40.77471968m

If it was a semi circle, then the radius would be the same all around the origin :)

Tom

No, not the origin but the base (as reference to where the pieces land being the widest part of the semi-circle. Because pieces flying off at 45 degrees, above the 100m plane, will go the farthest by the time they hit the ground. So really, the only relevant chunks that make up the outer "shell" of the volume, would be the pieces that fly off from 45 degrees above the 100m plane, and up to the 90 degree angle. Gravity will take care of the rest.

You've also got to remember, that the origin you are talking about is not positioned at the core of a half of a sphere as what this blast radius would look like. It's about somewhere in the half of a half of a sphere range. :thumbsup2:

edit: maybe not exactly half of a half, because it depends on how high the chunks fly from the point of explosion relative to the distance from the point of explosion to the ground.

Redeye3323 · Jan 21, 2013

Hey all,

I went for a complex c# method for doing Problem 1 but it doesn't work, can anyone spot the problem :S

Code:

int counter = 0;
            int x = 3;
            int[] multiplesOfThree = new int[333];
            int y = 5;
            int[] multiplesOfFive = new int[199];
            int result = 0;

            while (x < 1000)
            {
                multiplesOfThree[counter] = x;
                counter++;
                x = x + 3;
            }

            counter = 0;

            while (y < 1000)
            {
                multiplesOfFive[counter] = y;
                counter++;
                y = y + 5;
            }

            foreach (int i in multiplesOfThree)
            {
                result = result + i;
            }

            foreach (int i in multiplesOfFive)
            {
                result = result + i;
            }

            Console.WriteLine("Result = " + result);

            Console.ReadLine();

AceInfinity · Jan 21, 2013

Redeye3323 said:

Hey all,

I went for a complex c# method for doing Problem 1 but it doesn't work, can anyone spot the problem :S

Code:

int counter = 0;
            int x = 3;
            int[] multiplesOfThree = new int[333];
            int y = 5;
            int[] multiplesOfFive = new int[199];
            int result = 0;

            while (x < 1000)
            {
                multiplesOfThree[counter] = x;
                counter++;
                x = x + 3;
            }

            counter = 0;

            while (y < 1000)
            {
                multiplesOfFive[counter] = y;
                counter++;
                y = y + 5;
            }

            foreach (int i in multiplesOfThree)
            {
                result = result + i;
            }

            foreach (int i in multiplesOfFive)
            {
                result = result + i;
            }

            Console.WriteLine("Result = " + result);

            Console.ReadLine();

May be good in theory, but recognize, that you would be adding duplicates. Calculating multiples of 3, and 5 separately, then adding the values to the result, you would be adding 15 twice for example. Once for iterating through the multiples of 3, and once again for iterating through the multiples of 5... Since, 15 is evenly divisible, by both 3 and 5. :)

Doing it separately you'd have to check if the value already exists in the array, if you're deciding to use an array for this:

Code:

int[] arr = new int[1000 / 5 + 1000 / 3];
int count = 0;
int result = 0;

for (int i = 3; i < 1000; i += 3)
{
	if (Array.IndexOf(arr, i) < 0)
	{
		arr[count++] = i;
	}
}

for (int i = 5; i < 1000; i += 5)
{
	if (Array.IndexOf(arr, i) < 0)
	{
		arr[count++] = i;
	}
}

for (int i = 0; i < count; i++)
{
	result += arr[i];
}

Otherwise, you can just loop from 3 to 999 once and check for even divisibility using the modulus operator:

Code:

int result = 0;
for (int i = 3; i < 1000; i++)
{
	if (i % 3 == 0 || i % 5 == 0)
	{
		result += i;
	}
}
Console.WriteLine(result);

Otherwise you can use LINQ to do relatively the same thing. Although I would've just used the loop:

Code:

Enumerable.Range(3, 997).Where(i => i % 3 == 0 || i % 5 == 0).Sum();

If you want to review an answer, I've posted up to ~45 answers in C# on the net.

Will · Jan 22, 2013

Adding duplicates must have been where I went wrong as well. Time to give this another shot.

Redeye3323 · Jan 22, 2013

I spent an hour debugging that whole program, and it seems that my understanding of the problem itself was the actual issue. Visual Studio doesn't have any way of debugging my brain does it :laugh:

I don't know how to use Enumerables if I am honest :S

[UPDATE] I went back and made a simple change to my code which fixed my issue.

I changed

Code:

foreach (int i in multiplesOfFive)
{
    result = result + i;
}

to

Code:

foreach (int i in multiplesOfFive)
{
    if ((i % 3) != 0)
    {
          result = result + i;
    }
}

AceInfinity · Jan 22, 2013

My last method there was an IEnumerable result that I applied LINQ to, in order to get a result of the summed values. :)

AceInfinity · Jun 2, 2013

Problem #55 Solution

Code:

bool isPalindrome(std::string s, int lowerIndex, int upperIndex)
{
	if (upperIndex <= lowerIndex) return true;
	if (s[lowerIndex] != s[upperIndex]) return false;
	return isPalindrome(s, ++lowerIndex, --upperIndex);
}

void Problem55()
{
	// How many Lychrel numbers are there below ten-thousand?
	int count = 0;
	for (int i = 1; i < 10000; i++)
	{
		int steps = 0;
		unsigned long long j = i, k;
		bool isLychrel = false;
		while (!isLychrel && steps < 50)
		{
			std::stringstream ss;
			std::string s; ss << j; s = ss.str();
			std::reverse(s.begin(), s.end());

			ss.str(s); ss >> k;

			// Empty and clear string stream
			ss.str(std::string()); // Set string contents
			ss.clear(); // Clear EOF flag bit

			ss << j + k; s = ss.str(); // Sum
			if (isPalindrome(s, 0, s.length() - 1)) isLychrel = true;

			ss >> j;
			steps++;
		}
		if (!isLychrel) count++;
	}
	std::cout << "Ans: " << count << std::endl;
}

I wrote this one in C++ a while ago.

AceInfinity · Jun 8, 2013

Lets (re?)awaken the programmers here. :) I'm having issues with #60. I've wrote it out a few times, but it seems a straight bruteforce iterative method isn't going to work. Even with generated primes and iterators pulling primes out to concatenate. My concatenation methods are vamped up for optimization as well, no strings, just straight math to avoid casting back and forth, but I still haven't got a solution (within a reasonable amount of time).

Project Euler

Emeritus, Contributor

Co-FounderSenior Administrator

Emeritus

Co-FounderSenior Administrator

Emeritus

Co-FounderSenior Administrator

Emeritus

Co-FounderSenior Administrator

Emeritus

Co-FounderSenior Administrator

Emeritus, Contributor

Emeritus

Emeritus, Contributor

Member

Emeritus, Contributor

Senior Administrator

Member

Emeritus, Contributor

Emeritus, Contributor

Emeritus, Contributor

Co-Founder
Senior Administrator

Co-Founder
Senior Administrator

Co-Founder
Senior Administrator

Co-Founder
Senior Administrator

Co-Founder
Senior Administrator