Wow! Thanks to Michael, Stefan, and Henry for the various solutions to my
tiling problem.
Henry's explanation using tetrahedral numbers was quite interesting, and
was easier for me to parse.
I'm still not very good at unravelling lengthy tacit code, and Henry's
extensive comments
made his process very clear.
Skip
Skip Cave
Cave Consulting LLC
On Thu, May 28, 2020 at 12:43 PM Henry Rich <henryhr...@gmail.com> wrote:
> I put 2 lines of commentary for every line of J I write. I should do
> the same in posts to the Forum. Here's my solution:
>
> NB. tetrahedral number y in x dimensions (generalization of triangle
> numbers)
> tetra =: ([ ! <:@:+)
>
> NB. number of ways to position y intervals of length 2 in length x
> NB. Think of it as deciding how many spaces to leave in front of each
> tile (could be 0).
> NB. This is equivalent to finding the number of ways to select y
> nonnegative
> NB. integers that add up to no more than (y-2x), which is the same as the
> NB. number of ways to select up to y positive integers that add to no
> more than (y-2x+1),
> NB. which is a tetrahedral number of dimension y.
> nhoriz =: ] tetra >:@:(- +:)
>
> NB. number of ways to position y tiles vertically. Each has 2 positions.
> nvert =: 2&^
>
> NB. number of ways to place y tiles in a 3-by-x grid. The dimensions
> are independent.
> npos =: nvert@] * nhoriz
>
> NB. number of ways to place up to y tiles in a 3-by-x grid. Add up for
> each number
> NB. of tiles. 0 is a possible number, meaning all 1x1s were used.
> totalpos =: +/ @: (npos i.@>:)
>
> 8 totalpos 4
> 171
> 12 totalpos 4
> 1995
> 12 totalpos 6
> 2731
>
> Henry Rich
>
> On 5/28/2020 12:44 PM, 'Michael Day' via Programming wrote:
> > Thanks - and Thank Goodness you arrive at the same result, for 3x8!
> >
> > I considered programming the cases for 1 and 2 2-tiles, but also
> > considered the
> >
> > mini-essay sufficient to demonstrate them for Skip!
> >
> > Cheers,
> >
> > Mike
> >
> >
> >
> > On 28/05/2020 11:14, Stefan Baumann wrote:
> >> 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 <
> >> programm...@jsoftware.com> 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 <
> >>>>> 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
> >>>
> >> ----------------------------------------------------------------------
> >> For information about J forums see http://www.jsoftware.com/forums.htm
> >
>
>
> --
> This email has been checked for viruses by AVG.
> https://www.avg.com
>
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
