[Jprogramming] Reshape error?

Wed May 27 10:56:55 UTC 2020

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 <
>> programming at 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 <skip at 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
>