Skip, Your 3x8 grid gives an area of 24. This sounds one could use the coin change problem/approach or partition of the integer and dynamic prigramming to solve this.
Here's a link: https://www.youtube.com/watch?v=DJ4a7cmjZY0&ab_channel=BackToBackSWE https://www.youtube.com/watch?v=_fgjrs570YE&ab_channel=TusharRoy-CodingMadeSimple Dale On Tue, May 26, 2020this, 8:28 PM Skip Cave <s...@caveconsulting.com> wrote: > Actually the tiling problem I was working on is more complex than my basic > explanation. > You have a large pile of 1x1 tiles and a pile of 2x2 tiles, as many as you > need. The question is: > How many ways are there to tile a 3x8 grid completely, using 1x1 & 2x2 > tiles. > Of course, you can cover the whole grid with 24-1x1 tiles, which is one way > to tile the grid. > The most 2x2s you can get in the grid will be 4, but then you must fill up > the remaining holes with 8-1x1s > However, there are several ways to arrange the 4-2x2s, along with the > 8-1x1s. > If you only use 1, 2, or 3 of the 4x4s, the number of tiling possibilities > goes up dramatically. > The answer is a count of all the ways. That is the problem. > > Skip > > > > On Tue, May 26, 2020 at 5:58 PM 'Michael Day' via Programming < > programm...@jsoftware.com> wrote: > > > In that case, it seems a bit of over-kill to use 2^24, > > > > In your 3x8 grid, you can fit exactly 4 2x2 tiles in a row. > > > > (It's surely equivalent to placing 4 2x1 tiles in a 3x4 grid.) > > > > To make the graphics easier, I'll consider 4 1x2 tiles in a vertical 4x3 > > grid. > > > > Each tile "[]" can then be "left" or "right", so there are 2^4 > > patterns: (best in fixed width!) > > > > [m =: 4#,:'.[]' NB. Each tile is [], spaces are .... > > .[] > > .[] > > .[] > > .[] > > > > 0 1 0 1 |."0 1 m NB. two patterns out of the 16 > > .[] > > []. > > .[] > > []. > > 0 1 1 1 |."0 1 m > > .[] > > []. > > []. > > []. > > > > So #: i. 16 will generate all patterns. > > > > Or have I missed something? > > > > Mike > > > > > > On 26/05/2020 22:14, Skip Cave wrote: > > > Ooops. You are right. I mis-copied the last dimension. :-( > > > Sorry for the confusion. > > > > > > The problem I was working on, was to try to find all the ways to place > > 2"x > > > 2" tiles non-overlapping on a 3"x 8" grid. > > > I know there's a technique called linear difference equations that can > > > solve this problem, but I wanted to try to > > > model it by brute force. So I generated all 16777216 possible 3x8 grids > > of > > > 1s & 0s. > > > > > > odo=:#: i.@(*/) > > > > > > $n=.odo 24#2 > > > > > > 16777216 24 > > > > > > $ns=.16777216 3 8$,n > > > > > > 16777216 3 8 > > > > > > _3{.ns > > > > > > 1 1 1 1 1 1 1 1 > > > > > > 1 1 1 1 1 1 1 1 > > > > > > 1 1 1 1 1 1 0 1 > > > > > > > > > 1 1 1 1 1 1 1 1 > > > > > > 1 1 1 1 1 1 1 1 > > > > > > 1 1 1 1 1 1 1 0 > > > > > > > > > 1 1 1 1 1 1 1 1 > > > > > > 1 1 1 1 1 1 1 1 > > > > > > 1 1 1 1 1 1 1 1 > > > > > > That fixed my problem, with the right dimensions. Now comes the hard > > part. > > > The problem now is to find all the 3x8 grids that only > > > > > > have 2x2 blocks of non-overlapping 1s in them, and no isolated 1s or > > > non-2x2 groups of 1s. > > > > > > Skip > > > > > > > > > On Tue, May 26, 2020 at 12:34 PM Skip Cave <s...@caveconsulting.com> > > wrote: > > > > > >> odo=:#: i.@(*/) > > >> > > >> $n=.odo 24#2 > > >> > > >> 16777216 24 > > >> > > >> _3{. n > > >> > > >> 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 > > >> > > >> 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 > > >> > > >> 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 > > >> > > >> _48{. ,n > > >> > > >> 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 > 1 > > 1 > > >> 1 1 1 1 1 1 1 1 1 1 1 > > >> > > >> $ns=.16777224 3 8$,n > > >> > > >> 16777224 3 8 > > >> > > >> _3{.ns > > >> > > >> 0 0 0 0 0 0 0 0 > > >> > > >> 0 0 0 0 0 0 0 0 > > >> > > >> 0 0 0 0 0 1 0 1 > > >> > > >> > > >> 0 0 0 0 0 0 0 0 > > >> > > >> 0 0 0 0 0 0 0 0 > > >> > > >> 0 0 0 0 0 1 1 0 > > >> > > >> > > >> 0 0 0 0 0 0 0 0 > > >> > > >> 0 0 0 0 0 0 0 0 > > >> > > >> 0 0 0 0 0 1 1 1 > > >> > > >> > > >> Shouldn't the last few 3x8 arrays in ns be almost all ones, and the > last > > >> array definitely all ones? > > >> > > >> > > >> > > >> Skip Cave > > >> Cave Consulting LLC > > >> > > > ---------------------------------------------------------------------- > > > For information about J forums see http://www.jsoftware.com/forums.htm > > > > -- > > This email has been checked for viruses by Avast antivirus software. > > https://www.avast.com/antivirus > > > > ---------------------------------------------------------------------- > > For information about J forums see http://www.jsoftware.com/forums.htm > > > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
