Project Euler/Problem 102 - Revision history

Admin at 06:08, 31 January 2020

2020-01-31T06:08:50Z

← Older revision		Revision as of 06:08, 31 January 2020
Line 1:		Line 1:
	Project Euler problem 102: https://projecteuler.net/problem=102		Project Euler problem 102: https://projecteuler.net/problem=102

	Solution: https://git.charlesreid1.com/cs/euler/src/master/102		Solution: https://git.charlesreid1.com/cs/euler/src/branch/master/scratch/Round3_100-110/102

	=Notes=		=Notes=

Admin: Replacing charlesreid1.com:3000 with git.charlesreid1.com

2019-10-09T03:50:10Z

Replacing charlesreid1.com:3000 with git.charlesreid1.com

← Older revision		Revision as of 03:50, 9 October 2019
Line 1:		Line 1:
	Project Euler problem 102: https://projecteuler.net/problem=102		Project Euler problem 102: https://projecteuler.net/problem=102

	Solution: https://charlesreid1.com~~:3000~~/cs/euler/src/master/102		Solution: https://git.charlesreid1.com/cs/euler/src/master/102

	=Notes=		=Notes=

Admin: /* Notes */

2017-07-08T22:09:27Z

Notes

Show changes

Admin at 22:05, 8 July 2017

2017-07-08T22:05:41Z

← Older revision		Revision as of 22:05, 8 July 2017
Line 1:		Line 1:
			Project Euler problem 102: https://projecteuler.net/problem=102

			Solution: https://charlesreid1.com:3000/cs/euler/src/master/102

			=Notes=

	The solution to Problem 102 came fairly quickly - it comes from comparing cases where the triangle does contain the origin, to cases where the triangle does not.		The solution to Problem 102 came fairly quickly - it comes from comparing cases where the triangle does contain the origin, to cases where the triangle does not.

	We start by noticing the pattern, that if all the points are clustered on one side of the graph, there is no way it will contain the origin. Same thing with top and bottom. From this we deduce that we need the x values or the y values or both to span the origin. Start by assuming that ONLY the x points straddle the origin, that is, that if we have two points on one side of the origin, we have one point on the other. Now we actually "draw" the two legs of the triangle that would fall on either side of the origin. Given the endpoints of the triangle, we can determine the equation of the line using the point-slope formula. Finally, we find if these fall on either side of the origin by comparing the signs of the y-intercepts.		We start by noticing the pattern, that if all the points are clustered on one side of the graph, there is no way it will contain the origin. Same thing with top and bottom. From this we deduce that we need the x values or the y values or both to span the origin. Start by assuming that ONLY the x points straddle the origin, that is, that if we have two points on one side of the origin, we have one point on the other. Now we actually "draw" the two legs of the triangle that would fall on either side of the origin. Given the endpoints of the triangle, we can determine the equation of the line using the point-slope formula. Finally, we find if these fall on either side of the origin by comparing the signs of the y-intercepts.

	[[Image:PETriangle1.jpg\|~~500px~~]]		[[Image:PETriangle1.jpg\|300px]]

	[[Image:PETriangle2.jpg\|500px]]		[[Image:PETriangle2.jpg\|500px]]
Line 15:		Line 21:


			=Flags=

	{{ProjectEulerFlag}}		{{ProjectEulerFlag}}

			[[Category:Math]]
			[[Category:Geometry]]

Admin at 22:04, 8 July 2017

2017-07-08T22:04:31Z

← Older revision		Revision as of 22:04, 8 July 2017
Line 13:		Line 13:
	** If the parity of the triangle is negative (two endpoints are on negative x side) we should use positive x endpoint for both lines		** If the parity of the triangle is negative (two endpoints are on negative x side) we should use positive x endpoint for both lines
	* The other two endpoints should each be used once in each of the two lines.		* The other two endpoints should each be used once in each of the two lines.



			{{ProjectEulerFlag}}

Admin at 22:03, 8 July 2017

2017-07-08T22:03:31Z

← Older revision		Revision as of 22:03, 8 July 2017
Line 2:		Line 2:

	We start by noticing the pattern, that if all the points are clustered on one side of the graph, there is no way it will contain the origin. Same thing with top and bottom. From this we deduce that we need the x values or the y values or both to span the origin. Start by assuming that ONLY the x points straddle the origin, that is, that if we have two points on one side of the origin, we have one point on the other. Now we actually "draw" the two legs of the triangle that would fall on either side of the origin. Given the endpoints of the triangle, we can determine the equation of the line using the point-slope formula. Finally, we find if these fall on either side of the origin by comparing the signs of the y-intercepts.		We start by noticing the pattern, that if all the points are clustered on one side of the graph, there is no way it will contain the origin. Same thing with top and bottom. From this we deduce that we need the x values or the y values or both to span the origin. Start by assuming that ONLY the x points straddle the origin, that is, that if we have two points on one side of the origin, we have one point on the other. Now we actually "draw" the two legs of the triangle that would fall on either side of the origin. Given the endpoints of the triangle, we can determine the equation of the line using the point-slope formula. Finally, we find if these fall on either side of the origin by comparing the signs of the y-intercepts.

			[[Image:PETriangle1.jpg\|500px]]

			[[Image:PETriangle2.jpg\|500px]]

			Implementing this solution required some somewhat complicated logic to decide which points to draw which lines from and to. I'm not sure how to avoid this. Here are the decisions and the decision criteria involved:
			* First, determine the "parity" of the triangle - how many points have positive x values, minus how many points have negative x values. If the parity is not 1 or -1, the triangle cannot contain the origin.
			* One of the endpoints will be used in both lines that we draw. This is the point whose x value has the opposite sign as our parity.
			** If the parity of the triangle is positive (meaning there are two endpoints on the positive x side) we should use the negative x endpoint for both of our lines
			** If the parity of the triangle is negative (two endpoints are on negative x side) we should use positive x endpoint for both lines
			* The other two endpoints should each be used once in each of the two lines.

Admin at 21:54, 8 July 2017

2017-07-08T21:54:04Z

← Older revision		Revision as of 21:54, 8 July 2017
Line 1:		Line 1:
	The solution to Problem 102 came fairly quickly - it comes from comparing cases where the triangle does contain the origin, to cases where the triangle does not.		The solution to Problem 102 came fairly quickly - it comes from comparing cases where the triangle does contain the origin, to cases where the triangle does not.

	We start by noticing the pattern, that if all the points are clustered on one side of the graph, there is no way it will contain the origin. Same thing with top and bottom. From this we deduce that we need the x values or the y values or both to span the origin.		We start by noticing the pattern, that if all the points are clustered on one side of the graph, there is no way it will contain the origin. Same thing with top and bottom. From this we deduce that we need the x values or the y values or both to span the origin. Start by assuming that ONLY the x points straddle the origin, that is, that if we have two points on one side of the origin, we have one point on the other. Now we actually "draw" the two legs of the triangle that would fall on either side of the origin. Given the endpoints of the triangle, we can determine the equation of the line using the point-slope formula. Finally, we find if these fall on either side of the origin by comparing the signs of the y-intercepts.

	Start by assuming that ONLY the x points straddle the origin, that is, that if we have two points on one side of the origin, we have one point on the other. Now we actually "draw" the two legs of the triangle that would fall on either side of the origin. Given the endpoints of the triangle, we can determine the equation of the line using the point-slope formula. Finally, we find if these fall on either side of the origin by comparing the signs of the y-intercepts.

Admin: Created page with "The solution to Problem 102 came fairly quickly - it comes from comparing cases where the triangle does contain the origin, to cases where the triangle does not. We start by..."

2017-07-08T21:50:00Z

Created page with "The solution to Problem 102 came fairly quickly - it comes from comparing cases where the triangle does contain the origin, to cases where the triangle does not. We start by..."

New page

The solution to Problem 102 came fairly quickly - it comes from comparing cases where the triangle does contain the origin, to cases where the triangle does not.

We start by noticing the pattern, that if all the points are clustered on one side of the graph, there is no way it will contain the origin. Same thing with top and bottom. From this we deduce that we need the x values or the y values or both to span the origin.

Start by assuming that ONLY the x points straddle the origin, that is, that if we have two points on one side of the origin, we have one point on the other. Now we actually "draw" the two legs of the triangle that would fall on either side of the origin. Given the endpoints of the triangle, we can determine the equation of the line using the point-slope formula. Finally, we find if these fall on either side of the origin by comparing the signs of the y-intercepts.