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 L
di sisi kiri dan hanya angka N
di 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 sebagai1337
) - Hanya bilangan asli dan nol yang akan muncul
L
. - Urutan dalam
L
tidak masalah. - Anda harus menggunakan semua nomor dalam
L
. - Hanya operator
+
,-
,*
,/
akan muncul dalamO
. O
dapat memiliki lebih banyak operator daripada yang Anda butuhkan, tetapi setidaknya|L|-1
operator- Anda dapat menggunakan setiap operator berapa kali hingga nilai masuk
O
. - Keempat operasi di
O
adalah 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:
- Anda memiliki turunan dari jumlah subset (karenanya, himpunan S bilangan bulat dan angka x)
- L: = S + [0, ..., 0] (| S | kali nol), N: = x, O: = {+: | S | -1, *: | S | - 1, /: 0, -: 0}
- Sekarang selesaikan contoh masalah saya ini
- 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
sumber
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./
≡div
), hanya floating-point dan harapan-untuk-tidak-pembulatan-kesalahan, ...?5+10+2*3+7*0+0...
Jawaban:
Python 2.7 / 478 karakter
Gagasan utamanya adalah menggunakan bentuk ekspresi postfix untuk mencari. Misalnya,
2*(3+4)
dalam bentuk postfix akan234+*
. Jadi masalahnya menjadi menemukan permutasi sebagian yangL
+O
dievalasikan keN
.Versi berikut adalah versi yang tidak disunat. Tumpukannya
stk
terlihat seperti[(5, '5'), (2, '5-3', (10, ((4+2)+(2*(4/2))))]
.sumber
P[opr](v1, v2)
. Saya tidak pernah berpikir untuk menggabungkan lambda dan kamus seperti ini, meskipun sekarang tampak jelas.