Hasilkan angka dengan menggunakan daftar angka dan operator aritmatika tertentu

11

Anda diberi daftar angka L = [17, 5, 9, 17, 59, 14], satu kantong operator O = {+:7, -:3, *:5, /:1}dan satu nomor N = 569.

Tugas

Keluarkan persamaan yang menggunakan semua angka di Ldi sisi kiri dan hanya angka Ndi sisi kanan. Jika ini tidak memungkinkan, hasilkan False. Contoh solusi:

59*(17-5)-9*17+14 = 569

Keterbatasan dan Klarifikasi

  • Anda tidak boleh menggabungkan angka ( [13,37]tidak boleh digunakan sebagai 1337)
  • Hanya bilangan asli dan nol yang akan muncul L.
  • Urutan dalam Ltidak masalah.
  • Anda harus menggunakan semua nomor dalam L.
  • Hanya operator +, -, *, /akan muncul dalam O.
  • Odapat memiliki lebih banyak operator daripada yang Anda butuhkan, tetapi setidaknya |L|-1operator
  • Anda dapat menggunakan setiap operator berapa kali hingga nilai masuk O.
  • Keempat operasi di Oadalah operasi matematika standar; khususnya, /adalah pembagian normal dengan fraksi yang tepat.

Poin

  • Semakin sedikit poin, semakin baik
  • Setiap karakter kode Anda memberi Anda satu poin

Anda harus memberikan versi tidak golf yang mudah dibaca.

Latar Belakang

Sebuah pertanyaan serupa diminta pada Stack Overflow. Saya pikir ini mungkin tantangan kode-golf yang menarik.

Kompleksitas Komputasi

Seperti yang dikatakan Peter Taylor dalam komentar, Anda dapat memecahkan jumlah subset dengan ini:

  1. Anda memiliki turunan dari jumlah subset (karenanya, himpunan S bilangan bulat dan angka x)
  2. L: = S + [0, ..., 0] (| S | kali nol), N: = x, O: = {+: | S | -1, *: | S | - 1, /: 0, -: 0}
  3. Sekarang selesaikan contoh masalah saya ini
  4. Solusi untuk jumlah subset adalah angka S yang tidak dikalikan dengan nol.

Jika Anda menemukan Algoritma yang lebih baik daripada O (2 ^ n), Anda membuktikan bahwa P = NP. Karena P vs NP adalah Masalah Hadiah Milenium dan karenanya bernilai 1.000.000 Dolar AS, sangat tidak mungkin ada orang yang menemukan solusi untuk ini. Jadi saya menghapus bagian peringkat ini.

Uji kasus

Berikut ini bukan satu-satunya jawaban yang valid, ada solusi lain, dan diizinkan:

  • ( [17,5,9,17,59,14], {+:7, -:3, *:5, /:1}, 569)
    => 59 * (17-5)- 9 * 17 + 14 = 569
  • ( [2,2], {'+':3, '-':3, '*':3, '/':3}, 1)
    => 2/2 = 1
  • ( [2,3,5,7,10,0,0,0,0,0,0,0], {'+':20, '-':20, '*':20, '/':20}, 16)
    => 5+10-2*3+7+0+0+0+0+0+0+0 = 16
  • ( [2,3,5,7,10,0,0,0,0,0,0,0], {'+':20, '-':20, '*':20, '/':20}, 15)
    => 5+10+0*(2+3+7)+0+0+0+0+0+0 = 15
Martin Thoma
sumber
Benarkah m = |L|? Jika ya, bagaimana Anda bisa mengharapkan runtime tidak tergantung pada ukuran daftar itu? Sebagai contoh [2,2],[+,+,...,+,/],1,. Faktanya, karena n adalah O (m), Anda mungkin menulis semuanya dalam bentuk m.
stan
3
Jenis aritmatika apa yang digunakan - pecahan tepat, bilangan bulat ( /div), hanya floating-point dan harapan-untuk-tidak-pembulatan-kesalahan, ...?
Berhenti menghidupkan counterclockwis
4
Mengapa aturan penilaian yang rumit untuk kompleksitas komputasi? Ada pengurangan yang mudah dari subset-sum, jadi apa pun yang lebih baik daripada O (2 ^ n) bernilai satu juta USD.
Peter Taylor
1
Terkait: stackoverflow.com/questions/3947937/…
Dr. belisarius
1
Kasus uji ke-3 tidak Salah ...5+10+2*3+7*0+0...
Shmiddty

Jawaban:

3

Python 2.7 / 478 karakter

L=[17,5,9,17,59,14]
O={'+':7,'-':3,'*':5,'/':1}
N=569
P=eval("{'+l+y,'-l-y,'*l*y,'/l/y}".replace('l',"':lambda x,y:x"))
def S(R,T):
 if len(T)>1:
  c,d=y=T.pop();a,b=x=T.pop()
  for o in O:
   if O[o]>0 and(o!='/'or y[0]):
    T+=[(P[o](a, c),'('+b+o+d+')')];O[o]-=1
    if S(R,T):return 1
    O[o]+=1;T.pop()
  T+=[x,y]
 elif not R:
  v,r=T[0]
  if v==N:print r
  return v==N
 for x in R[:]:
  R.remove(x);T+=[x]
  if S(R,T):return 1
  T.pop();R+=[x]
S([(x,`x`)for x in L],[])

Gagasan utamanya adalah menggunakan bentuk ekspresi postfix untuk mencari. Misalnya, 2*(3+4)dalam bentuk postfix akan 234+*. Jadi masalahnya menjadi menemukan permutasi sebagian yang L+ Odievalasikan ke N.

Versi berikut adalah versi yang tidak disunat. Tumpukannya stkterlihat seperti [(5, '5'), (2, '5-3', (10, ((4+2)+(2*(4/2))))].

L = [17, 5, 9, 17, 59, 14]
O = {'+':7, '-':3, '*':5, '/':1} 
N = 569

P = {'+':lambda x,y:x+y,
     '-':lambda x,y:x-y,
     '*':lambda x,y:x*y,
     '/':lambda x,y:x/y}

def postfix_search(rest, stk):
    if len(stk) >= 2:
        y = (v2, r2) = stk.pop()
        x = (v1, r1) = stk.pop()
        for opr in O:
            if O[opr] > 0 and not (opr == '/' and v2 == 0):
                stk += [(P[opr](v1, v2), '('+r1+opr+r2+')')]
                O[opr] -= 1
                if postfix_search(rest, stk): return 1
                O[opr] += 1
                stk.pop()
        stk += [x, y]
    elif not rest:
        v, r = stk[0]
        if v == N: print(r)
        return v == N
    for x in list(rest):
        rest.remove(x)
        stk += [x]
        if postfix_search(rest, stk):
            return True
        stk.pop()
        rest += [x]
postfix_search(list(zip(L, map(str, L))), [])
sinar
sumber
1
Wow, itu lebih pendek dari yang saya harapkan. Saya telah mencoret sebuah algoritma yang menyertakan postfix konversi <=> infix, tetapi coretan saya tidak jauh lebih pendek dari implementasi Anda. Mengesankan. Dan terima kasih untuk konstruksinya P[opr](v1, v2). Saya tidak pernah berpikir untuk menggabungkan lambda dan kamus seperti ini, meskipun sekarang tampak jelas.
Martin Thoma
Saya sudah mencoba menguji solusi Anda dengan testcase 4 saya. Setelah 2 jam, saya menghentikan eksekusi.
Martin Thoma
@ jauh saya akan mencoba menambahkan beberapa heuristik untuk membuatnya lebih cepat. Namun setelah itu panjang kode bisa berlipat ganda.
Ray
Menggunakan Fraksi seperti yang saya lakukan di sini memperbaiki masalah dalam jawaban Anda. Coba saja untuk contoh yang diberikan pada tautan yang saya berikan. Kode Anda saat ini tidak menemukan jawaban, tetapi ketika Anda menggunakan fraksi, jawabannya.
Martin Thoma