{"id":1815,"date":"2024-01-02T15:59:01","date_gmt":"2024-01-02T22:59:01","guid":{"rendered":"https:\/\/www.coastalvectors.com\/blog\/?p=1815"},"modified":"2024-01-02T15:59:01","modified_gmt":"2024-01-02T22:59:01","slug":"project-euler-174","status":"publish","type":"post","link":"https:\/\/www.coastalvectors.com\/blog\/2024\/01\/project-euler-174\/","title":{"rendered":"Project Euler 174"},"content":{"rendered":"

\"\"<\/a><\/p>\n

We shall define a square lamina to be a square outline with a square “hole” so that the shape possesses vertical and horizontal symmetry.<\/p>\n

Given eight tiles it is possible to form a lamina in only one way: 3 \u00d7 3 square with a 1 \u00d7 1 hole in the middle. However, using thirty-two tiles it is possible to form two distinct laminae. \"\"<\/a>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).<\/p>\n

Let N(n) be the number of t <= 1000000 such that t is type L(n); for example, N(15) = 832.<\/p>\n

What is sum of N(n) for n=1 to 10?<\/p><\/blockquote>\n

This question turned out to be fairly straight forward, and is solvable using a brute force method.<\/p>\n

Basically, we want to arrange tiles in laminae that are symmetrical, and don’t use more than 1,000,000 tiles. The largest lamina we can arrange would then be 250,000 tiles per side, with a wall thickness of 1.<\/p>\n

The way I set this up was to iterate through all lamina side lengths (L) from 3 to our limit, 250,000. Then, for each, iterate for different hole sizes (H) in the middle from L\u20132 down to 1. (The evenness of L and H have to match.)<\/p>\n

Calculating the number of tiles is an easy prospect; t = L\u00b2 \u2013 H\u00b2. A dictionary then keeps track of how many tiles are used for each combination. Once we’ve brute forced all the combinations, look through the dictionary to count up all the tile values that have 10 solutions or less!<\/p>\n

let history = {};\r\nlet limit = 1000000;\r\n\r\nfor (let L=3; L<250000; L++){\r\n    let L2 = L * L;\r\n    \/\/ Hole (H) size must be at least 1, smaller than or equal to l-2\r\n    for (let H=0; H<=L-2; H++){\r\n        \/\/ Calculate number of tiles (t) in lamina\r\n        let t = L2 - (H * H);\r\n\r\n        \/\/ L and H evenness must match\r\n        if (L%2 != H%2) continue;\r\n        \r\n        \/\/ Ignore answers over limit\r\n        if (t > limit) continue;\r\n\r\n        \/\/ Store result in history\r\n        if (history[t] == undefined)\r\n            history[t] = [];\r\n\r\n        history[t].push(L);\r\n    }\r\n}\r\n\r\nlet count = 0\r\nfor (let i in history)\r\n    if (history[i].length <= 10)\r\n        count++;\r\n\r\nconsole.log(count);\r\n<\/code><\/pre>\n
The first time I ran this, it was much slower than anticipated. I let it run overnight, and was happy to see the correct result when I checked on it the next day. I wondered what I needed to optimize to make it run better. It turns out that I had typed the upper limit, L, as 2,500,000! By decreasing that to the proper value, that reduced the compute time to 17 seconds.<\/p>\n
I was able to find one more low-hanging optimization opportunity. By iterating through the H values from largest to smallest, the number of tiles, t, would increase. Once that value got over the 1,000,000 limit, I can break out of the loop, and go to the next value of L. This saves a lot of time computing out of bounds answers!<\/p>\n
for (let L=3; L<250000; L++){\r\n    let L2 = L * L;\r\n    \/\/ Hole (H) size must be at least 1, smaller than or equal to l-2\r\n    for (let H=L-2; H>1; H-=2){\r\n        \/\/ Calculate number of tiles (t) in lamina\r\n        let t = L2 - (H * H);\r\n\r\n        \/\/ Break once we get over limit\r\n        if (t > limit) break;\r\n\r\n        \/\/ Store result in history\r\n        if (history[t] == undefined)\r\n            history[t] = [];\r\n\r\n        history[t].push(L); \r\n    } \r\n}\r\n<\/code><\/pre>\n
This optimization pushed the compute time down to .278s! That’s a very reasonable time for Project Euler.<\/p>\n","protected":false},"excerpt":{"rendered":"
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 \u00d7 3 square with a 1 \u00d7 1 hole in the middle. However, using thirty-two tiles … Continue reading Project Euler 174<\/span><\/a><\/p>\n","protected":false},"author":4,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[8],"tags":[],"class_list":["post-1815","post","type-post","status-publish","format-standard","hentry","category-programming"],"_links":{"self":[{"href":"https:\/\/www.coastalvectors.com\/blog\/wp-json\/wp\/v2\/posts\/1815","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.coastalvectors.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.coastalvectors.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.coastalvectors.com\/blog\/wp-json\/wp\/v2\/users\/4"}],"replies":[{"embeddable":true,"href":"https:\/\/www.coastalvectors.com\/blog\/wp-json\/wp\/v2\/comments?post=1815"}],"version-history":[{"count":4,"href":"https:\/\/www.coastalvectors.com\/blog\/wp-json\/wp\/v2\/posts\/1815\/revisions"}],"predecessor-version":[{"id":1820,"href":"https:\/\/www.coastalvectors.com\/blog\/wp-json\/wp\/v2\/posts\/1815\/revisions\/1820"}],"wp:attachment":[{"href":"https:\/\/www.coastalvectors.com\/blog\/wp-json\/wp\/v2\/media?parent=1815"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.coastalvectors.com\/blog\/wp-json\/wp\/v2\/categories?post=1815"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.coastalvectors.com\/blog\/wp-json\/wp\/v2\/tags?post=1815"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}