21
2
When stacking books you usually want to put the largest ones at the bottom and the smallest ones at the top. However, my latent OCD makes me feel very uneasy if I've got two books where one is shorter (in height) but wider than the other. No matter which order I place them in, the top book will extend beyond the bottom book on one side.
As an example, say one book has dimensions (10,15)
and another has dimensions (11,14)
. No matter which way around I put them, I get an overhang. But if I have books with dimensions (4,3)
and (5,6)
, I can avoid an overhanging by placing the latter below the former.
For the purposes of this challenge we will consider overhangs only in relation to the book immediately below. E.g. if I have a stack (5,5)
, (3,3)
, (4,4)
(not that any sane person would do that), the top book counts as an overhang, although it does not extend beyond the bottom book. Similarly, the stack (3,3)
, (3,3)
, (4,4)
also has only one overhang, despite the top book extending beyond the bottom one.
The Challenge
Given a list of integer pairs for book dimensions, sort those pairs/books such that the number of overhangs is minimal. You must not rotate the books - I want all the spines facing the same direction. If there are multiple solutions with the same number of overhangs, you may choose any such order. Your sorting algorithm does not have to be stable. Your implementation may assume that book dimensions are less than 216 each.
Time complexity: To make this a bit more interesting, the asymptotic worst-case complexity of your algorithm must be polynomial in the size of the stack. So you can't just test every possible permutation. Please include a short proof of your algorithm's optimality and complexity and optionally a plot that shows the scaling for large random inputs. Of course, you can't use the maximum size of the input as argument that your code runs in O(1).
You may write a program or function, take input via STDIN, ARGV or function argument in any convenient (not preprocessed) list format and either print or return the result.
This is code golf, so the shortest answer (in bytes) wins.
I am confident that a polynomial-solution exists, but if you can prove me wrong, you may submit such a proof instead of a golfed submission. In this case, you may assume P ≠ NP. I will accept the first correct such proof and award a bounty to it.
Examples
In: [[1, 1], [10, 10], [4, 5], [7, 5], [7, 7], [10, 10], [9, 8], [7, 5], [7, 5], [3, 1]]
Out: [[10, 10], [10, 10], [9, 8], [7, 7], [7, 5], [7, 5], [7, 5], [4, 5], [3, 1], [1, 1]]
In: [[4, 5], [5, 4], [5, 4], [5, 4], [5, 4], [4, 5], [4, 5], [4, 5], [5, 4], [4, 5]]
Out: [[4, 5], [4, 5], [4, 5], [4, 5], [4, 5], [5, 4], [5, 4], [5, 4], [5, 4], [5, 4]]
or [[5, 4], [5, 4], [5, 4], [5, 4], [5, 4], [4, 5], [4, 5], [4, 5], [4, 5], [4, 5]]
In: [[2, 3], [1, 1], [5, 5], [7, 1]]
Out: [[5, 5], [2, 3], [7, 1], [1, 1]]
or [[5, 5], [2, 3], [1, 1], [7, 1]]
or [[7, 1], [5, 5], [2, 3], [1, 1]]
or [[7, 1], [1, 1], [5, 5], [2, 3]]
I created these by hand, so let me know if you spot any mistakes.
3Are you certain that finding a solution with a minimum number of overhangs can be solved in polynomial time? – COTO – 2014-10-24T01:05:40.303
@COTO I'm fairly confident, yes. – Martin Ender – 2014-10-24T01:59:08.317
Hmm. I'd ordinarily tackle it with a greedy algorithm, but I can easily procure inputs leading to suboptimal outputs for any "greed" criterion I can come up with (e.g. area, maximize one dimension, maximize smallest dimension, etc.). The only other approaches I can think of involve partitioning the books into cliques, and all of them have exponential worst-case complexity. I'll be interested to see what answers come up. You might also want to request a brief proof of the optimality of the sort as part of the spec. – COTO – 2014-10-24T02:05:14.800
@COTO I've added a paragraph about this in case I'm actually wrong, but don't count on it. ;) – Martin Ender – 2014-10-24T02:43:20.637
Just in case, potential proofs that no polynomial-time algorithm exists should be allowed to assume that P does not equal NP. – xnor – 2014-10-24T06:09:57.777
Why [tag:code-golf]? Why not [tag:code-challenge] and have a set of test cases and the one with least number of overhangs wins? – justhalf – 2014-10-24T07:50:47.530
@justhalf Optimisation challenges seem to be more suitable for NP-hard problems. With polynomial-time solutions it would be very hard to get test case size and time limit right to prevent optimal solutions. However, this challenge was originally intended to be harder (minimising the overlapping area and potentially allowing books to be rotated) - I have a feeling that this variant might be NP-hard, in which case I might post that as a code challenge some time in the future. – Martin Ender – 2014-10-24T10:26:10.363
@MartinBüttner: I see. I forgot that some questions did face that issue, having too many submissions of optimal solutions. Sorry if I sounded too harsh, I just personally don't like code-golf :) – justhalf – 2014-10-24T10:32:27.347
I've put out a request for assistance on Math.SE, hence hopefully we can resolve the dilemma. ;)
– COTO – 2014-10-24T11:06:04.043