Nyatakan nomor
Kembali di tahun 60an, Perancis menciptakan acara permainan TV "Des Chiffres et des Lettres" (Digit & Letters). Tujuan bagian Digit adalah untuk sedekat mungkin dengan angka target 3 digit tertentu, menggunakan beberapa angka yang dipilih secara semi-acak. Para kontestan dapat menggunakan operator berikut:
- concatenation (1 dan 2 adalah 12)
- Selain itu (1 + 2 adalah 3)
- pengurangan (5 - 3 = 2)
- pembagian (8/2 = 4); pembagian hanya diperbolehkan jika hasilnya adalah bilangan alami
- perkalian (2 * 3 = 6)
- tanda kurung, untuk menimpa prioritas operasi yang biasa: 2 * (3 + 4) = 14
Setiap angka yang diberikan hanya dapat digunakan sekali atau tidak sama sekali.
Misalnya, nomor target 728 dapat dicocokkan persis dengan angka: 6, 10, 25, 75, 5 dan 50 dengan ekspresi berikut:
75 * 10 - ( ( 6 + 5 ) * ( 50 / 25 ) ) = 750 - ( 11 * 2 ) = 750 - 22 = 728
Dalam tantangan kode ini, Anda diberi tugas untuk menemukan ekspresi sedekat mungkin dengan nomor target tertentu. Karena kita hidup di abad ke-21, kita akan memperkenalkan angka target yang lebih besar dan angka yang lebih banyak untuk diajak bekerja sama daripada di tahun 60an.
Aturan
- Operator yang dibolehkan: concatenation, +, -, /, *, (dan)
- Operator gabungan tidak memiliki simbol. Baru saja menyatukan angkanya.
- Tidak ada "penggabungan terbalik". 69 adalah 69 dan tidak dapat dibagi menjadi 6 dan 9.
- Angka target adalah bilangan bulat positif dan memiliki maksimal 18 digit.
- Setidaknya ada dua angka untuk bekerja dan maksimal 99 angka. Angka-angka ini juga bilangan bulat positif dengan maksimum 18 digit.
- Mungkin (sebenarnya sangat mungkin) bahwa nomor target tidak dapat dinyatakan dalam hal jumlah dan operator. Tujuannya adalah untuk sedekat mungkin.
- Program harus selesai dalam waktu yang wajar (beberapa menit pada PC desktop modern).
- Celah standar berlaku.
- Program Anda mungkin tidak dioptimalkan untuk set tes di bagian "penilaian" dari teka-teki ini. Saya berhak mengubah set tes jika saya mencurigai ada orang yang melanggar aturan ini.
- Ini bukan codegolf.
Memasukkan
Input terdiri dari array angka yang dapat diformat dengan cara apa pun yang mudah. Angka pertama adalah nomor target. Sisa angka adalah angka yang harus Anda kerjakan untuk membentuk nomor target.
Keluaran
Persyaratan untuk output adalah:
- Ini harus berupa string yang terdiri dari:
- subset dari nomor input (kecuali nomor target)
- sejumlah operator
- Saya lebih suka output menjadi satu baris tanpa spasi, tetapi jika Anda harus, Anda dapat menambahkan spasi dan baris baru yang Anda inginkan. Mereka akan diabaikan dalam program pengendalian.
- Outputnya harus berupa ekspresi matematika yang valid.
Contohnya
Agar mudah dibaca, semua contoh ini memiliki solusi yang tepat dan setiap nomor input digunakan tepat satu kali.
Input: 1515483, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
Output:111*111*(111+11+1)
Input: 153135, 1, 2, 3, 4, 5, 6, 7, 8, 9
Output:123*(456+789)
Input: 8888888888, 9, 9, 9, 99, 99, 99, 999, 999, 999, 9999, 9999, 9999, 99999, 99999, 99999, 1
Output:9*99*999*9999-9999999-999999-99999-99999-99999-9999-999-9-1
Input: 207901, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0
Output:1+2*(3+4)*(5+6)*(7+8)*90
Input: 34943, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0
Output: 1+2*(3+4*(5+6*(7+8*90)))
Tetapi juga output yang valid adalah:34957-6-8
Mencetak gol
Skor penalti suatu program adalah jumlah kesalahan relatif dari ekspresi untuk testset di bawah ini.
Misalnya, jika nilai target adalah 125 dan ekspresi Anda memberi 120, skor penalti Anda abs (1 - 120/125) = 0,04.
Program dengan yang terendah skor (termurah jumlah relatif error) menang. Jika dua program selesai sama, pengajuan pertama menang.
Akhirnya, testset (8 kasus):
14142, 10, 11, 12, 13, 14, 15
48077691, 6, 9, 66, 69, 666, 669, 696, 699, 966, 969, 996, 999
333723173, 3, 3, 3, 33, 333, 3333, 33333, 333333, 3333333, 33333333, 333333333
589637567, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5
8067171096, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199
78649377055, 0, 2, 6, 12, 20, 30, 42, 56, 72, 90, 110, 132, 156, 182, 210, 240, 272, 306, 342, 380, 420, 462, 506, 552, 600, 650, 702, 756, 812, 870, 930, 992
792787123866, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169
2423473942768, 1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000, 20000, 50000, 100000, 2000000, 5000000, 10000000, 20000000, 50000000
Teka-teki serupa sebelumnya
Setelah membuat puzzle ini dan mempostingnya di kotak pasir, saya melihat sesuatu yang serupa (tapi tidak sama!) Di dua teka-teki sebelumnya: di sini (tidak ada solusi) dan di sini . Teka-teki ini agak berbeda, karena memperkenalkan operator gabungan, saya tidak mencari dan mencocokkan secara tepat dan saya suka melihat strategi untuk mendekati solusi tanpa kekerasan. Saya pikir ini menantang.
Jawaban:
C ++ 17, skor 0,0086
Program ini memiliki skor penalti non-deterministik karena balapan thread, jadi saya mendeklarasikan berdasarkan rata-rata tiga run, masing-masing menangani test suite dalam waktu kurang dari satu menit:
Inilah programnya; Penjelasan diberikan dalam komentar. Anda dapat menetapkan
CONCAT_NONE
aturan Countdown tradisional yang tidak mengizinkan penggabungan, atauCONCAT_DIGITS
untuk memungkinkan penyatuan nilai input, tetapi tidak untuk hasil antara. Secara default, tanpa salah satu dari keduanya, aturan yang paling liberal digunakan.Saya mengkompilasi ini menggunakan GCC 6.2, menggunakan
g++ -std=c++17 -fopenmp -march=native -O3
(bersama dengan beberapa opsi debugging dan peringatan).sumber
Python 2.7. Nilai: 1,67039106
Jadi, saya memutuskan untuk melemparkannya sendiri. Tidak ada yang terlalu mewah. Program ini mengurutkan angka dalam urutan terbalik (besar ke kecil), dan mencoba semua operator secara berurutan pada angka-angka tersebut. Sangat cepat, tetapi kinerja yang layak digantikan.
Inilah programnya:
Output untuk semua kasus uji adalah:
sumber