pengantar
Hampir semua orang terbiasa dengan Traveling Salesman Problem (TSP). Tugasnya adalah untuk, diberikan daftar N
kota, menemukan siklus Hamiltonian minimum yaitu jalur terpendek yang mengunjungi masing-masing kota dan datang kembali ke awal. Bukan itu tantangannya. Tantangan ini adalah untuk mengimplementasikan solusi Chuck Norris ke TSP:
Chuck Norris menyelesaikan masalah Travelling Salesman
O(1)
tepat waktu: memecah salesman menjadi beberapa bagian; tendang setiap bagian ke kota yang berbeda.
Tantangan
Untuk menyelesaikan TSP dengan cara ini, kita membutuhkan Salesman yang cukup tahan lama yang tidak akan menghindar dari kesembronoan seperti pemotongan; sejumlah kota untuk dikunjungi; satu set produk untuk dijual; metode konkrit untuk pemotongan; dan perhitungan untuk penilaian.
Spesifikasi
- Kota
N
adalah jumlah kutipan yang akan dikunjungi oleh Salesman kami
- Penjual
- Program atau fungsi utama
- Ditulis dalam bahasa
X
- Dengan panjang mod
N
sama dengan0
- Produk
- Pemotongan
- Mengiris Salesman menjadi
N
potongan terus menerus dengan panjang yang sama - Setiap karya harus merupakan fungsi atau program yang valid dalam bahasa
X
- Mengiris Salesman menjadi
- Keluaran
- Ketika dieksekusi, Salesman harus mengeluarkan
Chuck Norris
dan potongan masing-masing harus mengeluarkan produk yang berbeda - Hanya ruang ekstra trailing putih yang dapat diterima
- Ketika dieksekusi, Salesman harus mengeluarkan
- Mencetak gol
- Panjang,,
L
dari Salesman dalam bytes dibagi dengan jumlah kotaN
,, kuadrat. Score = L/(N*N)
- Kemenangan skor terkecil
- Harap sertakan 3 angka penting saat memposting skor desimal Anda
- Panjang,,
Contohnya
- Salesman ini mengunjungi 3 kota
N=3
dan dan memiliki panjang 9 jadiL=9
. Jadi skor untuk jawaban ini adalahS = 9 / (3 * 3) = 9/9 = 1
.- Perhatikan bahwa Salesman dan masing-masing potongan yang diiris (yang ada 3), semuanya harus merupakan program atau fungsi yang valid dalam bahasa yang sama.
Program -> Output
------- ------
aaaBBBccc -> Chuck Norris
aaa -> Helium
BBB -> Iridium
ccc -> Tennessine
N=4
danL=20
sebagainyaS=20/16=1.25
Program -> Output
------- ------
aaaaaBBBBBcccccDDDDD -> Chuck Norris
aaaaa -> Hydrogen
BBBBB -> Cadmium
ccccc -> Mercury
DDDDD -> Iron
sumber
ElementData
diperbolehkan? (Saya ragu itu akan menghemat banyak, tetapi saya tidak tahu.)Jawaban:
CJam, L = 1482, N = 114, skor 0,114
Cobalah online!
Setiap program panjangnya 13 byte. Di sini mereka dibagi menjadi beberapa baris:
Elemen yang hilang adalah Darmstadtium, Praseodymium, Protactinium dan Rutherfordium yang panjangnya 12 atau 13 karakter yang berarti saya tidak dapat mencetaknya masing-masing dalam 13 karakter.
Idenya adalah bahwa beberapa program pertama, yang mencetak elemen dengan nama pendek menggunakan karakter asing mereka untuk membangun string
Chuck Norri
dalam variabelL
, yang tidak mempengaruhi output ketika digunakan sendiri. Program terakhir kemudian memeriksa apakah ada yang sudah ada di stack, dan menggunakannya untuk memilih antaraL
(pluss
) danXenon
.Beberapa byte tambahan disimpan dengan menggunakan karakter yang baru saja kita tambahkan
L
sebagai bagian dari nama elemen, khusus untukC
arbon,N
ickel, Copper
dan Silver
.sumber
Python, L = 2596, N = 118, Skor = 0.186
Panjang setiap irisan adalah 22 sehingga membuatnya cukup panjang.
Berikut adalah Salesman setelah mengiris dan dicing:
Memperbarui
sumber
lambda:"Actinium";print""
output Actinium? Apakah ini khusus untuk Python 3?Actinium
. Tidakprint ""
melakukan apa pun yang berguna setelah Salesman telah dipotong-potong.