On 2/12/2022 3:49 PM, Father Horton wrote:

Performance definitely varies widely with similar (not the same)
inputs.  Another run for 100 blocks on a 60x60 space ran in 18m57s and
at the end had 2.6M entries on the free list.

This algorithm doesn't try to minimize the total area, and in fact does
an awful job at minimizing the bounding box.  It tends to walk up the
left side of the area, and then walk to the right, and then fill in from
the top down.  I don't yet fully understand the behavior, but I think
that it's dominated by the fact that, given a free block that can hold
the block to be placed, it uses the lower-left corner of that free block.

To minimize the bounding box, I think you'd want to sort of build out
from the origin, placing new blocks along the perimeter of the existing
blocks.

A related problem is to pack as many blocks as possible into a given
area.  That's where randomly permuting the inputs to this function might
be useful.  Probably you would make it stop and return what it has when
it's not able to place a block - and if it was able to place all of the
blocks, you could try placing more.

On 2/12/2022 4:08 PM, jon wrote:

It was an interesting puzzle.

But conceptually it's really not that complex.

Start with an area

ABCDE
FGHIJ
KLMNO
PQRST
UVWXY

Let's place, oh, a [2,3] block.  That's easy:

ABCDE
FGHIJ
**MNO
**RST
**WXY

We've placed our first block.  What space do we have left?  We have the
area above that block:

ABCDE   call this block 1
FGHIJ
.....
.....
.....

and the area to the right:

..CDE    call this block 2
..HIJ
..MNO
..RST
..WXY

left.  Now let's place a [4,1] block.  That fits in block 1:

ABCDE
****J
.....
.....
.....

and splits block 1 into:

ABCDE   call this block 3
.....
.....
.....
.....

and

....E   call this block 4
....J
.....
.....
.....

It also overlaps block 2.  It's chopping out the HI, so splits it into
the block above:

..CDE    call this block 5
.....
.....
.....
.....

the block to the right:

....E    call this block 6
....J
....O
....T
....Y

and the block below:

.....    call this block 7
.....
..MNO
..RST
..WXY

Now we're placed two blocks:

.....
2222.
11...
11...
11...

and have this free space:

ABCDE
....J
..MNO
..RST
..WXY

The free space is recorded in the form of five overlapping blocks -
blocks 3, 4, 5, 6, and 7.

3      4      5      6      7
ABCDE  ....E  ..CDE  ....E  .....
.....  ....J  .....  ....J  .....
.....  .....  .....  ....O  ..MNO
.....  .....  .....  ....T  ..RST
.....  .....  .....  ....Y  ..WXY

(Note:  this illustrates what I mean about the potential for
deduplication.  Block 5 (CDE) is entirely enclosed by block 3 (ABCDE)
and so could be dropped.  Similarly, block 4 (EJ) is entirely enclosed
by block 6 (EJOTY).)

We continue this process until we've placed all of the blocks, or until
we can't fit a block into an available space.

The implementation uses some slightly tricky OpenSCAD stuff like list
comprehensions (to find a free space to put a block, and to break up
free blocks when we place a block) and recursion (to process all of the
blocks to be placed), but with an idea of how it works maybe you can
understand the implementation better.

I don't claim that this is the best algorithm available for the
problem.  In particular, I suspect that it could be relatively easily
improved by looking for the smallest block that the new block will fit
into, rather than the first one found.  But it was what I came up with,
and it seems to sort of work...

On Sat, Feb 12, 2022 at 11:40:45PM +0000, Jordan Brown wrote:

In computer-science, I remember that for memory allocation, first-fit
and best fit perform very similar. That's because "best fit" is more
likely to leave very small remaining areas that end up never being
useful again. This might apply here too.

Roger.

--
** R.E.Wolff@BitWizard.nl ** https://www.BitWizard.nl/ ** +31-15-2049110 **
**    Delftechpark 11 2628 XJ  Delft, The Netherlands.  KVK: 27239233    **
f equals m times a. When your f is steady, and your m is going down
your a is going up.  -- Chris Hadfield about flying up the space shuttle.

On 2/13/2022 9:37 AM, Jordan Brown wrote:

Note that although the free list tends to grow rather explosively, it
does occasionally shrink.  If we now place a [1,5] block, it will fit
into block 6 and totally consume blocks 4 and 6, leaving:

8      9      10
ABCD.  ..CD.  .....
.....  .....  .....
.....  .....  ..MN.
.....  .....  ..RS.
.....  .....  ..WX.

Would it help if you sorted by size so that you placed the largest
objects first?

On 2/13/2022 12:37 PM, Jordan Brown wrote:

On 2/13/2022 10:07 AM, jon wrote:

Don't know, maybe.  Sounds likely.