Tengo algunos libros y una estantería. Me gustaría poner tantos libros en el estante como sea posible, pero tengo una regla. Todas las dimensiones de los libros (altura, ancho y profundidad) deben formar una secuencia no creciente en el estante.

Esto significa que todos los libros tienen que ser al menos tan altos como los que están detrás de él. Lo mismo ocurre con el ancho y la profundidad. No puede girar los libros para intercambiar su altura, ancho y profundidad.

Debería escribir un programa o función que, dado las dimensiones de todos los libros como entradas o salidas, devuelva el número máximo de libros que puedo poner en el estante.

Entrada

• Una lista de trillizos de enteros positivos donde cada trillizo define la altura, el ancho y la profundidad de un libro.
• Habrá al menos un triplete en la lista de entrada.
• Dos libros pueden tener la misma longitud a lo largo de cualquier cantidad de dimensiones.

Salida

• Un solo entero positivo, el número máximo de libros que caben en el estante obedeciendo la regla.

Complejidad de tiempo

Su algoritmo debe tener un polinomio de complejidad de tiempo en el peor de los casos en el número de libros. Esto significa que, por ejemplo, las siguientes complejidades temporales son todas válidas: O (N ^ 3), O (log (N) * N ^ 2), O (N) y las siguientes no son válidas: O (2 ^ N), O (N!), O (N ^ N).

Ejemplos

Entrada => Salida

(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 es el código de golf, por lo que gana la entrada más corta.

Un desafío interesante relacionado con la clasificación de libros: Book Stack Sort .

Python 3: 436 bytes

Al principio, vi esto como el problema NP-completo de encontrar la ruta simple más larga en un gráfico dirigido con ciclos. Sin embargo, cada ciclo en el gráfico (en realidad, un subgráfico completo) se puede representar como un solo vértice. En otras palabras, trate los libros idénticos como un libro, para colocarlos en el estante como una unidad. Luego podemos construir un gráfico acíclico dirigido donde a-> b significa que b podría seguir a a en el estante. Finalmente, encontramos la altura máxima de los árboles de salida usando un 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)

Pyth, 40 bytes

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

No es rápido, pero es polinomial.

Python3 equivalente:

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

Pruébalo aquí

Mi programa actualmente tiene los dos últimos ejemplos incorrectos. ¿Alguien puede ayudarme a arreglarlo, por favor? Gracias.

Ordeno la lista de los 6 posibles órdenes de permutación de las 3 dimensiones, luego veo cuál es la relación de orden continua más larga en la lista, luego encuentro el máximo de esos.

Además, sé si se puede jugar mucho más al golf, pero no pude averiguar si podría reducehacerlo. En pocas palabras, esta forma fue la más fácil de hacer en un tiempo razonable sin que mi cerebro explotara.

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