Tantangan ini merupakan penghargaan bagi pengguna PPCG, Dennis, karena memenangkan bagian perampok dari The Programming Language Quiz .
Melihat halaman profil PPCG Dennis, kita dapat melihat beberapa hal yang cukup mengesankan:
Dia saat ini memiliki lebih dari enam puluh delapan ribu reputasi, menjadikannya nomor dua di seluruh rep , melampaui tempat ketiga dengan hampir tiga puluh ribu. Dia baru-baru ini memenangkan pemilihan kami untuk moderator baru dan mendapatkan berlian baru yang mengilap di sebelah namanya. Tapi saya pribadi berpikir bagian paling menarik tentang Dennis adalah nomor ID pengguna PPCG-nya: 12012.
Pada pandangan pertama 12012
hampir terlihat seperti palindrom , angka yang membaca sama ketika dibalik, tetapi sedikit batal. Itu bisa menjadi palindrome 21012
jika kita menukar posisi yang pertama 1
dan 2
, dan itu bisa menjadi palindrom 12021
jika kita menukar yang terakhir 1
dan yang lain 2
. Juga, mengikuti konvensi bahwa angka nol terdepan dalam angka tidak ditulis, bertukar angka pertama 1
dan 0
hasilnya 02112
atau lebih tepatnya 2112
yang merupakan palindrom lain.
Mari kita mendefinisikan bilangan Dennis sebagai bilangan bulat positif yang bukan palindromik itu sendiri tetapi dapat dibuat menjadi palindrom dengan menukar posisi setidaknya satu pasangan dari dua digit. The rangka dari sejumlah Dennis adalah jumlah pasangan yang berbeda dari angka yang dapat ditukarkan untuk membuat (tidak selalu berbeda) palindrom.
Jadi urutan 12012
adalah 3 sejak 3 pasang yang berbeda dari digit ( 12012
, , ) dapat ditukarkan sekitar untuk menghasilkan palindrom. kebetulan menjadi urutan terkecil 3 nomor Dennis.12012
12012
12012
10
adalah nomor Dennis terkecil dan memiliki urutan 1 karena beralih di sekitar 1
dan 0
memberi 01
alias 1
yang merupakan palindrome.
Nol terkemuka imajiner nomor tidak dihitung sebagai digit yang dapat diganti. Misalnya, mengubah 8908
ke 08908
dan menukar dua digit pertama untuk mendapatkan palindrom yang 80908
tidak valid. 8908
bukan nomor Dennis.
Angka-angka non-Dennis dapat dikatakan memiliki pesanan 0.
Tantangan
Tulis program atau fungsi yang mengambil dalam bilangan bulat positif N dan mencetak atau mengembalikan angka Dennis terkecil ke-N beserta urutannya dalam beberapa format yang masuk akal seperti 12012 3
atau (12012, 3)
.
Sebagai contoh, 12012
adalah angka Dennis ke-774 jadi jika 774
input untuk program Anda, hasilnya harus seperti 12012 3
. (Anehnya, 774 adalah nomor Dennis lain.)
Kode terpendek dalam byte menang.
Berikut adalah 20 nomor Dennis pertama dan pesanan mereka untuk referensi:
N Dennis Order
1 10 1
2 20 1
3 30 1
4 40 1
5 50 1
6 60 1
7 70 1
8 80 1
9 90 1
10 100 1
11 110 2
12 112 1
13 113 1
14 114 1
15 115 1
16 116 1
17 117 1
18 118 1
19 119 1
20 122 1
sumber
Jawaban:
Pyth, 44 byte
Cobalah online: Demonstrasi atau Test Suite
Bug kecil bodoh (?) Di Pyth merusak solusi 41 byte.
Penjelasan:
sumber
.f
. Inilah permintaan tarik yang saya buat karena pertanyaan ini: github.com/isaacg1/pyth/pull/151CJam, 45 byte
Cobalah online!
Bagaimana itu bekerja
sumber
Haskell, 174 byte
p
memeriksa apakah suatu daftar adalah palindrome.x!y
JikaTrue
daftarx
dany
(yang harus memiliki panjang yang sama) berbeda persis di dua tempat. Secara khusus, jikax
permutasiy
,x!y
menentukan apakah itu merupakan "swap".o n
menemukan urutan Dennisn
. Ini menyaring untuk swap di antara permutasix = show n
, dan kemudian menghitung berapa banyak dari swap tersebut adalah palindrom. Pemahaman daftar yang melakukan penghitungan ini memiliki penjaga ekstranot (p x)
, yang berarti akan kembali0
jikan
merupakan palindrom untuk memulai.The
snd (span (<'1') v)
bit hanyadropWhile
tapi satu byte lebih pendek; itu berubah"01221"
menjadi"1221"
.f
indeks dari daftar di(i, o i)
manao i > 0
(yaitui
adalah nomor Dennis.) Biasanya ada kesalahan off-by-one di sini, karena(!!)
dihitung dari 0 tetapi masalahnya dihitung dari 1. Saya berhasil memperbaiki ini dengan memulai pencarian dari-10
(yang ternyata dianggap sebagai nomor Dennis oleh program saya!) sehingga mendorong semua angka ke tempat yang tepat.f 774
adalah(12012,3)
.sumber
Python 2, 176
Saya tidak dapat membayangkan bahwa kode swapping saya sangat optimal, tetapi ini adalah yang terbaik yang bisa saya dapatkan. Saya juga tidak suka seberapa sering saya mengkonversi antara string dan integer ...
Untuk setiap angka, ini membuat daftar apakah semua swap dua digit adalah palindrom. Ini mengurangi penghitung ketika setidaknya salah satu dari nilai-nilai ini benar, dan nomor aslinya bukan palindrom. Karena
0+True
dalam python mengevaluasi1
jumlah dari daftar akhir berfungsi untuk urutan nomor Dennis.sumber
Rust, 390 byte
Java baru? : /
Tidak dikumpulkan dan berkomentar:
sumber
Jelly , 33 byte (tidak bersaing)
Cobalah online!
Bagaimana itu bekerja
sumber
APL, 87
Tubuh loop mengembalikan vektor 4 angka: 1) argumen kirinya
⍺
membaca dari input, 2) menghitung angka Dennis sejauh ini, 3) nilai saat iniX
- penghitung loop, dan 4) pesanannyaK
dihitung sebagai jumlah palindrom dalam permutasi 1-swap. Ini berakhir ketika dua elemen pertama menjadi sama dan dua elemen terakhir kemudian dikembalikan sebagai hasilnya.sumber
JavaScript (ES6), 229
Seperti biasa, JavaScript bersinar karena ketidakmampuannya untuk kombinatorik (atau, mungkin ketidakmampuan saya ...). Di sini saya mendapatkan semua posisi swap kemungkinan menemukan semua angka biner dari panjang yang diberikan dan hanya 2 yang ditetapkan.
Tes menjalankan cuplikan di bawah ini di Firefox (karena MSIE jauh dari patuh EcmaScript 6 dan Chrome masih kehilangan parameter default)
sumber
awk, 199
Struktur
Pemakaian
Tempel ini ke konsol Anda dan ganti nomor setelahnya
echo
, jika Anda mauSemakin lambat pada angka yang lebih tinggi;)
Versi yang dapat digunakan kembali yang tidak dikumpulkan
sumber
Ruby, 156
Menggunakan fitur Ruby tempat panggilan
"19".next!
kembali"20"
untuk menghindari keharusan mengubah jenis bolak-balik; kami hanya menggunakan regex untuk mengabaikan memimpin0s
. Iterasikan semua pasang posisi string untuk memeriksa sakelar palindrom. Saya awalnya menulis ini fungsi rekursif tapi itu merusak tumpukan.Output untuk 774 adalah
["12012", 3]
(menghapus tanda kutip akan dikenakan biaya 4 byte lebih tetapi saya pikir spec memungkinkan mereka).sumber