RPG Math - Problem 6

We haven't had one of these in a while. It's time for another round of...

Problem 6: Taking Inventory

This problem is related to algorithms. For this problem, we will need to introduce some new terminology. This new terminology may appear in other algorithm-related problems in the future.

A decision problem is a problem which asks, given a certain input, whether that input satisfies a certain condition. For example, the Boolean satisfiability problem asks, given a Boolean formula (such as "A and B or (not (C and A))" whether or not there exists an assignment of "true" and "false" values to the variables (A, B, and C in this case) that will make the result of the formula "true". The independent set problem asks, given a graph G and an integer L, whether it is possible to choose L vertices such that no two of the vertices chosen have an edge between them.

An instance of a decision problem means a particular input for the decision problem. For example an "instance" of the Boolean satisfiability problem means a particular Boolean formula. An instance of a decision problem of course has one answer, "true" or "false".

To reduce a decision problem P to another decision problem Q means to show a simple* way to, given an instance of problem P, find an instance of problem Q that has the same answer. For example, consider the following two problems:

P: Given a graph G and an integer N, is there a way to color the vertices of G with N colors so that no edge of G has endpoints that are the same color?

Q: Given a partition M of the plane into regions, and an integer N, is there a way to color the regions of M in such a way that no two adjacent regions have the same color?

In this example, there is a way to reduce Q to P - given an instance of Q, create a graph with one vertex for each region, with edges between vertices corresponding to adjacent regions, and feed that to P. There is not, however, a corresponding way to reduce P to Q. (For instance, if N >= 4, then the answer to Q is always yes, but the same is not true of P.)

A problem P is equivalent to a problem Q if P can be reduced to Q and Q can be reduced to P.

---

Now with all the terminology taken care of, it's time to get to the problem.

Many computer games use a "grid inventory" system. This means that items that the character is carrying are arranged in a grid, with larger items taking up more space. For instance, a small item such as a gem might only take up one square of the grid, while a large item such as a suit of armor might take up, say, a 3x4 area of the grid. All items your character is carrying must fit in the grid, so you cannot pick up an item if you can't fit it in the grid. This image gives an example of what an inventory grid looks like. (If you can't see the image, hover over the line "NWN_inventory.jpg image by..." and click the "Zoom in" item on the menu bar that appears.)

The Inventory Grid Problem (IGP) is as follows: Given an NxM inventory grid, and a set of objects with associated sizes (e.g. you have an 8x10 grid, and you have one 4x6 object, three 3x3 objects, five 2x1 objects, etc.) is it possible to fit all the objects in the grid? (Note: Objects cannot be rotated.)

Just today I came into a real life situation that is very similar to the inventory grid situation. I have just bought miniatures for a miniatures combat game called Warmachine. In order to safely transport the miniatures without them being damaged, they sell large blocks of foam that are perforated in a grid pattern (see this image for an example) and you can remove the squares of foam in order to insert your miniatures. This way each miniature is stored separately and surrounded by a cushion of foam. This image is an example of foam being used to store miniatures.

Suppose that you have a whole bunch of miniatures, and a block of foam of a given size, and you want to see if it is possible to fit all the miniatures into that block. This problem is similar to the Inventory Grid Problem above, with the exception that objects cannot be adjacent to each other - there must be a "cushion" or "buffer" of at least one square between each object. Thus, we have the...

Buffered Inventory Grid Problem (BIGP): Given an NxM inventory grid, and a set of objects with associated sizes (e.g. you have an 8x10 grid, and you have one 4x6 object, three 3x3 objects, five 2x1 objects, etc.) is it possible to fit all the objects in the grid such that no two objects are adjacent? (Again, objects cannot be rotated. While this isn't very realistic in terms of the miniatures problem, it makes the problems below much simpler.)

-----

There are two problems here:

6.1. Show that the Inventory Grid Problem and the Buffered Inventory Grid Problem are equivalent.

(Hint. Reducing BIGP to IGP is fairly straightforward. Reducing IGP to BIGP is a little trickier.)

6.2. Show that the bin-packing problem** can be reduced to the Inventory Grid Problem. (This implies that IGP is NP-complete, meaning that there is (almost certainly) no algorithm that solves it in a time polynomial in the length of the input. I might go into further detail on this topic in future questions.

Solutions are here.

* "Simple" means "can be done in a time polynomial in the length of the input."

** The problem as described in the link is the optimization variant of the problem - find the minimum number of bins necessary. The decision problem variant of the problem is: given a number N, can you do it with N or fewer bins (thus the answer is "yes" or "no" as described above). Since we're dealing with decision problems here this is the one you want to use.