Books on a Shelf

Question

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.

Answer 1

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)

Answer 2

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)

Answer 3

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