Project Euler 174: Counting the number of "hollow" square laminae that can form one, two, three, ... distinct arrangements.
We shall define a square lamina to be a square outline with a square "hole" so that the shape possesses vertical and horizontal symmetry.
Given eight tiles it is possible to form a lamina in only one way: 3×3 square with a 1×1 hole in the middle. However, using thirty-two tiles it is possible to form two distinct laminae.
If t represents the number of tiles used, we shall say that t = 8 is type L(1) and t = 32 is type L(2).
Let N(n) be the number of t ≤ 1000000 such that t is type L(n); for example, N(15) = 832.
What is ∑ N(n) for 1 ≤ n ≤ 10?
Wanting a solution that could solve both problem 173 and 174 we decided that in a couple of minutes we could put something together that would run quickly. Instead of determining factors for each iteration we just modeled the building of the lamina which is faster than a solution counting even factors. In fact when the scale increases to, say 10,000,000 this program will outperform most others.
One drawback is the use of memory, but for the sake of development time it was of little consequence.
Project Euler 174 SolutionRuns < 0.001 seconds in Python 2.7.
#Project Euler Problem 174 L = 1000000 N = *(L+1) for h in range(1, L//4): nt = h*4 + 4 sumx = nt while sumx <= L: N[sumx] += 1 nt = nt + 8 sumx += nt print "Project Euler 174 Solution =", sum(1 <= n <= 10 for n in N)Use this link to get the Project Euler 174 Solution Python 2.7 source.
AnswerSlowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose define to reveal the answer.
- See also, Project Euler 173 Solution: Using up to one million tiles find many different "hollow" square laminae can be formed.