13
\$\begingroup\$

I have some books and a bookshelf. I would like to put as many books on the shelf as possible but I have a rule. All dimensions of the books (height, width and depth) should form a non-increasing sequence on the shelf.

This means every books has to be at least as high as the ones after it on the self. The same goes for the width and depth. You can not rotate the books to swap their height, width and depth.

You should write a program or function which given the dimensions of all the books as input outputs or returns the maximal number of books I can put on the shelf.

Input

  • A list of triplets of positive integers where each triplet defines a book's height, width and depth.
  • There will be at least one triplet in the input list.
  • Two books can have the same lengths along any number of dimensions.

Output

  • A single positive integer, the maximal number of books that fit on the shelf obeying the rule.

Time complexity

Your algorithm should have a worst-case time complexity polynomial in the number of books. This means that for example the following time complexities are all valid: O(N^3), O(log(N)*N^2), O(N) and the following ones are invalid: O(2^N), O(N!), O(N^N).

Examples

Input => Output

(1, 1, 1) =>  1

(5, 2, 5), (1, 3, 5) =>  1

(5, 2, 5), (1, 2, 5) =>  2

(2, 2, 2), (2, 2, 2), (2, 2, 2), (1, 3, 6) =>  3

(1, 2, 5), (1, 3, 5), (1, 2, 8), (1, 2, 5), (7, 7, 7) =>  4

(5, 19, 3), (9, 4, 16), (15, 16, 13), (7, 4, 16), (1, 13, 14), (20, 1, 15), (9, 8, 19), (4, 11, 1) =>  3

(1, 1, 18), (1, 13, 7), (14, 1, 17), (8, 15, 16), (18, 8, 12), (8, 8, 15), (10, 1, 14), (18, 4, 6), (10, 4, 11), (17, 14, 17), (7, 10, 10), (19, 16, 17), (13, 19, 2), (16, 8, 13), (14, 6, 12), (18, 12, 3) =>  5

This is code golf so the shortest entry wins.

A related interesting book sorting challenge: Book Stack Sort.

\$\endgroup\$
2
  • \$\begingroup\$ Do you mean it should form a decreasing sequence? That's what you get if each book is at least as high as the book after it, unless every book is the same height. \$\endgroup\$
    – mbomb007
    May 6, 2015 at 20:20
  • \$\begingroup\$ @mbomb007 Right, changed "non-decreasing" to "non-increasing". \$\endgroup\$
    – randomra
    May 6, 2015 at 21:01

3 Answers 3

4
\$\begingroup\$

Python 3: 436 bytes

At first I saw this as the NP-complete problem of finding the longest simple path in a directed graph with cycles. However, every cycle in the graph (actually a complete subgraph) can be represented as a single vertex. In other words, treat identical books as one book, to be placed on the shelf as a unit. We can then construct a directed acyclic graph where a->b means b could follow a on the shelf. Finally, we find the maximum height of the out tree(s) using a recursive method.

import sys
b=[]
n={}
r=[]
for L in sys.stdin.readlines():z=[int(x)for x in L.split()];r+=[z];z in b or b+=[z]
def l(a,b):return a[0]<=b[0]and a[1]<=b[1]and a[2]<=b[2]
R=range(len(b))
for i in R: 
    n[i]=[]
    for j in R:i!=j and l(b[i],b[j])and n[i]+=[j]
def L(t):
    global v;best=0
    if t in v:
            return v[t]
    for s in n[t]:best=max(best,L(s)+1)
    v[t]=best+r.count(b[t])-1;return best
m=0
for i in R:v={};m=max(L(i)+1,m)
print(m)
\$\endgroup\$
1
  • 1
    \$\begingroup\$ This is a nice solution, but it isn't really golfed yet. I'll upvote once it is. \$\endgroup\$
    – isaacg
    May 6, 2015 at 22:10
3
\$\begingroup\$

Pyth, 40 bytes

KYleolNe.eaK+e+]])olNf.A.eg@YbZeT<Kk]YSQ

Not fast, but it is polynomial.

Python3 equivalent:

def num_books(l):
    l = sorted(l)
    s = []
    for i, Y in enumerate(l):
        s.append(max([T for T in s[:i]
                      if all(Y[e] >= t for e, t in enumerate(T[-1]))] + [[]],
                     key=len) + [Y])
    return max(len(u) for u in s)
\$\endgroup\$
1
  • \$\begingroup\$ The Python 3 version is 177 bytes with the obvious golfs. Just an fyi. \$\endgroup\$
    – mbomb007
    May 8, 2015 at 21:32
0
\$\begingroup\$

Python 2, 231 bytes

Try it here

My program currently gets the last two examples wrong. Can someone help me fix it, please? Thanks.

I sort the list all of the 6 possible permutation orders of the 3 dimensions, then see what the longest continuous ordering relation is in the list, then find the max of those.

Also, I know if can be golfed a lot more, but I couldn't figure out if I could use reduce to do this. Simply put, this way was the easiest to make in a reasonable time without my brain exploding.

from operator import*
from itertools import*
def f(t):
    m=1
    for l in(sorted(t,key=itemgetter(*o))for o in permutations(range(3))):
        c=1
        for k in range(len(l)-1):
            c+=all(i<=j for i,j in zip(l[k],l[k+1]))
        m=max(m,c)
    print m
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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