Eu tenho alguns livros e uma estante de livros. Gostaria de colocar o maior número possível de livros na prateleira, mas tenho uma regra. Todas as dimensões dos livros (altura, largura e profundidade) devem formar uma sequência não crescente na prateleira.

Isso significa que todos os livros devem ser pelo menos tão altos quanto os que são depois dele. O mesmo vale para a largura e profundidade. Você não pode girar os livros para trocar sua altura, largura e profundidade.

Você deve escrever um programa ou função que, considerando as dimensões de todos os livros como saída, retorne o número máximo de livros que posso colocar na estante.

Entrada

• Uma lista de trigêmeos de números inteiros positivos, onde cada trigêmeo define a altura, largura e profundidade de um livro.
• Haverá pelo menos um trio na lista de entrada.
• Dois livros podem ter os mesmos comprimentos em qualquer número de dimensões.

Resultado

• Um número inteiro positivo único, o número máximo de livros que cabem na prateleira, obedecendo à regra.

Complexidade do tempo

Seu algoritmo deve ter um polinômio de complexidade de pior caso no número de livros. Isso significa que, por exemplo, todas as seguintes complexidades de tempo são válidas: O (N ^ 3), O (log (N) * N ^ 2), O (N) e as seguintes são inválidas: O (2 ^ N), O (N!), O (N ^ N).

Exemplos

Entrada => Saída

(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

Este é o código de golfe, portanto a entrada mais curta vence.

Um desafio relacionado à classificação de livros: Book Stack Sort .

Python 3: 436 bytes

No começo, vi isso como o problema NP-completo de encontrar o caminho simples mais longo em um gráfico direcionado com ciclos. No entanto, todos os ciclos no gráfico (na verdade um subgráfico completo) podem ser representados como um único vértice. Em outras palavras, trate livros idênticos como um livro, para serem colocados na prateleira como uma unidade. Podemos então construir um gráfico acíclico direcionado onde a-> b significa que b pode seguir a na prateleira. Finalmente, encontramos a altura máxima das árvores externas usando um método recursivo.

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)

Pitão, 40 bytes

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

Não é rápido, mas é polinomial.

Equivalente ao Python3:

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)

Python 2, 231 bytes

Experimente aqui

Meu programa atualmente está errado nos dois últimos exemplos. Alguém pode me ajudar a consertar isso, por favor? Obrigado.

Classifico a lista de todas as 6 ordens de permutação possíveis das 3 dimensões, depois vejo qual é a relação de ordenação contínua mais longa da lista e, em seguida, encontro o máximo delas.

Além disso, eu sei se posso jogar muito mais, mas não consegui descobrir se poderia usar reduceisso. Simplificando, esse caminho era o mais fácil de fazer em um tempo razoável sem meu cérebro explodir.

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