Hi,

what is a smart algorithm for this?

**Input data:** List L of rectangles. Rectangle is 4 ints: `(x, y)` of top-left corner, `(xl, yl)` the two lengths. Also input data is exactly one torus map M -- this is a large rectangle, it's larger than any single rectangle in L.

**Wanted output:** Rectangle O that surrounds all the listed rectangles. This rectangle should be as small as possible. It's allowed to move the rectangles in L by integer multiples of the length of M. The output rectangle O should account for O-minimizing optimal shifts of the rectangles in L. (To clarify after NaOH's question: I want to minimize the lengths of O. You may shift the rectangles of L as often as you wish to minimize the length of O.)

**I know:** You can separate this problem by dimension: Consider only x and x-length first, then y and y-length.

**Existing algorithms:** I have an algorithm to find the smallest container on a non-torus map -- when you're not allowed to move the rectangles in L by the length of M.

For example, if the rectangles are denoted as `Rect(x, y, xl, yl)`, the non-torus algorithm computes the correct smallest container for the following list of three rectangles:

` [ Rect(3, 5, 10, 10), Rect(5, 5, 9, 9), Rect(1, 1, 1, 1) ]`

.reduce!smallestContainer == Rect(1, 1, 13, 14)

I also have an exptime algorithm for the torus-smallest container: For each rectangle in the input list, try whether to set its top-left point in the range `[0, M.xl[` or into `[M.xl, 2 * M.xl[` instead. With an input list of length n, we have 2^{n} choices to try. For each choice, measure with the non-torus algorithm. Use the choice that minimizes the non-torus algorithm target value.

Can I do it in less than exptime?

-- Simon