Project Euler/502 - Revision history

Admin: Add solution link at top (via update-page on MediaWiki MCP Server)

2026-06-17T22:13:49Z

Add solution link at top (via update-page on MediaWiki MCP Server)

← Older revision		Revision as of 22:13, 17 June 2026
Line 1:		Line 1:
	Link; https://projecteuler.net/problem=502		Link; https://projecteuler.net/problem=502

			Solution: https://git.charlesreid1.com/cs/euler/src/branch/main/java/Problem502.java

	Solved: March 31, 2026		Solved: March 31, 2026

Unknown user at 17:57, 31 March 2026

2026-03-31T17:57:52Z

← Older revision		Revision as of 17:57, 31 March 2026
Line 1:		Line 1:
	Link; https://projecteuler.net/problem=502		Link; https://projecteuler.net/problem=502

			Solved: March 31, 2026

	=Project 502: Castle Polyominos=		=Project 502: Castle Polyominos=

Unknown user: /* Project 502: Castle Polyominos */

2026-03-28T21:07:23Z

Project 502: Castle Polyominos

@@ Line 3: / Line 3: @@
 =Project 502: Castle Polyominos=
-In Problem 502, we are presented with the following problem: given a lattice grid of width W and height H, we wish to place blocks down on the grid, according to certain rules, such that we construct a castle.
+We define a block to be a rectangle with a height of  and an integer-valued length. Let a castle be a configuration of stacked blocks.
 =Overview of Solution Approach=

Unknown user: /* Don't Count: Generate */

2025-04-22T01:28:39Z

Don't Count: Generate

← Older revision		Revision as of 01:28, 22 April 2025
Line 10:		Line 10:
	==Don't Count: Generate==		==Don't Count: Generate==

	~~Most of the discussions and/or attempts I've seen at the problem are attempting to actually enumerate the total number of combinations. But, think for just a minute about how insane that idea is.~~ For scale, The number of configurations for a castle with a width and height on the order of 10 - just a measely 13x10 grid - is given in the original problem as <math>F(13,10) = 3,729,050,610,636</math>. You can't ask a computer to COUNT that high, let alone store that many castles.		For scale, The number of configurations for a castle with a width and height on the order of 10 - just a measely 13x10 grid - is given in the original problem as <math>F(13,10) = 3,729,050,610,636</math>. You can't ask a computer to COUNT that high, let alone store that many castles.

	Now, the question at hand is to enumerate castles with a height of a TRILLION - so, a single castle will take a TERABYE just to store, and will take your computer a solid hour to generate a single castle (assuming you've got enough memory, or disk space). The larger castle configuration counts are mod a billion, with a b, so they're going to be mind-bogglingly large.		Now, the question at hand is to enumerate castles with a height of a TRILLION - so, a single castle will take a TERABYE just to store, and will take your computer a solid hour to generate a single castle (assuming you've got enough memory, or disk space). The larger castle configuration counts are mod a billion, with a b, so they're going to be mind-bogglingly large.

Unknown user at 01:28, 22 April 2025

2025-04-22T01:28:10Z

← Older revision		Revision as of 01:28, 22 April 2025
Line 1:		Line 1:
			Link; https://projecteuler.net/problem=502

	=Project 502: Castle Polyominos=		=Project 502: Castle Polyominos=

	In Problem 502, we are presented with the following problem: given a lattice grid of width W and height H, we wish to place blocks down on the grid, according to certain rules, such that we construct a castle.		In Problem 502, we are presented with the following problem: given a lattice grid of width W and height H, we wish to place blocks down on the grid, according to certain rules, such that we construct a castle.

	~~Project Euler problem: https://projecteuler.net/problem=502~~

	=Overview of Solution Approach=		=Overview of Solution Approach=

Unknown user: /* Generating functions */

2025-04-22T01:09:10Z

Generating functions

← Older revision		Revision as of 01:09, 22 April 2025
Line 20:		Line 20:

	The short version of how to use generating functions is to come up with a multivariate polynomial whose variables are dimensions of the problem (width and height, or some other variables if they are more convenient) and whose coefficients are the solutions to our problem.		The short version of how to use generating functions is to come up with a multivariate polynomial whose variables are dimensions of the problem (width and height, or some other variables if they are more convenient) and whose coefficients are the solutions to our problem.
	This ~~makes~~ finding a solution for a particular problem ~~as straightforward as~~ evaluating a particular term of the generating function (where each term is implemented using a recursive function or a similar method).		This turns the problem of finding a solution for a particular problem into evaluating a particular term of the generating function (where each term is implemented using a recursive function or a similar method).

	See [[Generating Functions]] for more details.		See [[Generating Functions]] for more details.

Unknown user: /* Useful Facts */

2025-04-22T01:05:43Z

Useful Facts

← Older revision		Revision as of 01:05, 22 April 2025
Line 249:		Line 249:

	<math>		<math>
	3729050610636 = 2^2 \times 3 \times 1163 \times 20553887		F(13,10) = 3729050610636 = 2^2 \times 3 \times 1163 \times 20553887
			</math>

			<math>
			F(10,13) = 37959702514 = 2 \times 102859 \times 184523
	</math>		</math>

Unknown user: /* References */

2025-04-22T01:03:53Z

References

← Older revision		Revision as of 01:03, 22 April 2025
Line 243:		Line 243:

	Meaning, on a grid of height 4 and width 5, there are 210 convex castles.		Meaning, on a grid of height 4 and width 5, there are 210 convex castles.

			=Useful Facts=

			Factorization of 3729050610636:

			<math>
			3729050610636 = 2^2 \times 3 \times 1163 \times 20553887
			</math>

	=References=		=References=

Unknown user: /* Step 2 Enumerating Convex Castles */

2021-08-25T19:12:39Z

Step 2 Enumerating Convex Castles

← Older revision		Revision as of 19:12, 25 August 2021
Line 227:		Line 227:

	<math>		<math>
	\mbox{CCC} = C(2(H-1)+W-1, W-1)		\mbox{CCC} = C(2(H-1)+W-1, W-1) = C(2H+W-3, W-1)
	</math>		</math>

Line 236:		Line 236:
	</pre>		</pre>

	Now we will insert W - 1 = 4 Rs into the castle, placing them into 2(H - 1) + 1 = 2(3)+1 = 7 partitions (which can hold multiple Rs), for a count of convex castles of:		Now we will insert W - 1 = 4 Rs into the castle, placing them into 2 (H - 1) + 1 = 2(3)+1 = 7 partitions (which can hold multiple Rs), for a count of convex castles of:

	<math>		<math>
	\mbox{CCC} = C(~~2(H-1)~~+W-1, W-1) = C(2(4~~-1)~~+5-1, 5-1) = C(10, 4) = 210		\mbox{CCC} = C(2H + W - 3, W-1) = C(2*4 + 5 - 3, 5-1) = C(10, 4) = 210
	</math>		</math>

Unknown user: /* Step 2 Enumerating Convex Castles */

2021-08-25T14:29:27Z

Step 2 Enumerating Convex Castles

← Older revision		Revision as of 14:29, 25 August 2021
Line 227:		Line 227:

	<math>		<math>
	CCC = C(2(H-1)+W-1, W-1)		\mbox{CCC} = C(2(H-1)+W-1, W-1)
	</math>		</math>

Line 239:		Line 239:

	<math>		<math>
	CCC = C(2(H-1)+W-1, W-1) = C(2(4-1)+5-1, 5-1) = C(10, 4) = 210		\mbox{CCC} = C(2(H-1)+W-1, W-1) = C(2(4-1)+5-1, 5-1) = C(10, 4) = 210
	</math>		</math>