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.

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

Overview of Solution Approach

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 $F(13,10)=3,729,050,610,636$ . 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.

Instead of enumerating castles, you should count castles with a generating function. This is where a brief dip into the mathematical literature can help. It also helps to remember that when you start talking about numbers and functions that get as big as combinatorics and permutations numbers do, you really have to utilize more sophisticated mathematical tools than manual enumeration.

That being said, implementing a computer program to enumerate castles manually (for small widths/heights) can help crystallize ideas on how to enumerate castles mathematically.

Generating functions

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).

See Generating Functions for more details.

Castle Rules

The rules established in Problem 502, repeated here again:

Rule 1 - Blocks can be placed on top of other blocks as long as nothing sticks out past the edges or hangs out over open space.
Rule 3 - Any two neighboring blocks on the same row have at least one unit of space between them.
Rule 4 - The bottom row is occupied by a block of length w.
Rule 5 - The maximum achieved height of the entire castle is exactly h.
Rule 6 - The castle is made from an even number of blocks.

Representing Castles

Before we can count castles, we have to find a way to represent them, and translate the rules for castles into rules for constructing representations.

There are a lot of different approaches to representing castles, but we cover a few below. The method that ended up being the most helpful was the step-based strings approach, writing castles as strings of up, down, and right steps.

We cover three approaches:

Binary strings
Integer tuples
Step-based strings

Binary String Representation

One way to represent a castle is to use a binary string. Specifically, a column-wise representation of the castle can be written as a binary string, with each column consisting of two blocks: a block of zeros (indicating no blocks) and ones (indicating blocks). This will create a set of W blocks, each block of length H.

Let's look at an example:

This castle can be represented as:

11000 11100 11111 11000 11100 10000 11111 11110

The rules for constructing castles can be translated likewise into restrictions on the binary numbers we are generating. For example, the restriction that castles of height H must have at least one column of height H is a restriction on the binary digits that there must be at least one contiguous block of H 1's.

The rule that the bottom row is one continuous block, on which the rest of the castle is built, is equivalent to saying that each block begins with a 1.

The rule that the number of blocks must be even requires a little more care, but we can count the number of blocks as follows:

Split the entire string into blocks of size H:

11000 11100 11111 11000 11100 10000 11111 11110

Now, for each block, count the number of ones in that block:

2 3 5 2 3 1 5 4

Add a zero to the front and end:

0 2 3 5 2 3 1 5 4 0

Now compute the difference between each entry (entry i minus entry i-1):

+2  +1  +2  -3  +1  -2  +4  -1  -4

If we sum all of the negative integers, we get the total number of blocks:

$10=\left|(-3)+(-2)+(-1)+(-4)\right|$

Integer Tuples

From the bit of analysis above, we might find an integer tuple representation of a castle more convenient. Specifically, we can represent a castle of known width by writing the number of up or down steps, or the height, between each rightward step.

This castle of width 8 can be represented with 8 integers:

2 3 5 2 3 1 5 4

We already saw that the number of blocks can be obtained by summing the negative numbers, and this can be used to check if the number of blocks is even. We can also easily specify that the castle should reach a height of exactly H by ensuring there is at least one integer with the value of H in the tuple, and ensure that the castle does not drop below the minimum height by ensuring all integers in the tuple are > 0.

Steps-Based Approach

The representation that led to the most breakthroughs in progressing with PE 502 was the same representation used to solve the Lattice Paths problem in Project Euler/15. In that problem, we represented a path through a lattice using a string of letters like RRRDDD. We can do the same thing here to represent castles.

Let's start with the simplest castles: rectangular castles. These castles consist of Us, then Rs, then Ds, representing upward steps, rightward steps, and downward steps. The 4 x 8 rectangular castle would be:

UUUURRRRRRRRDDD

The next type of castle is what we will call a convex castle. This type of castle can be split into three portions: the front, the middle, and the back.

The front of the castle consists of interspersed U and R steps, until the castle reaches its maximum height. No D steps are present in the front part.
The middle of the castle consists of any R steps taken at the maximum height. There must be at least one R step in the middle.
The back of the castle consists of interspersed D and R steps, until the castle reaches its base. No U steps are present in the back part.
The convex castle must begin with a U and end with a D (as per Rule X).

A few examples of convex castles:

UURUURUURUU RRRRRRR DDRDDRDDRDD
^           ^       ^
front       middle  back

URRRRRRUUUUURDDDDDD

UURRUURRRRRRUURDRDRRDDDD

UUUUUURRRRUUUUUURURRRDDDDDDRRDRRRRDRRDRRRRRRDDDD

URRRRUUURRRRRUUUURUUUUUURUUURRRUUURRRRRRUUUURRRRRURRRRRUURRUURRRRRURRURRURRRRRRDDDDDRRRRRRRDDDRDRDRDRDRDRDRRRRDDDRRDDDRRRDDDDDDDDDDDRRRRRRRRD

Finally, we can classify all remaining castles as variations on convex castles. To construct variations on castles, we look for runs of RRRs of length 3 or more. Each pair of Rs creates a slot for additional U or D moves, with long runs of Rs creating many slots and many possible castle variations.

For example, suppose we had a castle that began like this:

UUUURRRRRRUU

This string of Rs creates places where the castle could go. Assuming the maximum height the castle can reach is 6, we can construct variations by inserting Ds and Us in-between pairs of Rs. Note that we MUST insert Ds first; if we insert Us first, we will construct a duplicate castle variation that would be covered by another convex castle. We must also insert Ds and Us in pairs, so as to keep the total height change 0. Last, we cannot insert Ds and Us next to one another. Here are a few example castle variations:

UUUURDRURDRURRUU

UUUURDDRDRUURURRUU

UUUURDRUURDRRRUU

UUUURDRURURDRRUU

UUUURDRUURRRDRUU

UUUURRDDRUUURRDRUU

and so on...

In the next section we will show how to enumerate all convex castles, and given a convex castle, how to enumerate all variations. This will allow us to count the number of castles.

One last convenient property of this representation is the fact that each D move completes a new block, so checking if there are an even number of blocks is as easy as checking if the number of Ds is even.

Enumeration of Castles

Now that we have the U/R/D representation of a castle, we can enumerate castles by enumerating strings of U/R/D that satisfy the conditions of Problem 502. Particularly, the requirement that castles contain an even number of blocks.

Procedure

To assemble a castle of width W and height H, we use a three-step process:

Start with a bare minimum string of U/R/D. Explanation of a bare minimum string is given below.
Insert the number of remaining Rs into the castle string needed to make the castle have width W. (This is the number of CONVEX CASTLES.)
Insert pairs of U/D or D/U, separated by at least one R.

Step 1 Bare Minimum String

The bare minimum string consists of the minimum number of Us and Ds that the castle is required to have. For example, for castles of height 4 and width 5, the bare minimum string would be 4 Us, 4 Ds, and one R to separate them, since we know Us and Ds must be separated by at least one R:

U U U U R D D D D

However, the case where the height is odd requires a different bare minimum string, because the number of rows is odd, meaning the bare minimum string will not satisfy the requirement that castles must have an even number of blocks (an even number of Ds).

To get around that, we insert an extra U and an extra D, and two extra Rs to separate them. For example, for castles of height 5 and width 10, the bare minimum string would be:

U U U U U R D R U R D D D D D

Step 2 Enumerating Convex Castles

Starting with the bare minimum string, enumerating convex castles boils down to inserting W-1 different Rs into the bare minimum string.

There are H-1 possible slots between each U character, since the castle string can't start with an R. There are another H-1 possible slots between each D character, since the castle string can't end with a D. And last, there is one slot between the string of Us and string of Ds, where there is already at least one R - more Rs can be added there as well.

The problem of counting the number of ways to insert W - 1 Rs into 2(H - 1) + 1 partitions is equivalent to the "stars and bars" problem: given a number of objects (stars), how many ways can you separate them into n partitions, using n-1 bars?

*****|||

Now, the formula for counting the number of ways of partitioning s objects using n partitions, or n-1 bars, is

$C(n-1+s,r)$

where C is the choose function:

$C(m,k)={\dfrac {m!}{k!(m-k)!}}$

Now, the count of convex castles (CCC) can be written as a formula:

${\mbox{CCC}}=C(2(H-1)+W-1,W-1)=C(2H+W-3,W-1)$

For example, for castles of height 4 and width 5, we start with the bare minimum string:

U U U U R D D D D

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:

${\mbox{CCC}}=C(2H+W-3,W-1)=C(2*4+5-3,5-1)=C(10,4)=210$

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

References

File: step polyominos, motzkin numbers, and bessel functions: File:PolyominosMotzkinBessel.pdf

File: a method for the enumeration of classes of column-convex polygons File:EnumerationColumnConvexPolynomials.pdf

File: construction procedure for parallel polyomino transfer matrices File:PolyominoTransferMatrix.pdf

Flags

Project Euler/502

From charlesreid1

Contents