Project Euler/11 - Revision history

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

2019-10-09T03:45:50Z

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

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

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

	In this problem you are presented with a 20 x 20 grid, and asked to find the maximum product of 4 sequential integers (up, down, left, right, diagonal up/diagonal down).		In this problem you are presented with a 20 x 20 grid, and asked to find the maximum product of 4 sequential integers (up, down, left, right, diagonal up/diagonal down).

Admin at 08:26, 8 July 2017

2017-07-08T08:26:44Z

← Older revision		Revision as of 08:26, 8 July 2017
Line 1:		Line 1:
	Project Euler problem 11: https://projecteuler.net/problem=11		Project Euler problem 11: https://projecteuler.net/problem=11

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

	In this problem you are presented with a 20 x 20 grid, and asked to find the maximum product of 4 sequential integers (up, down, left, right, diagonal up/diagonal down).		In this problem you are presented with a 20 x 20 grid, and asked to find the maximum product of 4 sequential integers (up, down, left, right, diagonal up/diagonal down).

Admin at 08:26, 8 July 2017

2017-07-08T08:26:24Z

← Older revision		Revision as of 08:26, 8 July 2017
Line 2:		Line 2:

	In this problem you are presented with a 20 x 20 grid, and asked to find the maximum product of 4 sequential integers (up, down, left, right, diagonal up/diagonal down).		In this problem you are presented with a 20 x 20 grid, and asked to find the maximum product of 4 sequential integers (up, down, left, right, diagonal up/diagonal down).

			==The data structure==

	The way that I thought about this problem was, we were applying a stencil - a moving window, that was looking at a similar sequence of 4 integers, but applied to different parts of the square. Initially, it was my intention to solve this problem using some kind of recursive backtracking - start at the end and work backwards, trying 4-number combinations as I went. However, this is a gross overcomplication. The stencil idea turns out to be a good one to focus on.		The way that I thought about this problem was, we were applying a stencil - a moving window, that was looking at a similar sequence of 4 integers, but applied to different parts of the square. Initially, it was my intention to solve this problem using some kind of recursive backtracking - start at the end and work backwards, trying 4-number combinations as I went. However, this is a gross overcomplication. The stencil idea turns out to be a good one to focus on.

			==The procedure==

	To apply a stencil, you can use a sub-array, and walk the sub-array along the main array structure. Copy operations can also be sped up (if talking about primitive data). In this case, the stencil is a 4 x 4 sub-array. We are looking at valid 4-integer products that are covered by the stencil (specifically, we are computing them, and comparing them to a running maximum to see if we have a new 4-integer sequence yielding a larger product).		To apply a stencil, you can use a sub-array, and walk the sub-array along the main array structure. Copy operations can also be sped up (if talking about primitive data). In this case, the stencil is a 4 x 4 sub-array. We are looking at valid 4-integer products that are covered by the stencil (specifically, we are computing them, and comparing them to a running maximum to see if we have a new 4-integer sequence yielding a larger product).

	The moving stencil operation can also be adapted to linked or array structures, and a great deal more optimization can be done to minimize the number of products computed and operations performed.		The moving stencil operation can also be adapted to linked or array structures, and a great deal more optimization can be done to minimize the number of products computed and operations performed.

			==The more general principle==

			The solution to this problem is one that applies to any number of other problems involving finding combinations of local values - if you build a stencil structure, and shift the structure as you move through all of your data, you can implement the calculations once and keep the task simple.

			Note that the way that I implemented it was inefficient - I was re-computing many of the combinations of local values that I had computed before. With greater care and more time this could be improved, but the algorithm is quite cheap for the given problem so speed was not an issue.



	{{ProjectEulerFlag}}		{{ProjectEulerFlag}}
	[[Category:Grid]]		[[Category:Grid]]

Admin: Admin moved page Project Euler/Greatest Product in Grid to Project Euler/11

2017-07-05T04:14:05Z

Admin moved page Project Euler/Greatest Product in Grid to Project Euler/11

← Older revision	Revision as of 04:14, 5 July 2017
(No difference)

Admin: Created page with "Project Euler problem 11: https://projecteuler.net/problem=11 In this problem you are presented with a 20 x 20 grid, and asked to find the maximum product of 4 sequential int..."

2017-07-01T09:22:32Z

Created page with "Project Euler problem 11: https://projecteuler.net/problem=11 In this problem you are presented with a 20 x 20 grid, and asked to find the maximum product of 4 sequential int..."

New page

Project Euler problem 11: https://projecteuler.net/problem=11

In this problem you are presented with a 20 x 20 grid, and asked to find the maximum product of 4 sequential integers (up, down, left, right, diagonal up/diagonal down).

The way that I thought about this problem was, we were applying a stencil - a moving window, that was looking at a similar sequence of 4 integers, but applied to different parts of the square. Initially, it was my intention to solve this problem using some kind of recursive backtracking - start at the end and work backwards, trying 4-number combinations as I went. However, this is a gross overcomplication. The stencil idea turns out to be a good one to focus on.

To apply a stencil, you can use a sub-array, and walk the sub-array along the main array structure. Copy operations can also be sped up (if talking about primitive data). In this case, the stencil is a 4 x 4 sub-array. We are looking at valid 4-integer products that are covered by the stencil (specifically, we are computing them, and comparing them to a running maximum to see if we have a new 4-integer sequence yielding a larger product).

The moving stencil operation can also be adapted to linked or array structures, and a great deal more optimization can be done to minimize the number of products computed and operations performed.

{{ProjectEulerFlag}}
[[Category:Grid]]