Project Euler/502: Difference between revisions
From charlesreid1
No edit summary |
No edit summary |
||
| Line 10: | Line 10: | ||
1 + (2**W - 1) ^ (H - 1) | 1 + (2**W - 1) ^ (H - 1) | ||
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]] | |||
Revision as of 00:07, 13 July 2017
Generating polynomials
Recursion relations
Straight away you can see that something like recursion or an enumeration of every castle is simply impossible, given the size of the grids we're talking about: a trillion columns. There's no hope of actually building any of those grids.
So, we need to break this problem down into something we can handle: numbers.
Let's start with the grid. Each castle lives on a grid, and the rules the castle follow are grid-based. Each row of a castle can be represented using a binary system of 0s and 1s, so the rules can be translated into number-based rules. A castle, then, becomes a sequence of integers that follow certain rules.
1 + (2**W - 1) ^ (H - 1)
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
