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
