6
$\begingroup$

I made up the following problem but have not made any headway in solving it in anything less than exponential time. Hopefully somebody can shed some light on it. I'm starting to think it may be $\sf{NP}$-Complete.

I created a programming challenge type description to encourage my CS friends to have a go at it.


Charlie likes to draw.

He’s given a piece of paper of width $W$ and height $H$ and a list of $N$ numbers $a_1, a_2, a_3, ... a_N$

For each number, he wants to draw a rectangle on the piece of paper. If the rectangle has width $w$ and height $h$ then $w > 0, h > 0, w \geq h$ and $w \leq W$ and $h \leq H$. Both w and h must be positive integers.

If a number $a_x > a_y$, then $a_x$’s rectangle must have area bigger or equal to $a_y$’s rectangle, where area is $w*h$. If $a_x = a_y$, then they can have different areas.

Charlie doesn’t like to waste ink. For a rectangle of width $w$ and height $h$, he must draw a line of length $2w + 2h$, using $2w + 2h$ units of ink. Clarification: even if two rectangles are adjacent, the adjacent side must be drawn twice.

What is the least units of ink that Charlie can use, drawing one rectangle for each number on the piece of paper, such that no rectangles overlap and the whole paper is covered by rectangles?

Input File:
Line 1       : The width W and height H of the piece of paper, separated by spaces
Line 2       : N, the number of numbers to draw
Lines 3..N+2 : One number on each line.

Constraints: 
W and H are positive integers <= 1000
N is a positive integer <= W * H 
ax, where 1  <= x <= N, is a positive integer <= 1000

Output file:
A single line containing the least units of ink Charlie can use.

Bonus:

Output, for each number ax, the position and size of its rectangle on the piece of paper for a solution that uses the least amount of ink (there can be more than one).

Sample input file:

2 2
4
1
1
1
1

Sample output file:

16

Sample bonus:

-----
| | |
-----
| | |
-----

As pointed out by Marzio, here's the decision problem version:

Given a $W × H$ paper, the numbers $a_1..a_N$ and an amount $K$ of ink, can the $N$ rectangles be drawn, filling the entire paper, as described above?

$\endgroup$
  • $\begingroup$ Just a note: you should convert it to a decision problem, i.e. "Given a $W \times H$ paper, the numbers $a_1..a_N$ and an amount $K$ of ink, can the $N$ rectangles be drawn?" $\endgroup$ – Marzio De Biasi Apr 6 '13 at 20:07
  • 8
    $\begingroup$ Since you don't care about the actual values of the $a_i$, a simpler version of your problem is that you want to divide a $W \times H$ grid into $n$ rectangular pieces while minimizing the total length of fencing used. If you solve this, then you merely sort the resulting rectangle areas and then assign them to the input numbers (it's easier here to assume that all numbers are distinct) $\endgroup$ – Suresh Venkat Apr 6 '13 at 20:32
  • 1
    $\begingroup$ To me, this seems more suitable for Computer Science. $\endgroup$ – Kaveh Apr 6 '13 at 23:41
  • 1
    $\begingroup$ Without loss of generality, for all $i$, either $a_i = a_{i-1}$ or $a_i = a_{i-1} + 1$. Right? $\endgroup$ – Jeffε Apr 7 '13 at 23:34
  • 1
    $\begingroup$ @Alexandre: now that some details are clear, you can also consider to drop the ink minimization constraint and get a "simpler???" problem: "Given a WxH paper and a list of N area ranks, can we draw all the (integer sized) rectangles on the paper? (without ink constraints) $\endgroup$ – Marzio De Biasi Apr 8 '13 at 10:39
4
$\begingroup$

A closely related problem is strongly NP-hard.

Leung et al. [1] prove that the following decision version of your problem is strongly NP-complete, by reduction from 3-Partition.

Is it possible to pack $n$ squares of given widths $w_1, w_2, \dots, w_n$ into a larger square of width $W$?

I misread the original question as a generalization of the following decision problem:

Is it possible to pack $n$ rectangles with given areas $a_1, a_2, \dots, a_n$ into a $H\times W$ rectangle?

The first problem can be reduced to the second as follows: Squares with widths $w_1,\dots,w_n$ can be packed into an outer square of width $W$ if and only if the minimum-perimeter packing of rectangles with areas $w_1^2, \dots, w_n^2$ into a $W\times W$ rectangle uses precisely $4\sum_i w_i$ units of ink. (Proof: The minimum-perimeter rectangle with any given area is a square.)

However, this reduction does not imply that the actual posted question is NP-hard.

  1. Joseph Y-T. Leung, Tommy W. Tam, C. S. Wong, Gilbert H. Young, and Francis Y. L. Chin. Packing squares into a square. J. Parallel and Distributed Computing 10(3):271–275, 1990.
$\endgroup$
  • 1
    $\begingroup$ @JeffE: but in the OP's question the areas of the rectangles are not given (there is only a bigger/smaller constraint according to the corresponding $a_i, a_j$). But perhaps I misinterpreted it ?!? $\endgroup$ – Marzio De Biasi Apr 7 '13 at 21:00
  • $\begingroup$ Hmm. I interpreted $a_i$ as the area of the $i$th rectangle — otherwise why use the letter $a$? But maybe it only means the area rank of the $i$th rectangle. $\endgroup$ – Jeffε Apr 8 '13 at 0:45
  • 1
    $\begingroup$ Yes, the problem is actually about area ranks, rather than area. $\endgroup$ – Suresh Venkat Apr 8 '13 at 6:08
  • $\begingroup$ Correct, the relations between the $a_x$ yields area rank, not area. Does your reduction still hold? $\endgroup$ – Alexandre Apr 8 '13 at 9:47
0
$\begingroup$

this is only a sketch of an idea. Not sure if it yields an optimal solution.

Following my comment above, the only parameter that matters is $n$, the number of rectangles. Since it isn't clear whether strict inequality matters, I'll assume that areas can be equal even if the numbers aren't, but that reverse ordering is prohibited.

It seems that a lower bound for the problem is $2n$, assuming you're drawing on a grid (otherwise by @JeffE's comment, the problem doesn't make sense). This is implied by the claim that each new rectangle needs at least 2 units of ink (amortized), because it can be associated with (say) its lower right hand corner, which needs to extend nontrivially.

Here's a scheme that yields this bound upto terms that vanish with $n$. WLOG assume that $H < W$ and $n < WH$. If $n = 2$, then the only solution is to draw a line of length $H$ dividing the rectangle into two parts, and it doesn't matter where you draw it.

Suppose now that $n < H+1$. Then draw the length $H$ line to create a strip of unit "width", and then repeatedly subdivide that strip to get the desired number of pieces. It's not hard to see that the total ink used is roughly $H + n-2$. As $n$ increases, create more unit width strips and subdivide them. A quick calculation shows that as $n$ increases, you pay roughly $2H$ for each "full" strip and the last strip is negligible, yielding the bound.

I suspect that (a) this is not optimal and (b) this doesn't quite capture the spirit of what you need. But it does answer the question as stated.

$\endgroup$
  • $\begingroup$ each new rectangle needs at least 2 units of ink (amortized) — As I read the problem, the cost is the sum of the perimeters of the rectangles. In particular, if the boundaries of two rectangles overlap, you have to pay for the length of that overlap twice. So each new rectangle needs at least four units of ink. $\endgroup$ – Jeffε Apr 9 '13 at 13:52
  • $\begingroup$ @JɛffE: Correct! $\endgroup$ – Alexandre Apr 9 '13 at 14:53
  • $\begingroup$ I see. that doesn't change the argument, because the upper bound calculation didn't overcount ink. However, @Alexandre's earlier comment renders this answer invalid, since my solution doesnt guarantee distinct area sizes - there may be a way to perturb it, but that would break the claim on asymptotic optimality. $\endgroup$ – Suresh Venkat Apr 9 '13 at 15:36
  • $\begingroup$ @SureshVenkat: Sorry about my earlier comment. It was incorrect. I will revise your solution and comment asap. $\endgroup$ – Alexandre Apr 9 '13 at 20:48
0
$\begingroup$

Following Suresh's observation that the problem consists of splitting the W x H rectangle into N rectangles, using as little ink as possible, I experimented with some things.

I wrote a brute-force algorithm (p_brute_force() below) and observed a recursive pattern in the solution. The answer seemed to be breaking the W x H rectangle into two rectangles, for example W - i x H and i x H, in a way that a) obeys the constraints and b) minimizes ink for the sub-rectangles.

I implemented this recursion in the p() algorithm below and, hurray, it matches the brute force answers for the tests below. I couldn't run many more tests because of the exponential time of the brute-force algorithm, but p() does seem to yield an optimal solution. I will have to think about the proof optimality, but I believe this to be the answer to the Drawing Challenge. If so, $Drawing Challenge \in P$ :)

import itertools

mem_p = {}
def p(w, h, n):
    ident = (w, h, n)
    if ident in mem_p:
        return mem_p[ident]
    if n < 1 or w < 1 or h < 1:
        return None
    if w * h == n:
        return n * 4
    if n == 1:
        if w < h:
            return None
        return 2 * (w + h)
    ink = []
    for i in xrange(1, w):
        if i < h:
            continue
        try:
            ink.append(2 * (i + h) + p(w - i, h, n - 1))
        except TypeError:
            pass
    for i in xrange(1, h):
        if i > w:
            continue
        try:
            ink.append(2 * (i + w) + p(w, h - i, n - 1))
        except TypeError:
            pass
    v = None
    if ink:
        v = min(ink)
    mem_p[ident] = v
    return v


def intersect(r1, r2):
    return r1[0] < r2[1] and r1[1] > r2[0] and r1[2] < r2[3] and r1[3] > r2[2]

def x_y_tuple(r):
    x1 = r[0]
    x2 = x1 + r[2]
    y1 = r[1]
    y2 = y1 + r[3]
    return (x1, x2, y1, y2)

def line_length(c):
    return sum([2 * (v[2] + v[3]) for v in c])

def p_brute_force(W, H, N):
    r = []
    for xi in range(W):
        for yi in range(H):
            # origin = (xi, yi)
            for w in range(1, W + 1 - xi):
                #for h in range(1, H + 1 - yi):
                for h in range(1, w + 1):
                    r.append((xi, yi, w, h))
    s = []
    for c in itertools.combinations(r, N):
        valid = True
        for r1, r2 in itertools.combinations(c, 2):
            if intersect(x_y_tuple(r1), x_y_tuple(r2)):
                valid = False
                break
        if valid:
            for v in c:
                if v[0] + v[2] > W or v[1] + v[3] > H:
                    valid = False
                    break
            if valid:
                area = sum([v[2] * v[3] for v in c])
                if not area == W * H:
                    continue
                #print 'found a valid solution'
                #print c
                #print 'ink = ', line_length(c)
                s.append(c)
    b = sorted(s, key=lambda v: line_length(v))
    if not b:
        return None
    #print 'best solution'
    #print b[0]
    #print 'ink = ', line_length(b[0])
    return line_length(b[0])

import sys
print p(100, 100, 100)
sys.exit(0)
for i in range(1, 5):
    for j in range(1, 5):
        for k in range(1, min(5, i * j)):
            a = p(i, j, k)
            b = p_brute_force(i, j, k)
            if not a == b:
                print i, j, k
                print a, b
                print 'no match'
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.