Project Euler/502: Difference between revisions
From charlesreid1
| Line 23: | Line 23: | ||
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: | 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: | ||
[[ | [[Image:Polyomino1.png|500px]] | ||
Revision as of 12:09, 18 July 2017
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:
Definition of a polyomino
The zoo of polyominoes
Variations on rules and constraints lead to different formulations and generating functions
Ultimately, you wind up with a polynomial whose coefficients will enumerate your arrangements
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
