Project Euler/18 - Revision history

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

2019-10-09T03:46:30Z

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

← Older revision		Revision as of 03:46, 9 October 2019
Line 74:		Line 74:
	==Code==		==Code==

	Problem 18 code: https://charlesreid1.com~~:3000~~/cs/euler/src/master/scratch/Round1_001-020/018		Problem 18 code: https://git.charlesreid1.com/cs/euler/src/master/scratch/Round1_001-020/018

	Problem 67 code: https://charlesreid1.com~~:3000~~/cs/euler/src/master/scratch/Round2_050-070/067		Problem 67 code: https://git.charlesreid1.com/cs/euler/src/master/scratch/Round2_050-070/067

	==Flags==		==Flags==

Admin at 09:05, 8 January 2018

2018-01-08T09:05:47Z

← Older revision		Revision as of 09:05, 8 January 2018
Line 1:		Line 1:
	~~Link: https://projecteuler.net/problem~~=18		==The Problem==

	~~Related: [[Project Euler/67]]~~

	<pre>		<pre>
Line 14:		Line 12:
	it cannot be solved by brute force, and requires a clever method! ;o)		it cannot be solved by brute force, and requires a clever method! ;o)
	</pre>		</pre>

			Link: https://projecteuler.net/problem=18

			Related: [[Project Euler/67]]

			==The Solution==

	Note:		Note:
			* Initial idea was marginal sums, change directions when marginal sum changes

	~~Initial~~ idea ~~was marginal sums, change directions when marginal sum changes~~		Next idea:
			* Normalized marginal sums
	~~Next idea was normalized~~ marginal sums

	Actually implemented these, failure		Actually implemented these, failure

	Third idea ~~was summing~~ up sub-triangles on left and right		Third idea:
			* Summing up sub-triangles on left and right

	This actually gets you pretty close to correct, but not quite.		This actually gets you pretty close to correct, but not quite.

	I knew the algorithm was flawed in a subtle way because it worked for contrived examples and for smaller triangles, but not for larger triangles. Counter-example was needed.		I knew the algorithm was flawed in a very subtle way because it worked for contrived examples and for smaller triangles, but not for larger triangles. Counter-example was needed.

	I ended up writing a recursive solution to solve the problem via brute force (about a second) and that gave me the correct path.		I ended up writing a recursive solution to solve the problem via brute force (about 1 second) and that gave me the correct path. At this point I could have solved this problem, but not Problem 67.

	I ~~then~~ compared ~~this~~ path to the path that my algorithm was predicting, and found a counterexample:		I compared the brute force solution path to the path that my algorithm was predicting, and found a counterexample:

	<pre>		<pre>
Line 41:		Line 46:
	This is a counterexample to my proposed method of finding the correct route, because the left subtriangle has a larger sum than the right subtriangle, and therefore my algorithm recommends choosing 23 then 77, instead of the more obvious 75 then 73.		This is a counterexample to my proposed method of finding the correct route, because the left subtriangle has a larger sum than the right subtriangle, and therefore my algorithm recommends choosing 23 then 77, instead of the more obvious 75 then 73.

	This arises because we cannot utilize all of the outcomes in the left and right subtriangles - we need a way to say, yes, having a really huge number in your subtriangle is important - that's why we always want to sum over the entire subtriangle. However, we also need a way to account for the importance of the first choice we make over all the other choices - that is, choosing to go left because there is a value of 100 somewhere 5 levels away in the left sub-triangle is different from choosing to go left because you are choosing between 1 and 100. The two should be weighted differently.		This arises because we cannot utilize all of the outcomes in the left and right subtriangles - we need a way to say, yes, having a really huge number ''somewhere'' in your subtriangle is important - that's why we always want to sum over the ''entire'' subtriangle. However, we also need a way to account for the importance of the first choice we make over all the other choices - that is, choosing to go left because there is a value of 100 somewhere 5 levels away in the left sub-triangle is different from choosing to go left because you are choosing between 1 and 100.

			The two should be weighted differently.

	This leads to a more formalized approach to the problem. Of course, we should have seen this earlier, but this is precisely what the Project Euler questions are intended to do.		This leads to a more formalized approach to the problem. Of course, we should have seen this earlier, but this is precisely what the Project Euler questions are intended to do.

	We can take a statistical/mathematical approach to the problem of finding the maximum cost function over a group of discrete choices~~, by saying that~~ we ~~want~~ to maximize the expectation of our sum. We are given a choice between left and right, and we want to make a quantitative choice between left and right, so we assign a value. The value is the expected sum, the expected value of the sum, if we take the average over all the paths that the left choice would lead us to, versus the average over all the paths that the right choice would lead us to.		We can take a statistical/mathematical approach to the problem of finding the maximum cost function over a group of discrete choices: we say wewant to ''maximize the expectation of our sum.''

			We are given a choice between left and right, and we want to make a quantitative choice between left and right, so we assign a value. The value is the expected sum, the expected ''value of the sum'', if we take the average over all the paths that the left choice would lead us to, versus the average over all the paths that the right choice would lead us to.

	In the example tree above:		In the example tree above:
Line 63:		Line 72:


			==Code==

			Problem 18 code: https://charlesreid1.com:3000/cs/euler/src/master/scratch/Round1_001-020/018

			Problem 67 code: https://charlesreid1.com:3000/cs/euler/src/master/scratch/Round2_050-070/067

			==Flags==

	{{ProjectEulerFlag}}		{{ProjectEulerFlag}}

	[[Category:Probability]]		[[Category:Probability]]

Admin at 02:14, 18 July 2017

2017-07-18T02:14:38Z

← Older revision		Revision as of 02:14, 18 July 2017
Line 10:		Line 10:
	Find the maximum total from top to bottom of the triangle below:		Find the maximum total from top to bottom of the triangle below:

	NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)		NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route.
			However, Problem 67, is the same challenge with a triangle containing one-hundred rows;
			it cannot be solved by brute force, and requires a clever method! ;o)
	</pre>		</pre>

Admin at 01:39, 11 July 2017

2017-07-11T01:39:37Z

← Older revision		Revision as of 01:39, 11 July 2017
Line 1:		Line 1:
	Link: https://projecteuler.net/problem=18		Link: https://projecteuler.net/problem=18

			Related: [[Project Euler/67]]

	<pre>		<pre>

Admin at 01:39, 11 July 2017

2017-07-11T01:39:22Z

← Older revision		Revision as of 01:39, 11 July 2017
Line 1:		Line 1:
			Link: https://projecteuler.net/problem=18

			<pre>
			By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

			That is, 3 + 7 + 4 + 9 = 23.

			Find the maximum total from top to bottom of the triangle below:

			NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)
			</pre>

	Note:		Note:

Admin at 01:38, 11 July 2017

2017-07-11T01:38:32Z

← Older revision		Revision as of 01:38, 11 July 2017
Line 45:		Line 45:
	= 75 + [ (1/2)(73) + (1/2)(7) ]		= 75 + [ (1/2)(73) + (1/2)(7) ]
	</pre>		</pre>




			{{ProjectEulerFlag}}

			[[Category:Probability]]

Admin: Created page with "Note: Initial idea was marginal sums, change directions when marginal sum changes Next idea was normalized marginal sums Actually implemented these, failure Third idea was..."

2017-07-11T01:38:10Z

Created page with "Note: Initial idea was marginal sums, change directions when marginal sum changes Next idea was normalized marginal sums Actually implemented these, failure Third idea was..."

New page

Note:

Initial idea was marginal sums, change directions when marginal sum changes

Next idea was normalized marginal sums

Actually implemented these, failure

Third idea was summing up sub-triangles on left and right

This actually gets you pretty close to correct, but not quite.

I knew the algorithm was flawed in a subtle way because it worked for contrived examples and for smaller triangles, but not for larger triangles. Counter-example was needed.

I ended up writing a recursive solution to solve the problem via brute force (about a second) and that gave me the correct path.

I then compared this path to the path that my algorithm was predicting, and found a counterexample:

<pre>
82
23 75
77 73 7
</pre>

This is a counterexample to my proposed method of finding the correct route, because the left subtriangle has a larger sum than the right subtriangle, and therefore my algorithm recommends choosing 23 then 77, instead of the more obvious 75 then 73.

This arises because we cannot utilize all of the outcomes in the left and right subtriangles - we need a way to say, yes, having a really huge number in your subtriangle is important - that's why we always want to sum over the entire subtriangle. However, we also need a way to account for the importance of the first choice we make over all the other choices - that is, choosing to go left because there is a value of 100 somewhere 5 levels away in the left sub-triangle is different from choosing to go left because you are choosing between 1 and 100. The two should be weighted differently.

This leads to a more formalized approach to the problem. Of course, we should have seen this earlier, but this is precisely what the Project Euler questions are intended to do.

We can take a statistical/mathematical approach to the problem of finding the maximum cost function over a group of discrete choices, by saying that we want to maximize the expectation of our sum. We are given a choice between left and right, and we want to make a quantitative choice between left and right, so we assign a value. The value is the expected sum, the expected value of the sum, if we take the average over all the paths that the left choice would lead us to, versus the average over all the paths that the right choice would lead us to.

In the example tree above:

<pre>
E(left subtriangle) = E(level 1) + E(level 2)
= 23 + [ (1/2)(77) + (1/2)(73) ]
= 98
</pre>

whereas for the right tree:

<pre>
E(right subtriangle) = E(level 1) + E(level 2)
= 75 + [ (1/2)(73) + (1/2)(7) ]
</pre>