Edycja: Łamigłówka na końcu pytania.

Biorąc pod uwagę zestaw liczb 1-cyfrowych, powinieneś określić, jak wysoką wieżę mogą zbudować.

Cyfry żyją na płaszczyźnie poziomej z poziomem ziemi, na którym mogą stać. Żadnej cyfry nie chce się mylić z liczbą wielocyfrową, więc zawsze mają puste miejsce po obu stronach.

4 2  1 9  6  8

Cyfra może znajdować się na innej:

2
6

lub może być wspierany przez dwie inne po przekątnej:

 9
5 8

Dolny (-e) musi podtrzymywać ciężar, który górny (o ile taki istnieje), oraz ciężar górnego, który zawsze wynosi 1 . Jeśli jest dwóch kibiców, dzielą wagę całkowitą górnego równomiernie (50% -50%).

Waga każdej cyfry wynosi 1 niezależnie od jej wartości.

Jeśli jedna cyfra obsługuje dwie inne, musi być w stanie utrzymać sumę odpowiadającej jej wagi. Cyfra może obsługiwać co najwyżej jej wartość liczbową.

Niektóre ważne wieże (z wysokości 4, 3i 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

Niektóre nieprawidłowe wieże:

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)    

Powinieneś napisać program lub funkcję, która podaje listę cyfr jako dane wyjściowe lub zwraca wysokość najwyższej możliwej do zbudowania wieży, używając niektórych (być może wszystkich) tych cyfr.

Wejście

• Lista nieujemnych liczb jednocyfrowych z co najmniej jednym elementem.

Wynik

• Pojedyncza dodatnia liczba całkowita, wysokość najwyższej możliwej do zbudowania wieży.
• Twoje rozwiązanie musi rozwiązać każdy przykładowy przypadek testowy w ciągu minuty na moim komputerze (przetestuję tylko zamknięte przypadki. Mam komputer poniżej średniej).

Przykłady

Format jest Input list => Output numberz możliwą wieżą w następnych wierszach, która nie jest częścią wyniku.

[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

To jest golf golfowy, więc wygrywa najkrótszy wpis.

Hojność

Przyznam 100 nagród za reputację (niezwiązanych z już przyznaną) za rozwiązanie poniższego rozszerzonego problemu w czasie wielomianowym (w odniesieniu do długości listy danych wejściowych) lub udowodnienie, że nie jest to możliwe (zakładając, że P! = NP). Szczegóły rozszerzonego problemu:

• liczbami wejściowymi mogą być dowolne nieujemne liczby całkowite, a nie tylko cyfry
• liczby wielocyfrowe zajmują to samo miejsce, co liczby jednocyfrowe
• liczby wielocyfrowe mogą obsługiwać ich wartości liczbowe, np. 24mogą obsługiwać24

Oferta nagród nie ma daty ważności. Dodam i nagrodzę nagrodę, jeśli pojawi się dowód.

Python 2 - 326

Działa łatwo poniżej limitu czasu dla wszystkich podanych przykładów, chociaż poświęciłem trochę wydajności dla rozmiaru, co prawdopodobnie byłoby zauważalne przy znacznie większych nakładach. Teraz, gdy o tym myślę, ponieważ dozwolone są tylko liczby jednocyfrowe, największa możliwa wieża może nie być bardzo duża i zastanawiam się, jaka jest maksymalna.

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