Rectangles in cross-hatched grids
Problem 147
In a 3x2 cross-hatched grid, a total of 37 different rectangles could be situated within that grid as indicated in the sketch.
There are 5 grids smaller than 3x2, vertical and horizontal
dimensions being important, i.e. 1x1, 2x1, 3x1, 1x2 and 2x2. If each of
them is cross-hatched, the following number of different rectangles
could be situated within those smaller grids:
Adding those to the 37 of the 3x2 grid, a total of 72 different rectangles could be situated within 3x2 and smaller grids.
How many different rectangles could be situated within 47x43 and smaller grids?
Solution
The normal rectangles that are parallel to the borders are easy to count. For the 'diagonal rectangles', it is relatively straight forward to figure out the pattern for square ones (1*1, 2*2). It's the counting of the non-square 'diagonal rectangles' that is the trickiest.
The first step is given the width (m) and height (n) of the box, work out a list of 'max length' of 'diagonal rectangles' with a width of 1 block, starting from top left corner to bottom right corner.
For example, for m = 7, n = 5, we have the list as [2, 4, 6, 8, 9, 9, 8, 6, 4, 2]
Assume m >= n, the general pattern is [2, 4, ... 2(n-1), 2n - 1, ..., 2n - 1, 2(n-1), ..., 4, 2]. There are (m - n) of the (2n - 1) item in the middle. Apparently, when m=n, there is no (2n - 1) item.
The key of this problem is how to calculate the max length of any consecutive blocks that can form a rectangle. Let's define it as M(consecutive_blocks)
For example, for M([2, 4]) = 2. For M([6, 8, 9, 9]) = 6.
By taking advantage of symmetry, there is no need to work out all the cases. Assuming the width of the block is always less than the M(consecutive_blocks), we don't need to consider [4, 6, 8, 8, 6] because the width of [4, 6, 8, 8, 6] = 5, which is greater than M([4, 6, 8, 8, 6]) = 4. Also M([8, 9, 9, 8, 6]) is the same as M([6, 8, 9, 9, 8]).
Start with 'max length' being the first item of the list, iterate over the list, how far can it go before the 'max length' starts to decrease?
In this example, we can see that M([6]) = 6, M([6, 8]) = 6, M([6, 8, 9]) = 6, M([6, 8, 9, 9]) = 6, but the next one, M([6, 8, 9, 9, 8]) = 5. Since m >= n, the length of the 'L' shape is fixed, which is 2n - 1. So the max length can go (2n - 1 - first_item) steps before it starts to decease.
Next question is deceasing by 1 or 2? It can be proved that as long as the first item is less than or equal to the last item, it's always decreasing by 1.
Once we know the value of M(consecutive_blocks), we can easily calculate the number of full-width non-square rectangles (only consider length > width) that can be situated in the blocks.
For example, if M(cb) = 6 and width(cb) = 3, we just calculate the number of 4*3, 5*3, 6*3 rectangles, which is 3+2+1=6.
Multiply this number by 2 (due to symmetry), we can get the total number of non-square 'diagonal rectangles
Finally, let's prove 'as long as the first item is less than or equal to the last item, it's always decreasing by 1.'
Suppose m >= n, then b >= a, we move the line P toward bottom right, when the lower end hits point X, the 'max length' will start to decease, but until it coincides line R, it deceases by 1 unit. After that, it decreases by 2 units. Line Q which is of the same length of line P, sits between line P and Line R. So between line P and line Q, the 'max length' can decrease by 1 unit at most.
https://github.com/sunmingtao/sample-code/blob/master/python/projecteuler/p147.py
| 1x1 | 1 |
| 2x1 | 4 |
| 3x1 | 8 |
| 1x2 | 4 |
| 2x2 | 18 |
How many different rectangles could be situated within 47x43 and smaller grids?
Solution
The normal rectangles that are parallel to the borders are easy to count. For the 'diagonal rectangles', it is relatively straight forward to figure out the pattern for square ones (1*1, 2*2). It's the counting of the non-square 'diagonal rectangles' that is the trickiest.
The first step is given the width (m) and height (n) of the box, work out a list of 'max length' of 'diagonal rectangles' with a width of 1 block, starting from top left corner to bottom right corner.
For example, for m = 7, n = 5, we have the list as [2, 4, 6, 8, 9, 9, 8, 6, 4, 2]
Assume m >= n, the general pattern is [2, 4, ... 2(n-1), 2n - 1, ..., 2n - 1, 2(n-1), ..., 4, 2]. There are (m - n) of the (2n - 1) item in the middle. Apparently, when m=n, there is no (2n - 1) item.
The key of this problem is how to calculate the max length of any consecutive blocks that can form a rectangle. Let's define it as M(consecutive_blocks)
For example, for M([2, 4]) = 2. For M([6, 8, 9, 9]) = 6.
By taking advantage of symmetry, there is no need to work out all the cases. Assuming the width of the block is always less than the M(consecutive_blocks), we don't need to consider [4, 6, 8, 8, 6] because the width of [4, 6, 8, 8, 6] = 5, which is greater than M([4, 6, 8, 8, 6]) = 4. Also M([8, 9, 9, 8, 6]) is the same as M([6, 8, 9, 9, 8]).
Start with 'max length' being the first item of the list, iterate over the list, how far can it go before the 'max length' starts to decrease?
Next question is deceasing by 1 or 2? It can be proved that as long as the first item is less than or equal to the last item, it's always decreasing by 1.
Once we know the value of M(consecutive_blocks), we can easily calculate the number of full-width non-square rectangles (only consider length > width) that can be situated in the blocks.
For example, if M(cb) = 6 and width(cb) = 3, we just calculate the number of 4*3, 5*3, 6*3 rectangles, which is 3+2+1=6.
Multiply this number by 2 (due to symmetry), we can get the total number of non-square 'diagonal rectangles
Finally, let's prove 'as long as the first item is less than or equal to the last item, it's always decreasing by 1.'
Suppose m >= n, then b >= a, we move the line P toward bottom right, when the lower end hits point X, the 'max length' will start to decease, but until it coincides line R, it deceases by 1 unit. After that, it decreases by 2 units. Line Q which is of the same length of line P, sits between line P and Line R. So between line P and line Q, the 'max length' can decrease by 1 unit at most.
https://github.com/sunmingtao/sample-code/blob/master/python/projecteuler/p147.py
No comments:
Post a Comment