Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #37377 > unrolled thread

Is there already an easy fit algorithm?

Back to article view | Back to comp.lang.java.programmer

Contents

  Is there already an easy fit algorithm? Eric Douglas <e.d.programmer@gmail.com> - 2017-09-08 05:05 -0700
    Is there already an easy fit algorithm? lewbloch@gmail.com - 2017-09-08 07:38 -0700
      Re: Is there already an easy fit algorithm? Eric Douglas <e.d.programmer@gmail.com> - 2017-09-08 08:34 -0700
      Re: Is there already an easy fit algorithm? Eric Douglas <e.d.programmer@gmail.com> - 2017-09-08 11:36 -0700
        Re: Is there already an easy fit algorithm? Joshua Cranmer 🐧 <Pidgeot18@verizon.invalid> - 2017-09-10 22:52 -0400
          Re: Is there already an easy fit algorithm? Gene Wirchenko <genew@telus.net> - 2017-09-11 20:24 -0700
            Re: Is there already an easy fit algorithm? Eric Douglas <e.d.programmer@gmail.com> - 2017-09-12 05:05 -0700
            Re: Is there already an easy fit algorithm? Eric Douglas <e.d.programmer@gmail.com> - 2017-09-12 05:11 -0700
              Re: Is there already an easy fit algorithm? lewbloch@gmail.com - 2017-09-12 10:31 -0700
                Re: Is there already an easy fit algorithm? Eric Douglas <e.d.programmer@gmail.com> - 2017-09-12 10:52 -0700
                  Re: Is there already an easy fit algorithm? lewbloch@gmail.com - 2017-09-12 12:43 -0700
                    Re: Is there already an easy fit algorithm? Eric Douglas <e.d.programmer@gmail.com> - 2017-09-12 13:02 -0700
                      Re: Is there already an easy fit algorithm? Eric Sosman <esosman@comcast-dot-net.invalid> - 2017-09-12 17:08 -0400
                        Re: Is there already an easy fit algorithm? Eric Douglas <e.d.programmer@gmail.com> - 2017-09-13 05:21 -0700
                          Re: Is there already an easy fit algorithm? Eric Sosman <esosman@comcast-dot-net.invalid> - 2017-09-13 12:49 -0400
                            Re: Is there already an easy fit algorithm? Eric Douglas <e.d.programmer@gmail.com> - 2017-09-13 11:13 -0700
                          Re: Is there already an easy fit algorithm? lewbloch@gmail.com - 2017-09-13 14:24 -0700
                            Re: Is there already an easy fit algorithm? Arne Vajhøj <arne@vajhoej.dk> - 2017-09-13 20:35 -0400
                              Re: Is there already an easy fit algorithm? lewbloch@gmail.com - 2017-09-14 11:26 -0700
                                Re: Is there already an easy fit algorithm? Eric Douglas <e.d.programmer@gmail.com> - 2017-09-14 11:53 -0700
                                  Re: Is there already an easy fit algorithm? Martin Gregorie <martin@address-in-sig.invalid> - 2017-09-14 19:49 +0000
                                  Re: Is there already an easy fit algorithm? lewbloch@gmail.com - 2017-09-14 14:38 -0700
                                    Re: Is there already an easy fit algorithm? Arne Vajhøj <arne@vajhoej.dk> - 2017-09-14 20:34 -0400
                                      Re: Is there already an easy fit algorithm? Andreas Leitgeb <avl@logic.at> - 2017-09-15 09:22 +0000
                                        Re: Is there already an easy fit algorithm? Arne Vajhøj <arne@vajhoej.dk> - 2017-09-15 20:03 -0400
                                      Re: Is there already an easy fit algorithm? Gene Wirchenko <genew@telus.net> - 2017-09-19 21:16 -0700
                                        Re: Is there already an easy fit algorithm? Arne Vajhøj <arne@vajhoej.dk> - 2017-09-20 08:58 -0400
                                Re: Is there already an easy fit algorithm? leif.roar@dimnakorr.com - 2017-09-18 04:14 -0500
                      Re: Is there already an easy fit algorithm? Martin Gregorie <martin@address-in-sig.invalid> - 2017-09-12 21:50 +0000
                        Re: Is there already an easy fit algorithm? Eric Douglas <e.d.programmer@gmail.com> - 2017-09-13 05:12 -0700
                          Re: Is there already an easy fit algorithm? Martin Gregorie <martin@address-in-sig.invalid> - 2017-09-13 13:07 +0000
                            Re: Is there already an easy fit algorithm? Eric Douglas <e.d.programmer@gmail.com> - 2017-09-13 06:33 -0700
                              Re: Is there already an easy fit algorithm? Martin Gregorie <martin@address-in-sig.invalid> - 2017-09-13 16:37 +0000
                                Re: Is there already an easy fit algorithm? Eric Douglas <e.d.programmer@gmail.com> - 2017-09-13 10:36 -0700
                                  Re: Is there already an easy fit algorithm? Martin Gregorie <martin@address-in-sig.invalid> - 2017-09-13 18:54 +0000
              Re: Is there already an easy fit algorithm? Gene Wirchenko <genew@telus.net> - 2017-09-19 21:21 -0700
            Re: Is there already an easy fit algorithm? Eric Douglas <e.d.programmer@gmail.com> - 2017-09-12 07:32 -0700
              Re: Is there already an easy fit algorithm? Eric Douglas <e.d.programmer@gmail.com> - 2017-09-12 08:02 -0700
    Re: Is there already an easy fit algorithm? Eric Sosman <esosman@comcast-dot-net.invalid> - 2017-09-12 11:47 -0400
    Re: Is there already an easy fit algorithm? Martin Gregorie <martin@address-in-sig.invalid> - 2017-09-15 10:27 +0000

Page 2 of 2 — ← Prev page 1 [2]

#37420

On Thu, 14 Sep 2017 11:53:05 -0700, Eric Douglas wrote:

> On Thursday, September 14, 2017 at 2:27:32 PM UTC-4, lewb...@gmail.com
> wrote:
>> 
>> It is an imperial *and* a US measure, but calling it out as if these
>> are separate definitions of "foot" is ludicrous. No one says "imperial
>> foot". No one says "imperial inch". No one says "imperial mile" (though
>> there is "nautical mile"). It just isn't a distinction.
>> 
>> A cubic foot is a cubic foot is a cubic foot. You don't say "cubic feet
>> (imperial)".
>> 
>> --
>> Lew
> 
> That is just a proper word wikipedia used
> (https://en.wikipedia.org/wiki/Imperial_units) to describe it, "British
> Imperial" meaning the same as what we know as the English measurement
> system.
> There is only one unit of measurement known as a foot that I'm aware of,
> though as you mentioned there's something called a nautical mile and I
> don't know much about measurement systems besides English and Metric.

FYI the Nautical mile is widely used in both air and marine navigation 
along with the knot (1 nautical mph), but both are seldom used outside 
these areas. The nautical mile is roughly 15% bigger than the imperial 
measure at 1852m, 6076ft, approximately 1 minute of arc round the earth 
at sea level at 48 degrees latitude.

It counts as an international unit because the ICAO adopted it in 1947, 
along with the knot for speed, the foot for height and the millibar for 
pressure, as the navigational units to be used for navigation and 
communication by civil aviation.
 

-- 
martin@   | Martin Gregorie
gregorie. | Essex, UK
org       |

[toc] | [prev] | [next] | [standalone]

#37421

A cubic foot is a cubic foot is a cubic foot.

[toc] | [prev] | [next] | [standalone]

#37422

On 9/14/2017 5:38 PM, lewbloch@gmail.com wrote:
> A cubic foot is a cubic foot is a cubic foot.

A cubic foot (X) is a cube with each side 1 foot (X).

1 foot (X) depends on X.

There was a list in the link I gave you.

Imperial
US Customary
Prussian
Danish
Swedish
etc.

It is perfectly to specify what type of foot it is.

If nothing is specified then Imperial/US Customary is
a good default, but a good default does not rule out
being explicit.

Arne

[toc] | [prev] | [next] | [standalone]

#37423

Arne Vajhøj <arne@vajhoej.dk> wrote:
> but a good default does not rule out
> being explicit.

In Java, at least the default visibility does rule out being explicit about it.

(trying to divert pointless rambling about qualified feet back to java ;-)

[toc] | [prev] | [next] | [standalone]

#37426

On 9/15/2017 5:22 AM, Andreas Leitgeb wrote:
> Arne Vajhøj <arne@vajhoej.dk> wrote:
>> but a good default does not rule out
>> being explicit.
> 
> In Java, at least the default visibility does rule out being explicit about it.

Which I also thought was bad.

Every time I see it I wonder: did the author deliberately chose package
visibility or did the author forget to think about visibility.

Arne

[toc] | [prev] | [next] | [standalone]

#37433

On Thu, 14 Sep 2017 20:34:11 -0400, Arne Vajhøj <arne@vajhoej.dk>
wrote:

>On 9/14/2017 5:38 PM, lewbloch@gmail.com wrote:
>> A cubic foot is a cubic foot is a cubic foot.
>
>A cubic foot (X) is a cube with each side 1 foot (X).

     It can be, but many other dimensions sets define an object with a
volume of one cubic foot.  For example, a rectangular prism of 1/2
foot by 2 feet by 1 foot has a volume of one cubic foot.

[snip]

Sincerely,

Gene Wirchenko

[toc] | [prev] | [next] | [standalone]

#37436

On 9/20/2017 12:16 AM, Gene Wirchenko wrote:
> On Thu, 14 Sep 2017 20:34:11 -0400, Arne Vajhøj <arne@vajhoej.dk>
> wrote:
>> On 9/14/2017 5:38 PM, lewbloch@gmail.com wrote:
>>> A cubic foot is a cubic foot is a cubic foot.
>>
>> A cubic foot (X) is a cube with each side 1 foot (X).
>
>      It can be, but many other dimensions sets define an object with a
> volume of one cubic foot.  For example, a rectangular prism of 1/2
> foot by 2 feet by 1 foot has a volume of one cubic foot.

... is the same volume as a ...

Arne

[toc] | [prev] | [next] | [standalone]

#37427

lewbloch@gmail.com wrote:
> 
> It is an imperial *and* a US measure, but calling it out as 
> if these are separate definitions of "foot" is ludicrous. 

http://vterrain.org/Projections/sp_feet.html

> No one says "imperial foot". No one says "imperial inch". 
> No one says "imperial mile" (though there is "nautical mile"). 

I do. Granted, I'll usually say "an American foot" / "English mile"
but I'll use "Imperial" in formal writing.

> It just isn't a distinction. 

Until there is.

-- 
Leif Roar Moldskred

[toc] | [prev] | [next] | [standalone]

#37401

On Tue, 12 Sep 2017 13:02:31 -0700, Eric Douglas wrote:

> On Tuesday, September 12, 2017 at 3:43:34 PM UTC-4, lewb...@gmail.com
> wrote:
>> That "high-cube" designation doesn't indicate an "actual cube" at all.
>> "Cube" there is not a noun or a unit but part of an adjectival phrase
>> meaning that the container has a high cubic capacity. There is no
>> particular "cube" implied. It doesn't represent a particular measure,
>> and high-cube containers are not themselves cubes in shape.
>> 
>> So what is an "actual cube"?
> 
> Actual cube meaning the cube that is used to measure all truck trailers.
>  I'm guessing that means cubic feet.

I notice you haven't mentioned the external shape or weight of any of 
these packages, which surprises me, since the shape could well affect the 
packing density you can achieve in a container just as the weight could 
cause a load of dense packages to exceed the permitted maximum weight for 
a container.


-- 
martin@   | Martin Gregorie
gregorie. | Essex, UK
org       |

[toc] | [prev] | [next] | [standalone]

#37403

On Tuesday, September 12, 2017 at 5:50:27 PM UTC-4, Martin Gregorie wrote:
> 
> I notice you haven't mentioned the external shape or weight of any of 
> these packages, which surprises me, since the shape could well affect the 
> packing density you can achieve in a container just as the weight could 
> cause a load of dense packages to exceed the permitted maximum weight for 
> a container.
> 

Ultimately if we could write a 'just do it, always correct' packing algorithm it would take that and more into account.  If they sufficiently pad the cubes then worst case they should fit what we suggest and more.  Obviously we can't say for certain without knowing all the factors, packaging is big as sometimes things are boxed and sometimes they're blanket wrapped, pretty sure weight wouldn't be an issue since we're shipping wooden furniture not steel boxes.  We do have approximate weights we can throw in the total line in case that's an issue.  Of course for now the final packing scheme will still be done manually by the traffic person.

[toc] | [prev] | [next] | [standalone]

#37405

On Wed, 13 Sep 2017 05:12:12 -0700, Eric Douglas wrote:

> Ultimately if we could write a 'just do it, always correct' packing
> algorithm it would take that and more into account.  If they
> sufficiently pad the cubes then worst case they should fit what we
> suggest and more.  Obviously we can't say for certain without knowing
> all the factors, packaging is big as sometimes things are boxed and
> sometimes they're blanket wrapped, pretty sure weight wouldn't be an
> issue since we're shipping wooden furniture not steel boxes.
>
Thanks for the clarification: it wasn't obvious from your other posts 
what you were shipping.   

> approximate weights we can throw in the total line in case that's an
> issue.  Of course for now the final packing scheme will still be done
> manually by the traffic person.


-- 
martin@   | Martin Gregorie
gregorie. | Essex, UK
org       |

[toc] | [prev] | [next] | [standalone]

#37406

On Wednesday, September 13, 2017 at 9:07:48 AM UTC-4, Martin Gregorie wrote:
> >
> Thanks for the clarification: it wasn't obvious from your other posts 
> what you were shipping.   
> 

If we get into details of which items to allow by weight, much less how the items could be arranged, then it definitely matters.  For providing a list of parts, saying each part takes up x cubes, and each truck allows x cubes, they can be widgets.  While we do show item weights (and I'm not sure how accurate those are), we don't have total allowed truck weight in the system, so that is not a system calculation.  For software to know exact dimensions and weights and which direction each item may be rotated (a sofa on it's side?) and whether any specific item may be placed on top of any other specific item is a lot more involved.

[toc] | [prev] | [next] | [standalone]

#37408

On Wed, 13 Sep 2017 06:33:46 -0700, Eric Douglas wrote:

> On Wednesday, September 13, 2017 at 9:07:48 AM UTC-4, Martin Gregorie
> wrote:
>> >
>> Thanks for the clarification: it wasn't obvious from your other posts
>> what you were shipping.
>> 
>> 
> If we get into details of which items to allow by weight, much less how
> the items could be arranged, then it definitely matters.  For providing
> a list of parts, saying each part takes up x cubes, and each truck
> allows x cubes, they can be widgets.  While we do show item weights (and
> I'm not sure how accurate those are), we don't have total allowed truck
> weight in the system, so that is not a system calculation.  For software
> to know exact dimensions and weights and which direction each item may
> be rotated (a sofa on it's side?) and whether any specific item may be
> placed on top of any other specific item is a lot more involved.

Yes, I appreciate that, but it still seems to me that 3D-Tetris has some 
similarities with what you're trying to do in that the shape and its 
orientation matters when you're filling a container. Calculating how to 
fill a container with a mix of sofas, chairs and desks springs to mind. 

Obviously, the people doing the stacking manually optimise container 
packing, but maybe your loading calculator should as well, otherwise it 
may miscalculate the amount of stuff it include in a load. 

It may not matter so much if it underestimates a load, but is it likely 
to cause problems if it consistently overestimates what can be put in a 
container?


-- 
martin@   | Martin Gregorie
gregorie. | Essex, UK
org       |

[toc] | [prev] | [next] | [standalone]

#37410

On Wednesday, September 13, 2017 at 12:37:58 PM UTC-4, Martin Gregorie > Yes, I appreciate that, but it still seems to me that 3D-Tetris has some 
> similarities with what you're trying to do in that the shape and its 
> orientation matters when you're filling a container. Calculating how to 
> fill a container with a mix of sofas, chairs and desks springs to mind. 
> 
> Obviously, the people doing the stacking manually optimise container 
> packing, but maybe your loading calculator should as well, otherwise it 
> may miscalculate the amount of stuff it include in a load. 
> 
> It may not matter so much if it underestimates a load, but is it likely 
> to cause problems if it consistently overestimates what can be put in a 
> container?
> 

Yes, obviously, and this is a first step in simplifying the process to select which items can go in trucks together, which is previously done 100% manually.  Unless we can find a perfect algorithm to reproduce exactly what they've come up with in spreadsheets every time they will need to manually adjust the load.  Once they try it out we can get some feedback to tweak the algorithm.  I wouldn't want to go all out gathering data not currently in the system trying to reach the endgame in one shot.

I'm sure the traffic manager would love it if we could write a truck packing screen as a game of 3D Tetris.

[toc] | [prev] | [next] | [standalone]

#37412

On Wed, 13 Sep 2017 10:36:41 -0700, Eric Douglas wrote:

> I'm sure the traffic manager would love it if we could write a truck
> packing screen as a game of 3D Tetris.
>
:-)

FWIW, I've been maintaining a set of six club duty rosters for the last 
few years. These are interlinked by a set of rules:

- some members are on more than one roster so must not be rostered on
  both rosters for the same weekend

- some members (on different rosters) travel together, so should be
  rostered on the same day at the same time

- group ownership of rather a rather expensive piece of sporting
  equipment means that only one group member can be rostered on a day,
  regardless of which rosters each of them volunteer for.

..and finally, for each roster there are rules that set the minimum gap 
between successive duties for a member.

Before I took the task over it was handled by a massive 13 page 
spreadsheet (six rosters, a preferences import page for each and last 
season's overall roster), which did little more than record its user's 
input and required manual application of the above rules. 

I built a Java program that does all the above AND implements those rules 
as well as visually showing days blocked out because they are too close a 
member's previous duty, but this still requires duty allocation to be 
done manually. 

It uses a matrix. The X axis lists member names, the Y axis shows dates 
and duty allocations for that roster. The matrix body contains colour 
coded cells showing the status of a member vs duty allocation, e.g.:

pale blue=unallocated  

green=allocated duty

darkgreen=allocated all-day duty

red=rejected allocation attempt

I initially wanted to try automating duty allocation but was persuaded 
that this would be a nightmare to implement, while the current approach 
of just automating the rules to do real-time checks as duties are 
allocated works well and is fairly intuitive to use.

I suspect you may find my rostering task has similarities to your 
container packing task, so making something with a UI like a 3D Tetris 
game with automated packing rules and manual package allocation may not 
be such a bad idea, particularly if it is possible to simultaneously show 
all the trucks currently in loading bays or all trucks taking stuff to 
the same destination while still having a usable screen.


-- 
martin@   | Martin Gregorie
gregorie. | Essex, UK
org       |

[toc] | [prev] | [next] | [standalone]

#37434

On Tue, 12 Sep 2017 05:11:21 -0700 (PDT), Eric Douglas
<e.d.programmer@gmail.com> wrote:

>On Monday, September 11, 2017 at 11:25:05 PM UTC-4, Gene Wirchenko wrote:

[snip]

>>      Your use of the term "cubes" is unclear.  Do you mean the
>> gemoetric object or cubic units of measure?

[snip]

>By cubes I mean actual cubes, as in the writing you see on the back of a truck.

     That is a stunning example of a bad answer.  Since I do not know
what you are referring to by "cubes", using the word as part of the
definition does not work.

Sincerely,

Gene Wirchenko

[toc] | [prev] | [next] | [standalone]

#37392

On Monday, September 11, 2017 at 11:25:05 PM UTC-4, Gene Wirchenko wrote:
> >Integer knapsack is NP-complete. The greedy algorithm doesn't work. 
> >Imagine your capacity is 10 units, and you have cubes of size 7, 6, and 
> >4. Your algorithm says you can only fit the 7 cube, but you can fit 
> >cubes 6 and 4.
> 
>      Bad example since the second truck will get 6 and 4.  The
> solution is optimum though accidentally so.
> 
>      Here is an example that illustrates the point:
> 
>      Capacity is 10.  You have units 5, 4, 3, 3, 3, 2.
> 
>      Greedy gets [5, 4] then [3, 3, 3] then [2] requiring 3 loads.
> 
>      Better is [5, 3, 2] then [4, 3, 3] requiring 2 loads.
> 
> 
>      Your use of the term "cubes" is unclear.  Do you mean the
> gemoetric object or cubic units of measure?
> 
> Sincerely,
> 
> Gene Wirchenko

ok, I changed up the algorithm.  Now your sample gets 2 buckets, a 2,3,5 and a 3,3,4.

Trying to fill trucks that hold 2800 cubes my previous algorithm took 1 large order and split it to 4 trucks totaling 2798.9, 2797.6, 2798.7, and 2300.6.  My new algorithm gets the same totals, so as I mentioned it may not make a noticeable difference when you're working with larger totals and larger quantities, though I think the code is cleaner.  Paste this into my previous sample.

     public boolean fitsOnTruck(final float truckCubes, final int pick) { 
          if (pick == arr.length) { 
               return false; 
          }
          if (arr[pick] > truckCubes) { 
               return fitsOnTruck(truckCubes, pick + 1); 
          } else if (arr[pick] < truckCubes) { 
               if (fitsOnTruck(truckCubes - arr[pick], pick + 1) || pick == arr.length - 1) {
                    retArr.add(arr[pick]); 
                    return true; 
               } else { 
                    return fitsOnTruck(truckCubes, pick + 1); 
               } 
          } else { 
               retArr.add(arr[pick]); 
               return true; 
          } 
     } 

Of course my final code is a little more complicated.  I'm passing in an ArrayList of line items.  Each line item has an item ID, a quantity, and a cube amount.  My return value is an ArrayList telling me which items and how many of each.

[toc] | [prev] | [next] | [standalone]

#37393

On Tuesday, September 12, 2017 at 10:32:39 AM UTC-4, Eric Douglas wrote:
>      public boolean fitsOnTruck(final float truckCubes, final int pick) { 
>           if (pick == arr.length) { 
>                return false; 
>           }
>           if (arr[pick] > truckCubes) { 
                 if (pick == 0) { throw new Error("Item " + arr[pick] + " too big for container"); }
>                return fitsOnTruck(truckCubes, pick + 1); 
>           } else if (arr[pick] < truckCubes) { 
>                if (fitsOnTruck(truckCubes - arr[pick], pick + 1) || pick == arr.length - 1) {
>                     retArr.add(arr[pick]); 
>                     return true; 
>                } else { 
>                     return fitsOnTruck(truckCubes, pick + 1); 
>                } 
>           } else { 
>                retArr.add(arr[pick]); 
>                return true; 
>           } 
>      } 
> 

Technically it should check for the error condition, though normally I'd think if you're checking any items that don't fit in your container alone you've got issues.

Of course at some point it also needs to do the loop to show totals for multiple containers.

[toc] | [prev] | [next] | [standalone]

#37394

On 9/8/2017 8:05 AM, Eric Douglas wrote:
> Before I reinvent another wheel...
> We have a fixed amount of cubes we know can fit in a truck.  We have a variable amount of products, each with a variable amount of cubes, which may require more than one truck.  Is there a simple way to select which products should go in a truck to come as close to the cubes amount without going over?
> 

https://en.wikipedia.org/wiki/Bin_packing_problem


-- 
esosman@comcast-dot-net.invalid
Twelve hundred twenty-six days to go.

[toc] | [prev] | [next] | [standalone]

#37424

On Fri, 08 Sep 2017 05:05:02 -0700, Eric Douglas wrote:

> Before I reinvent another wheel...
> We have a fixed amount of cubes we know can fit in a truck.  We have a
> variable amount of products, each with a variable amount of cubes, which
> may require more than one truck.  Is there a simple way to select which
> products should go in a truck to come as close to the cubes amount
> without going over?

This is OTT I know, but if may interest you to see how a somewhat unusual 
cargo can be transported in a custom-fitted container:

https://docs.google.com/document/d/1HsEw2XpHRDVAbtc5Nxc-nes0d-
iMQTmiACybBYbmfD8/edit


-- 
martin@   | Martin Gregorie
gregorie. | Essex, UK
org       |

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.lang.java.programmer

csiph-web