Sunting: Bounty puzzle di akhir pertanyaan.

Diberi satu set angka 1 digit, Anda harus menentukan seberapa tinggi menara yang bisa mereka bangun.

Digit-digitnya hidup di bidang horizontal dengan permukaan tanah di mana mereka bisa berdiri. Tidak ada digit yang ingin dikacaukan dengan angka multi-digit, sehingga mereka selalu memiliki ruang kosong di kedua sisi mereka.

4 2  1 9  6  8

Angka bisa di atas yang lain:

2
6

atau dapat didukung oleh dua lainnya secara diagonal di bawahnya:

 9
5 8

Yang paling bawah harus menopang berat yang disokong orang atas (jika ada), ditambah yang berat di atasnya selalu 1 . Jika ada dua pendukung, mereka membagi total berat badan bagian atas secara merata (50% -50%).

Berat setiap digit adalah 1 terlepas dari nilainya.

Jika satu digit mendukung dua yang lain, angka tersebut harus dapat mendukung jumlah dari berat yang sesuai. Digit dapat mendukung paling banyak nilai numeriknya.

Beberapa menara yang valid (dengan ketinggian 4, 3dan 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

Beberapa menara tidak valid:

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)    

Anda harus menulis sebuah program atau fungsi yang memberikan daftar digit sebagai input output atau mengembalikan ketinggian menara tertinggi yang dapat dibangun dengan menggunakan beberapa (mungkin semua) dari digit tersebut.

Memasukkan

• Daftar nomor satu digit non-negatif dengan setidaknya satu elemen.

Keluaran

• Integer positif tunggal, ketinggian menara tertinggi yang dapat dibangun.
• Solusi Anda harus menyelesaikan contoh uji kasus di bawah satu menit di komputer saya (saya hanya akan menguji kasus tutup. Saya memiliki PC di bawah rata-rata.).

Contohnya

Format adalah Input list => Output numberdengan menara yang mungkin pada baris berikutnya yang bukan merupakan bagian dari output.

[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

Ini adalah kode-golf, sehingga entri terpendek menang.

Karunia

Saya akan menghadiahkan 100 reputasi hadiah (tidak terkait dengan yang sudah diberikan) untuk menyelesaikan masalah yang diperpanjang di bawah ini dalam waktu polinomial (terkait dengan panjangnya daftar masukan) atau membuktikan bahwa itu tidak mungkin (dengan asumsi P! = NP). Detail masalah yang diperluas:

• angka input dapat berupa bilangan bulat non-negatif, bukan hanya digit
• nomor multi-digit berlangsung sama dengan nomor satu digit
• angka multi-digit dapat mendukung nilai numeriknya mis. 24dapat mendukung24

Penawaran karunia tidak memiliki tanggal kedaluwarsa. Saya akan menambahkan dan menghargai hadiah jika bukti muncul.

Python 2 - 326

Berjalan dengan mudah di bawah batas waktu untuk semua contoh yang diberikan, meskipun saya mengorbankan beberapa efisiensi untuk ukuran, yang mungkin akan terlihat memberikan input yang jauh lebih besar. Sekarang saya berpikir tentang itu, karena hanya angka satu angka yang diizinkan menara terbesar mungkin tidak terlalu besar, dan saya bertanya-tanya apa yang maksimum.

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