Edit: puzzle Bounty à la fin de la question.

Étant donné un ensemble de nombres à 1 chiffre, vous devez déterminer la hauteur d'une tour qu'ils peuvent construire.

Les chiffres vivent sur un plan horizontal avec un niveau au sol où ils peuvent se tenir. Aucun chiffre ne veut être confondu avec un numéro à plusieurs chiffres, ils ont donc toujours un espace vide de chaque côté.

4 2  1 9  6  8

Un chiffre peut être au-dessus d'un autre:

2
6

ou peut être supporté par deux autres diagonales en dessous:

 9
5 8

Le ou les bas doivent supporter le poids que le supérieur supporte (s'il y en a), plus le poids du haut qui est toujours 1 . S'il y a deux supporters, ils partagent également le poids total du supérieur (50% -50%).

Le poids de chaque chiffre est de 1 indépendamment de sa valeur.

Si un chiffre en supporte deux autres, il doit pouvoir supporter la somme de leur poids correspondant. Un chiffre peut prendre en charge au plus sa valeur numérique.

Quelques tours valides (avec des hauteurs 4, 3et 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

Quelques tours invalides:

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)    

Vous devez écrire un programme ou une fonction qui a donné une liste de chiffres comme sorties d'entrée ou renvoie la hauteur de la tour la plus élevée constructible en utilisant certains (peut-être tous) de ces chiffres.

Contribution

• Une liste de nombres à un chiffre non négatifs avec au moins un élément.

Production

• Un seul entier positif, la hauteur de la plus haute tour constructible.
• Votre solution doit résoudre tout exemple de cas de test en moins d'une minute sur mon ordinateur (je ne testerai que les cas fermés. J'ai un PC inférieur à la moyenne.).

Exemples

Le format est Input list => Output numberavec une tour possible sur les lignes suivantes qui ne fait pas partie de la sortie.

[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

C'est le golf de code, donc l'entrée la plus courte l'emporte.

Prime

Je vais attribuer 100 primes de réputation (sans rapport avec celle déjà attribuée) pour résoudre le problème étendu ci-dessous en temps polynomial (en ce qui concerne la longueur de la liste d'entrée) ou prouver que ce n'est pas possible (en supposant P! = NP). Détails du problème étendu:

• les numéros d'entrée peuvent être des entiers non négatifs, pas seulement des chiffres
• les numéros à plusieurs chiffres occupent la même place que les numéros à un chiffre
• les nombres à plusieurs chiffres peuvent prendre en charge leur valeur numérique, par exemple 24peuvent prendre en charge24

L'offre de prime n'a pas de date d'expiration. J'ajouterai et récompenserai la prime si une preuve apparaît.

Python 2 - 326

Fonctionne facilement sous la limite de temps pour tous les exemples donnés, bien que j'ai sacrifié une certaine efficacité pour la taille, ce qui serait probablement perceptible compte tenu des entrées beaucoup plus importantes. Maintenant que j'y pense cependant, puisque seuls les chiffres à un seul chiffre sont autorisés, la plus grande tour possible peut ne pas être très grande, et je me demande quel est le maximum.

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())))