7
\$\begingroup\$

Challenge description

Let's define an W x H grid as a two-dimensional array of length H whose each subarray is of length W. Example: a 2x3 grid (. character used as a blank):

..
..
..

A unit is a single point of a grid. A block is either a single unit or a set of contiguous units (meaning each unit of a block has at least another one next to, above or below it). In the 10x10 grid below there are 4 blocks (units represented by X's):

........X.   ........1.
..X.......   ..2.......
..X.......   ..2.......
..X.......   ..2.......
.......X..   .......3..
.......XX.   .......33.
.......XX.   .......33.
..X.......   ..4.......
..XX..X...   ..44..4...
...XXXX...   ...4444...

Two blocks are distinct if either their positions in the grid or the number of blocks they consist of are different. In the 10x10 grid below there are 5 blocks (they're all 2x2 squares, but their positions are different, therefore they're distinct):

..........   ..........
.XX....XX.   .11....22.
.XX....XX.   .11....22.
..........   ..........
.......XX.   .......33.
.......XX.   .......33.
....XX....   ....44....
....XX....   ....44....
XX........   55........
XX........   55........

Given two integers W and H (W, H > 0), calculate the number of distinct blocks that can be constructed within a W x H grid.

Sample inputs / outputs

(1, 1) -> 1     | only a 1x1 block can be constructed
(1, 2) -> 3     | two 1x1 blocks, and one 1x2 block
(2, 2) -> 13
(3, 3) -> 218
(4, 4) -> 11506

Notes

  • Remember that this is a challenge, so make your code as short as possible!
  • Relevant sequences: A059525, A059020
\$\endgroup\$
  • 1
    \$\begingroup\$ To clarify: are we supposed to compute the total number of 4-way connected non-empty subsets of the W x H grid? \$\endgroup\$ – Zgarb Aug 5 '16 at 12:37
  • \$\begingroup\$ Yes, I just realized that this whole challenge could be worded much more concisely, but that's the gist. \$\endgroup\$ – shooqie Aug 5 '16 at 12:44
  • \$\begingroup\$ @shooqie The gist of what? \$\endgroup\$ – mınxomaτ Aug 5 '16 at 12:46
  • 2
    \$\begingroup\$ Of @Zgarb just said, it's an expression... \$\endgroup\$ – shooqie Aug 5 '16 at 12:47
  • 1
    \$\begingroup\$ Two blocks are distinct if both their positions in the grid and the number of blocks they consist of are different. I think you mean an either/or rather than a both/and here. Else, the sentence doesn't match the example with the 5 2x2 blocks. Also, it would probably be a good thing if you explicitly stated that the blocks for counting aren't all placed on the grid at the same time. That's implied by your (1,2) example, but not explicit. With that being the case, this is very similar to the recent count-the-rectangle challenges. \$\endgroup\$ – AdmBorkBork Aug 5 '16 at 13:09
3
\$\begingroup\$

Python 2, 208 184 169 167 163 bytes

w,h=input()
def f(x):global g;o=g;g&=~2**x;o>g>[x/w==(x+s)/w<f(x+s)or-1<x/w+s<h<f(x+s*w)for s in[-1,1]]
n=i=1<<w*h
while i:g=i=i-1;f(len(bin(g))-3);n-=g>0
print~-n
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.