Editar: rompecabezas de recompensas al final de la pregunta.

Dado un conjunto de números de 1 dígito, debe determinar qué tan alto pueden construir una torre.

Los dígitos viven en un plano horizontal con un nivel del suelo donde pueden pararse. Ningún dígito quiere confundirse con un número de varios dígitos, por lo que siempre tienen un espacio vacío en ambos lados.

4 2  1 9  6  8

Un dígito puede estar encima de otro:

2
6

o puede ser soportado por otros dos en diagonal debajo de él:

 9
5 8

El (los) inferior (es) debe (n) soportar el peso que soporta el superior (si lo hay), más el peso del superior, que siempre es 1 . Si hay dos seguidores, dividen el peso total de la parte superior de manera uniforme (50% -50%).

El peso de cada dígito es 1 independientemente de su valor.

Si un dígito admite otros dos, debe ser capaz de soportar la suma de su peso correspondiente. Un dígito puede soportar como máximo su valor numérico.

Algunas torres válidas (con alturas 4, 3y 5):

            0          
7           1
5    1     1 1         9 supports a total weight of 1.5 = (1+1/2)/2 + (1+1/2)/2
2   5 4    5 5        
3  5 9 5  5 6 3        6 supports a total weight of 3 =  1.5 + 1.5 = (2*1+(2*1/2))/2 + (2*1+(2*1/2))/2

Algunas torres inválidas:

1         5           The problems with the towers are (from left to right):
1  12    2 3     8      1 can't support 1+1; no space between 1 and 2;
1  5 6  1 1 1   9       1 can't support 1.5 = (1+1/2)/2 + (1+1/2)/2; 8 isn't properly supported (digits at both bottom diagonals or exactly below the 8)    

Debe escribir un programa o función que proporcione una lista de dígitos como salidas de entrada o que devuelva la altura de la torre más alta que se puede construir utilizando algunos (tal vez todos) de esos dígitos.

Entrada

• Una lista de números de un solo dígito no negativos con al menos un elemento.

Salida

• Un solo entero positivo, la altura de la torre construible más alta.
• Su solución tiene que resolver cualquier caso de prueba de ejemplo en menos de un minuto en mi computadora (solo probaré casos cercanos. Tengo una PC por debajo del promedio).

Ejemplos

El formato es Input list => Output numbercon una posible torre en las siguientes líneas que no es parte de la salida.

[0]  =>  1

0

[0, 1, 1, 1, 1, 1]  =>  3

  0
  1
 1 1

[1, 1, 1, 1, 1, 2, 2]  =>  4

   1
   1
  1 1
 1 2 2

[0, 0, 2, 2, 2, 2, 2, 5, 5, 5, 7, 7, 9]  =>  9

0
2
2
5
5
5
7
7
9

[1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5]  =>  9

   1
   2
   2
   3
   4
   5
  3 3
 4 4 4
5 5 5 5

[0, 0, 0, 0, 0, 1, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 7, 7, 9]  =>  11

   0
   1
   2
   3
   4
   5
  3 3
  4 5
  5 5
 3 7 3
2 7 9 2

[0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9]  =>  12

 0
 1
 2
 3
 4
 5
 6
 7
4 5
6 7
8 8
9 9

[0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9]  =>  18

      0
      1
      2
      3
      4
      5
      6
      7
      8
      9
     5 5
     6 6
     7 7
    4 8 4
   3 7 7 3
  2 6 8 6 2
 2 5 8 8 5 2
 3 9 9 9 9 3

Este es el código de golf, por lo que gana la entrada más corta.

Generosidad

Otorgaré 100 recompensas de reputación (no relacionadas con la ya otorgada) por resolver el problema extendido a continuación en tiempo polinómico (con respecto a la longitud de la lista de entrada) o probar que no es posible (suponiendo P! = NP). Detalles del problema extendido:

• los números de entrada pueden ser enteros no negativos, no solo dígitos
• los números de varios dígitos ocupan el mismo lugar que los números de un solo dígito
• los números de varios dígitos pueden soportar su valor numérico, por ejemplo, 24pueden soportar24

La oferta de recompensa no tiene fecha de vencimiento. Agregaré y recompensaré la recompensa si aparece una prueba.

Python 2 - 326

Se ejecuta fácilmente por debajo del límite de tiempo para todos los ejemplos dados, aunque sacrifiqué algo de eficiencia por el tamaño, lo que probablemente sería notable con entradas mucho más grandes. Ahora que lo pienso, sin embargo, dado que solo se permiten números de un solo dígito, la torre más grande posible puede no ser muy grande, y me pregunto cuál es el máximo.

def S(u,c=0,w=[]):
 for(s,e)in[(len(w),lambda w,i:w[i]),(len(w)+1,lambda w,i:.5*sum(([0]+w+[0])[i:i+2]))]:
    m=u[:];l=[-1]*s
    for n in u:
     for i in range(s):
        if 0>l[i]and n>=e(w,i):m.remove(n);l[i]=n;break
    if([]==l or-1in l)==0:
     for r in S(m,c+1,[1+e(w,i)for i in range(s)]):yield r
 yield c
print max(S(sorted(input())))