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
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 ==> 28 for both
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
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?!
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 <
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
--
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
