From charlesreid1

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

Let's talk through the solution approach for this problem.

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. The number of configurations for a castle with a width and height on the order of 10 is given in the original problem as F(13,10) = 3729050610636. The width and height of one of the three problems is a TRILLION, so just constructing and storing one single castle is going to take you oodles of memory and a solid minute of computation time. The larger castle configuration counts are MOD A BILLION, which means they're so big that you have to wrap back around when you get to a billion, which means they're going to be mind-bogglingly large.

So, manual enumeration of castles is completely out.

Instead of counting castles, you should generate castles. Specifically, you should generate them using generating functions. 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.

Polyominoes

We can refer to the literature on polyominoes for inspiration on how to formulate a mathematical model for our castles. Let's start with some definitions.

We define a polyomino to be a two-dimensional shape formed by contiguous unit square tiles aligned on a 2D grid. We keep the definition general to keep it as flexible as possible. Those who are familiar with Tetris or John Conway's Game of Life will have already seen polyominoes in other contexts. Here's an example:

Polyomino1.png

We can define different rules governing the construction of polyominoes, and these will lead to different possible shapes. For example, if we set no rules besides the fact that all squares are contiguous, we end up with a huge variety of shapes, so huge that it is computationally extremely difficult to enumerate for large numbers of tiles (large means, >50). However, we might set other rules, like saying a polyomino must have at least one column that is the height of a single square, or we may prohibit overhangs, or we may require the area to be an even number...

Polyomino Rules

Many of these have echoes of 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.

When we break down each of these restrictions, they are written in terms of the "castle" and "block" objects defined in the problem but we can translate them into restrictions on our polyominoes. For example, let's take Rule 6, which states the castle must be made from an even number of blocks.

Steps-Based Approach

Here, we describe one way of describing the problem: we can think of a polynomino castle as being constructed by a series of up/down steps and left-right steps, starting at the lower left corner of the castle and marching to the right (to form the top of the castle), then marching back along the bottom of the castle.

To count the number of blocks in a given row of a castle, we can draw a horizontal line through the entire row, and count the number of vertical block ends are intersected. That number is twice the number of blocks in the row. So, the key to counting the number of blocks is counting the number of vertical up or down steps. Any pair of up/down steps will always form a block - due to Rule 3. Counting the number of up and down steps, together with the (known) number of left/right steps, which is always twice the width, we are looking at the perimeter of the polyomino:


P = 2W + US + DS

where US is number of up steps and DS is number of down steps. Number of blocks is given by:


N_{b} = \dfrac{DS + US}{2}

Therefore if we want the number of blocks to be an even number 2k, where k is an arbitrary integer,


2k = \dfrac{DS+US}{2}


DS + US = 4k

and because the number of up and down steps must be equal to form a closed shape,


2VS = 4k \rightarrow VS = 2k

where VS is number of vertical steps. This means our castle polyominoes must take an even number of vertical steps up/down.

This requires the generating function (our mathematical model for the castle polyomino) to account for the number of vertical steps that a given polyomino takes to construct. We must decide (implicitly, using a combinatorics formula, of course) at the very last step, whether a particular configuration that's been constructed (which may contain multiple rows with an odd number of vertical steps) leads to an even overall number of vertical steps or not.

Definition of a polyomino

The zoo of polyominoes

Variations on rules and constraints lead to different formulations and generating functions

Generating functions ultimately give you a polynomial whose coefficients will enumerate your arrangements

Alternative Approach: Binary Strings

An alternative representation of a castle is to use a binary string. Specifically, a column-wise representation of the castle will create a set of W blocks, each block of length H.

Let's look at an example:

PE502.png

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 hte 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 2 1 3

Add a zero to the front and end:

0 2 3 2 1 3 0

Now compute the difference between each entry:

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

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


5 = (-1) + (-1) + (-3)

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


Related

Polyominoes

Dyck Words

Lattice Paths

Combinatorics

Flags