Bearbeiten: Kopfgeldrätsel am Ende der Frage.

Ausgehend von einer Reihe von einstelligen Zahlen sollten Sie bestimmen, wie hoch ein Turm sein kann, den sie bauen können.

Die Ziffern leben auf einer horizontalen Ebene mit einer Bodenhöhe, auf der sie stehen können. Keine Ziffer möchte mit einer mehrstelligen Zahl verwechselt werden, daher haben sie auf beiden Seiten immer ein Leerzeichen.

4 2  1 9  6  8

Eine Ziffer kann über einer anderen stehen:

2
6

oder kann von zwei anderen diagonal darunter getragen werden:

 9
5 8

Die untere (n) Person (en) müssen das Gewicht tragen, das die obere (n) trägt (falls vorhanden), plus das Gewicht der oberen Person, das immer 1 ist . Wenn es zwei Unterstützer gibt, teilen sie das Gesamtgewicht des Oberen gleichmäßig auf (50% -50%).

Das Gewicht jeder Ziffer ist 1, unabhängig von ihrem Wert.

Wenn eine Ziffer zwei andere unterstützt, muss sie die Summe ihres entsprechenden Gewichts unterstützen können. Eine Ziffer kann höchstens ihren numerischen Wert unterstützen.

Einige gültigen Türme (mit Höhen 4, 3und 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

Einige ungültige Türme:

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)    

Sie sollten ein Programm oder eine Funktion schreiben, die eine Liste von Ziffern als Eingabe-Ausgabe enthält oder die Höhe des höchsten Turms zurückgibt, der unter Verwendung einiger (möglicherweise aller) dieser Ziffern erstellt werden kann.

Eingang

• Eine Liste nicht negativer einstelliger Zahlen mit mindestens einem Element.

Ausgabe

• Eine einzelne positive ganze Zahl, die Höhe des höchsten konstruierbaren Turms.
• Ihre Lösung muss jeden Beispieltestfall auf meinem Computer in weniger als einer Minute lösen (ich teste nur enge Fälle. Ich habe einen unterdurchschnittlichen PC.).

Beispiele

Das Format ist Input list => Output numbermit einem möglichen Turm in den nächsten Zeilen, der nicht Teil der Ausgabe ist.

[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

Dies ist Code-Golf, also gewinnt der kürzeste Eintrag.

Kopfgeld

Ich werde 100 Reputationsprämie (unabhängig von der bereits vergebenen) für die Lösung des erweiterten Problems in Polynomzeit (in Bezug auf die Länge der Eingabeliste) oder für den Nachweis, dass dies nicht möglich ist (unter der Annahme von P! = NP) vergeben. Details des erweiterten Problems:

• Eingabenummern können beliebige nicht negative ganze Zahlen sein, nicht nur Ziffern
• Mehrstellige Nummern nehmen den gleichen Platz ein wie einstellige Nummern
• Mehrstellige Zahlen können den numerischen Wert unterstützen, z. B. 24unterstützen24

Das Kopfgeldangebot hat kein Ablaufdatum. Ich werde das Kopfgeld hinzufügen und belohnen, wenn ein Beweis erscheint.

Python 2 - 326

Läuft problemlos unter dem Zeitlimit für alle angegebenen Beispiele, obwohl ich bei der Größe einen gewissen Wirkungsgrad geopfert habe, der sich bei viel größeren Eingaben wahrscheinlich bemerkbar machen würde. Nun, da ich darüber nachdenke, ist der größtmögliche Turm möglicherweise nicht sehr groß, da nur einstellige Zahlen zulässig sind, und ich frage mich, was das Maximum ist.

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