// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (5 votes, average: 5.00 out of 5)
Loading...

Project Euler Solutions

Project Euler 174 Solution

Project Euler 174 Solution

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.

Project Euler 174 Solution

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?

Analysis

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 Solution

Runs < 0.001 seconds in Python 2.7.
#Project Euler Problem 174

L = 1000000
N = [0]*(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)
download arrowUse this link to get the Project Euler 174 Solution Python 2.7 source.

Answer

Slowly 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.
|209566|

Afterthoughts

Project Euler 174 Solution last updated

Discussion

No comments yet.

Post a comment