stevan apter — 2005-03-26 15:40:31

in case some of you missed it, this one's fun:

http://developers.slashdot.org/article.pl?sid=05/03/14/2258219&tid=156&tid=8

from the author's description:

----------------------------------

The garden layout problem is as follows:

Given a garden laid out on an mxn grid, you must place "Planted" and "Empty" cells
on the grid so that you can reach each Planted cell while standing in an Empty cell.
In other words, for each Planted cell, one of its four neighbors (no diagonals) must
be Empty. Thus, you can tend your garden without ever standing in the planted areas
(which would compact the soil and potentially damage the plants that are growing
there).

Of course, you want to maximize the amount of space used for plants in the garden,
so you want to solve the above problem with the minimum number of Empty cells.

John Carter — 2005-03-30 21:55:05

On Sat, 26 Mar 2005, stevan apter wrote:

>
> in case some of you missed it, this one's fun:
>
> http://developers.slashdot.org/article.pl?sid=05/03/14/2258219&tid=156&tid=8
>
> from the author's description:
>
> ----------------------------------
>
> The garden layout problem is as follows:
>
> Given a garden laid out on an mxn grid, you must place "Planted" and "Empty" cells
> on the grid so that you can reach each Planted cell while standing in an Empty cell.
> In other words, for each Planted cell, one of its four neighbors (no diagonals) must
> be Empty. Thus, you can tend your garden without ever standing in the planted areas
> (which would compact the soil and potentially damage the plants that are growing
> there).
>
> Of course, you want to maximize the amount of space used for plants in the garden,
> so you want to solve the above problem with the minimum number of Empty cells.

I'll nibble (just a little) on this one.

It looks to be one of those things you can apply symmetry groups and group
theoretic tricks to massively decrease the space of possibilities.

For example given any mxn board, you can apply a set of symmetry
transforms (flip horizontally, flip vertically, swap planted and bare)

On an mxm board you can also add rotations.

ie. With the correct representation, you can massively decrease the size
of the problem.

ie. Half the secret to an efficient solution of this problem lies in being
able to iterate over non-duplicate layouts efficiently.

(Looking at the optimum boards, the "bare" patches are pretty sparse.
ie. I suspect one can probably at least calculate a crude lower and upper
bound on the optimum number of "bare" patches and only iterate across that
subset as well.)

ie. Most of the challenge in solving this problem lies in the analysis
before you even fire up your editor to start coding in _any_ langauge.

John Carter Phone : (64)(3) 358 6639
Tait Electronics Fax : (64)(3) 359 4632
PO Box 1645 Christchurch Email : john.carter@...
New Zealand

Refactorers do it a little better every time.

stevan apter — 2005-03-31 00:14:16

----- Original Message -----
From: "John Carter" <john.carter@...>
To: <concatenative@yahoogroups.com>
Sent: Wednesday, March 30, 2005 4:55 PM
Subject: Re: [stack] the garden problem

>
> On Sat, 26 Mar 2005, stevan apter wrote:
>
> >
> > in case some of you missed it, this one's fun:
> >
> > http://developers.slashdot.org/article.pl?sid=05/03/14/2258219&tid=156&tid=8
> >
> > from the author's description:
> >
> > ----------------------------------
> >
> > The garden layout problem is as follows:
> >
> > Given a garden laid out on an mxn grid, you must place "Planted" and "Empty" cells
> > on the grid so that you can reach each Planted cell while standing in an Empty cell.
> > In other words, for each Planted cell, one of its four neighbors (no diagonals) must
> > be Empty. Thus, you can tend your garden without ever standing in the planted areas
> > (which would compact the soil and potentially damage the plants that are growing
> > there).
> >
> > Of course, you want to maximize the amount of space used for plants in the garden,
> > so you want to solve the above problem with the minimum number of Empty cells.
>
> I'll nibble (just a little) on this one.
>
> It looks to be one of those things you can apply symmetry groups and group
> theoretic tricks to massively decrease the space of possibilities.
>
> For example given any mxn board, you can apply a set of symmetry
> transforms (flip horizontally, flip vertically, swap planted and bare)
>
> On an mxm board you can also add rotations.
>
> ie. With the correct representation, you can massively decrease the size
> of the problem.
>
> ie. Half the secret to an efficient solution of this problem lies in being
> able to iterate over non-duplicate layouts efficiently.
>
> (Looking at the optimum boards, the "bare" patches are pretty sparse.
> ie. I suspect one can probably at least calculate a crude lower and upper
> bound on the optimum number of "bare" patches and only iterate across that
> subset as well.)
>
> ie. Most of the challenge in solving this problem lies in the analysis
> before you even fire up your editor to start coding in _any_ langauge.

just so.

the current state of my k implementation is here:

http://www.nsl.com/k/garden.k

i make two assumptions:

1. a minimal solution for m rows, n cols can always be constructed
from the set of symmetrical rows of length n. for example, the
set for n = 7 is:

0 0 0 0 0 0 0
1 0 0 0 0 0 1
0 1 0 0 0 1 0
1 1 0 0 0 1 1
0 0 1 0 1 0 0
1 0 1 0 1 0 1
0 1 1 0 1 1 0
1 1 1 0 1 1 1
0 0 0 1 0 0 0
1 0 0 1 0 0 1
0 1 0 1 0 1 0
1 1 0 1 0 1 1
0 0 1 1 1 0 0
1 0 1 1 1 0 1
0 1 1 1 1 1 0
1 1 1 1 1 1 1

2. we can further reduce the search space by considering only
those rows containing at least k 1s, where k is some
function of n s.t. 1 < k < n. for example, the set above
is reduced to:

1 1 0 0 0 1 1
1 0 1 0 1 0 1
0 1 1 0 1 1 0
1 1 1 0 1 1 1
1 1 0 1 0 1 1
1 0 1 1 1 0 1
0 1 1 1 1 1 0

which finds two solutions:

1 1 0 1 0 1 1
0 1 1 1 1 1 0
1 1 1 0 1 1 1
1 0 1 1 1 0 1
1 1 1 0 1 1 1
0 1 1 1 1 1 0
1 1 0 1 0 1 1

1 0 1 1 1 0 1
1 1 1 0 1 1 1
0 1 1 1 1 1 0
1 1 0 1 0 1 1
0 1 1 1 1 1 0
1 1 1 0 1 1 1
1 0 1 1 1 0 1

the implementation requires that m <= n, and that n is odd. the
script contains an earlier version without these restrictions, but
i'm not happy with my analysis for those cases. i expect to have
a solution soon.

the timings are much better than those published in the article i
mentioned. here they are for 3 x 3 -> 11 x 11. "#" means "number
of minimal solutions."

results: 3.0 ghz

rows cols ms # empties
---- ---- -- - -------
3 3 0 6 1
3 5 0 1 4
3 7 0 1 6
3 9 0 1 7
3 11 15 4 10
4 5 0 2 6
4 7 0 2 7
4 9 0 6 10
4 11 15 1 11
5 5 0 1 7
5 7 0 7 10
5 9 0 6 12
5 11 31 3 14
6 7 15 1 11
6 9 0 4 14
6 11 78 3 17
7 7 15 2 12
7 9 15 1 16
7 11 203 3 19
8 9 31 1 18
8 11 531 7 22
9 9 78 12 21
9 11 1390 1 24
10 11 3671 2 27
11 11 9687 19 30

>
> John Carter Phone : (64)(3) 358 6639
> Tait Electronics Fax : (64)(3) 359 4632
> PO Box 1645 Christchurch Email : john.carter@...
> New Zealand
>
> Refactorers do it a little better every time.
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
>

John Carter — 2005-03-31 01:31:40

On Wed, 30 Mar 2005, stevan apter wrote:

>>> Given a garden laid out on an mxn grid, you must place "Planted" and "Empty" cells
>>> on the grid so that you can reach each Planted cell while standing in an Empty cell.
>>> In other words, for each Planted cell, one of its four neighbors (no diagonals) must
>>> be Empty. Thus, you can tend your garden without ever standing in the planted areas
>>> (which would compact the soil and potentially damage the plants that are growing
>>> there).

> i make two assumptions:
>
> 1. a minimal solution for m rows, n cols can always be constructed
> from the set of symmetrical rows of length n.

Hmm. I'm not sure I believe that. What about m==n==2?
PE
PP

John Carter Phone : (64)(3) 358 6639
Tait Electronics Fax : (64)(3) 359 4632
PO Box 1645 Christchurch Email : john.carter@...
New Zealand

Refactorers do it a little better every time.

stevan apter — 2005-03-31 02:27:50

----- Original Message -----
From: "John Carter" <john.carter@...>
To: <concatenative@yahoogroups.com>
Sent: Wednesday, March 30, 2005 8:31 PM
Subject: Re: [stack] the garden problem

>
> On Wed, 30 Mar 2005, stevan apter wrote:
>
> >>> Given a garden laid out on an mxn grid, you must place "Planted" and "Empty" cells
> >>> on the grid so that you can reach each Planted cell while standing in an Empty cell.
> >>> In other words, for each Planted cell, one of its four neighbors (no diagonals) must
> >>> be Empty. Thus, you can tend your garden without ever standing in the planted areas
> >>> (which would compact the soil and potentially damage the plants that are growing
> >>> there).
>
> > i make two assumptions:
> >
> > 1. a minimal solution for m rows, n cols can always be constructed
> > from the set of symmetrical rows of length n.
>
> Hmm. I'm not sure I believe that. What about m==n==2?

as i said, the algorithm assumes odd n. i should have added: and n>2.
(which is obvious from the code, and from the table of results.)

> PE
> PP
>
>
>
> John Carter Phone : (64)(3) 358 6639
> Tait Electronics Fax : (64)(3) 359 4632
> PO Box 1645 Christchurch Email : john.carter@...
> New Zealand
>
> Refactorers do it a little better every time.
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
>

Greg Buchholz — 2005-03-31 16:17:48

--- John Carter <john.carter@...> wrote:

> On Wed, 30 Mar 2005, stevan apter wrote:
> > 1. a minimal solution for m rows, n cols can always be constructed
> > from the set of symmetrical rows of length n.
>
> Hmm. I'm not sure I believe that. What about m==n==2?
> PE
> PP

You can't access a planted cell from an empty cell through a diagonal.
At least according to...

http://hcsoftware.sourceforge.net/jason-rohrer/worklog/index.php?y=2005&m=3&d=14

So the smallest answer for the 2x2 case would be one of...

PE EE EP EP PP PE
EP PP EP PE EE PE

Greg Buchholz

__________________________________
Do you Yahoo!?
Yahoo! Mail - now with 250MB free storage. Learn more.
http://info.mail.yahoo.com/mail_250