Trying to directly calculate the number of solutions and ending up up with this - x length of grid, y number of 2-tiles:
n=: 4 : '(2^y)* # ([: ~.@,/ [: |:"2 +"_ 1)/ (] $~ (x-2*y),#) e.@i. >: y' Starts with an identity matrix corresponding to the possible gaps next to the 2-tiles and tries to find the number of ways filling the gaps with 1-tile columns. It doesn't work for when the 2 tiles span all the columns so to get your result you have to: (2&^ + [: +/ (8&n"0)@i.) 4 171 Ciao. Stefan. On Wed, May 27, 2020 at 12:57 PM 'Michael Day' via Programming < [email protected]> wrote: > Another "oops" - main analysis is ok below - I'll correct a few entries > in line > > > On 27/05/2020 08:13, 'Michael Day' via Programming wrote: > > OK, thanks - more interesting! > > > > So youcan regard this as 5 sub-problems - ie using 0 1 2 3 or 4 2x2s. > > It's not quite clear > > > > whether you need to identify the different tiles or not, eg by colour > > or name or number. > > > > If you don't need to do so, then sub-problems 0 and 4 are still trivial. > > > > 0 - fill all 24 slots with 1x1s > ===> 1 solution for 0 2x2s > > > > 4 - use 4 2x2s and 8 1x1s, as in my graphic, earlier, with 4 "[]" > > symbols, and 8 "."s > > > > > The other 3 cases are somewhat more complicated, but I think it's > > still a matter of > > > > placing the 2x2s and regarding the 1x1s as space-fillers. > > > > [As for the other 3: ] > > > > In a 3 x w grid, there are 2 x (w-1) placings for just 1 2x2 tile: > > > > 1 - there are 14 = 2x7 possible locations for 1 2x2 tile > > > > 2 - If the first 2x2 tile is in columns 0 1, there are 10=2x5 > > placings for the 2nd 2x2, > > > > so 20 = 2x2x5 for both, > > > > 1st in cols 1 2, 8=2x4 for 2nd ==> 16 > > > > ... > > > > 1st in 4 5, 2nd in 67 ==> 4 > > > > ... so 60 ways for 1 2x2 tile > NO - 60 ways for 2 2x2 tiles ! > > > > 3 - 1st in cols 0 1, 2nd in cols 2 3, 3rd in 6 possible places ==> > > 2x2x6=24 > > > > 2nd in 3 4, 3rd in 4 places ==> 16 > > > > 4 5, 3rd in 2 ==> 8 > > > > so 48 tilings with first tile in cols 0 1. > > > > 1st in 1 2, 3 4 4 ==> > > > > .... > > > > This table encapsulates the possible triples of starting columns: > > > > (;~$) (#~"1 */@:(1<2-~/\]))0 2 4 + |:3#.inv i.3^3 > > +----+-------------------+ > > |3 10|0 0 0 0 0 0 1 1 1 2| > > | |2 2 2 3 3 4 3 3 4 4| > > | |4 5 6 5 6 6 5 6 6 6| > > +----+-------------------+ > > > > So there are 80 = 2x2x2x10 placings for 3 2x2 tiles?! > > > To summarise: > +---------------+-+--+--+--+--+-----+ > |no of 2x2 tiles|0|1 |2 |3 |4 |total| > +---------------+-+--+--+--+--+-----+ > |no of solutions|1|14|60|80|16|171 | > +---------------+-+--+--+--+--+-----+ > > > Cheers, > > > > Mike > > > > > > > > On 27/05/2020 01:28, Skip Cave 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 < > >> [email protected]> 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 <[email protected]> > >>> 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 > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
