Public Solving: Elf Post Service package calculator

In today's puzzle, we get asked by Santa himself to optimize their package performance.

You can find the puzzle here.

Great idea, since Amazon seems to suck at this!
And it's wasteful to use big boxes when having smaller ones available.

So, it's up to us to find the best fit package for each item we are packing.
Luckily, we only have to work with one item per box query.
However, the item could be rotated, making it more complicated.

Thinking out the solution

To determine if an item fits in a box, we have to loop over each box and find the smallest box.

The boxes are already in order of size, so we don't need to introduce a new function for this.

My first thought was actually to check if each element is equal to or smaller than the box like so:

item.width <= box.width &&
item.length <= box.width &&
item.height <= box.height;

This would partially work. In some cases, we would still get a bigger box, which means the item could be rotated inside the box to fit!

We could manually write out to check for each possible combination, but that would get very difficult to understand.

Writing the final solution

So my new idea is to calculate the item's surface and the box surface.

Let's create a function for that.

const calculateSurface = (item) => {
  return item.length * item.width * item.height;
};

This function will retrieve an item (box or item) and calculate the surface.

Then we can work on the selectBox function. The easiest way to handle this is to use the find method, as this will stop the moment it has a hit.

return boxes.find((box) => {
    return (
      calculateSurface(item) <= calculateSurface(box)   
  );
});

This will return if the item surface is smaller than the box surface.

However, there is a catch here!

Let's take this item: 3x3x80 it has a surface of 720.
And our tool states it fits in a petit box with the following dimensions: 20x20x10, which gives a surface of 4000.

But there is no way this will fit, as the 80 is way bigger than the 20...

That means we have to introduce another check, which will find the biggest side of an item, and makes sure it doesn't exceed the biggest side of the box.

Let's create that function.

const biggestSide = (item) => {
  return Math.max(...Object.values(item).filter(Number));
};

Bear with me. A lot is going on here.

First, we use Object.values to get all the values of the item we pass in.

Then we filter out only the numbers. This will remove the strings for the box.

Then we spread the values into a single array, and retrieve the highest number using the Math.max function.

All we have to do is introduce this as the second option for our find method.

return boxes.find((box) => {
    return (
      calculateSurface(item) <= calculateSurface(box) &&
      biggestSide(item) <= biggestSide(box)
    );
});

Let's give it a test run and see what happens.

We did it!

Let me know what you think of this solution or what you would do differently.

Thank you for reading, and let's connect!

Thank you for reading my blog. Feel free to subscribe to my email newsletter and connect on Facebook or Twitter

Comments

[Alex Lohr]

Any box can take 3 positions if you don't account for mirrored ones: laying on the top/bottom, the front/back or either side. Ruling out each of these positions directly should be faster than either sorting the proportions (the first solution I shortly considered) or perform lots of multiplication and finding the maximum size for each box.

type Box = { width: number, height: number, length: number };
const fitsOriented = (outer: Box, inner: Box) =>
  outer.width > inner.width &&
  outer.height > inner.height &&
  outer.length > inner.length;
// turn over the X axis: swap height and length
const turnX = (box: Box) =>
  ({ width: box.width, height: box.length, length: box.height });
// turn over the Z axis: swap width and length
const turnZ = (box: Box) =>
  ({ width: box.length, height: box.height, length: box.width });
const fits = (outer: Box, inner: Box) =>
  fitsOriented(outer, inner) || 
  fitsOriented(outer, turnX(inner)) ||
  fitsOriented(outer, turnZ(inner));
const solution = boxes.find((box) => fits(box, item));

[Chris Bongers]

Yeah technically indeed, however you might occur objects who fit diagonal in either of the three ways introducing another level.

Not really an issue for this puzzle, but in terms of finding the "best" one I got stuck on that as well.