From: Jacob Fugal <lukfugl@...>
Date: 2006-01-14T09:42:37+09:00
Subject: Re: [QUIZ] Packing (#62)

On 1/13/06, Ilmari Heikkinen <ilmari.heikkinen@gmail.com> wrote:
> On 1/13/06, Adam Shelly <adam.shelly@gmail.com> wrote:
> > regarding padding, is this a valid result?
> > 10x10
> > 5x5 5x5
> >
> > #####ooooo
> > #####ooooo
> > #####ooooo
> > #####ooooo
> > #####ooooo
> > ooooo#####
> > ooooo#####
> > ooooo#####
> > ooooo#####
> > ooooo#####
> >
> > i.e: do I need to put a pad in the spot marked with the ?
> > #####o
> > #####o
> > #####o
> > #####o
> > #####o
> > ooooo?
>
> Yes, that needs to be padded. Each point in a box should
> be >= 1 units from another box.

If you calculate using the manhattan distance, the distance between
the two corners (non-inclusive) is 1:

  #        #-O
  |    or    |
  O-#        #

But if you count the diagonal, then you need the pad:

  #
   \
    O
     \
      #

The choice isn't so obvious from the original wording: "The boxes need
to be padded with one unit worth of foam on each side that's facing
another box." The sides in Adam's example aren't *quite* facing each
other, hence the question. But as per your response I assume we're
counting the diagonal.

Jacob Fugal