Pelat Lisensi Sempurna
Mulai beberapa tahun yang lalu, saya membuat permainan kecil saat mengemudi: memeriksa apakah plat nomor terdekat "sempurna". Ini relatif jarang, tetapi menyenangkan ketika Anda menemukannya.
Untuk memeriksa apakah plat nomornya sempurna:
- Ringkas karakter, dengan A = 1, B = 2, ... Z = 26.
- Ambil setiap potongan angka berturut-turut, dan jumlahkan; kalikan masing-masing jumlah ini bersama-sama.
Jika nilai di bagian 1 dan bagian 2 sama, selamat! Anda telah menemukan plat nomor sempurna!
Contohnya
License plate: AB3C4F
Digits -> 3 * 4
= 12
Chars -> A + B + C + F
= 1 + 2 + 3 + 6
= 12
12 == 12 -> perfect!
License plate: G34Z7T
Digits -> (3 + 4) * 7
= 49
Chars -> G + Z + T
= 7 + 26 + 20
= 53
49 != 53 -> not perfect!
License plate: 10G61
Digits -> (1 + 0) * (6 + 1)
= 7
Chars -> G
= 7
7 == 7 -> perfect!
Tantangan
Saya menggunakan plat nomor dengan panjang 5 dan 6 sebagai contoh, tetapi prosedur ini berlaku untuk semua panjang plat. Tantangan Anda adalah, untuk panjang tertentu N, kembalikan jumlah plat nomor yang sempurna dengan panjang itu. Untuk tujuan tantangan, plat nomor yang valid adalah kombinasi angka 0-9 dan karakter AZ. Piring harus berisi karakter dan angka agar dianggap berpotensi sempurna. Untuk tujuan pengecekan, berikut adalah nilai yang saya dapatkan (meskipun saya tidak bisa 100% tentang kebenarannya, hahaha)
N < 2: 0
N = 2: 18
N = 3: 355
N = 4: 8012
Catatan
Jika entah bagaimana itu membuat masalah lebih sederhana dalam bahasa Anda, Anda dapat menampilkan proporsi plat nomor sempurna untuk N yang diberikan, setidaknya 2 digit signifikan.
N < 2: 0
N = 2: 0.0138888...
N = 3: 0.0076088...
N = 4: 0.0047701...
ATAU, Anda dapat menampilkan nilai setara mod 256
N < 2: 0
N = 2: 18
N = 3: 99
N = 4: 76
Kemenangan terpendek!
N
.Jawaban:
Python 3.6, 150 byte
hasil:
Versi tidak dikoleksi dengan penjelasan:
Masalahnya bermuara pada pencarian pohon di mana setiap tingkat pohon sesuai dengan posisi dalam nomor plat dan setiap node memiliki 36 anak (10 digit dan 26 huruf). Fungsi melakukan pencarian pohon secara rekursif, mengumpulkan nilai untuk digit dan huruf saat berjalan.
Termasuk Golf, mengonversi loop for menjadi jumlah generator:
Kemudian menggabungkan generator. Encode huruf, A ke Z, sebagai -1 hingga -26 dan digit sebagai 0 hingga 9. Jadi jumlahnya menjadi:
dimana args adalah:
Sisa golf adalah mengubah fungsi menjadi lambda, memperpendek nama variabel, dan menyederhanakan ekspresi.
sumber
n*n*log(n)
atau yang serupa?Dyalog APL,
5756 byte(mengasumsikan
⎕io←0
)a
matriks semua plat nomor yang valid (kecuali00...0
) dikodekan dengan: 0-9 untuk digit, 10-35 untuk hurufb
bitmask untuk tempat digit terjadic
bitmask untuk digit terakhir di setiap grup digit berurutansumber
Python 2,
359295 byteAgak panjang; ini adalah solusi sepele. Saya yakin ini benar, meskipun tidak cocok dengan kasus uji dalam tantangan. Solusi yang saya dapatkan cocok dengan jawaban Dada.
-64 byte berkat saran dari @numbermaniac
sumber
for
; antaramap(ord,x)
danif
; dan di baris terakhir, antara.join(x)
danfor
. Saya pikir Anda juga dapat menyimpan lebih banyak jika Anda mendefinisikan kembali fungsi ke lambdas.Python 2 ,
291287276273 byteCobalah online!
Hasil:
sumber
Perl 5 , 117 byte
116 byte kode +
-p
bendera.Cobalah online!
Rasanya cukup optimal, tapi saya kehabisan ide sekarang.
Kode itu sendiri sangat tidak efisien karena menghitung setiap permutasi
a..z,0..9
panjangn
(dibutuhkan sekitar 1 detik untukn=3
, ~ 15 detik untukn=4
dan ~ 7 menit untukn=5
).Algoritma ini cukup lurus ke depan: untuk setiap kemungkinan ukuran pelat
n
(dihasilkan denganglob"{@F}"x$_
-glob
operatornya cukup ajaib),$r*=eval s/./+$&/gr for/\d+/g;
menghitung produk dari setiap bilangan digit, dan$r+=64-ord for/\pl/g
mengurangi bobot huruf-hurufnya. Kemudian, kami menambah penghitung$\
jika$r
is0
(!$r
) dan jika pelat berisi angka dan huruf (/\pl/*/\d/
).$\
dicetak secara implisit di akhir berkat-p
bendera.Perhatikan bahwa nomor saya mendapatkan yang
n=2 -> 18
,n=3 -> 355
,n=4 -> 8012
,n=5 -> 218153
. Saya cukup yakin ini adalah yang benar, tetapi saya mungkin salah, dalam hal ini beri tahu saya dan saya akan menghapus jawaban ini.sumber
APL (Dyalog) , 71 byte
Tubuh program penuh. Prompt untuk N. N≥4 membutuhkan banyak memori dan perhitungan.
Cobalah online!
sumber
Scala, 265 byte
Penjelasan:
Catatan:
-64
dan-48
digunakan untuk mengubahChar
(masing-masing surat dan digit) ke nyaInt
nilai ('A' - 64 = 1
,'B' - 64 = 2
, ...,'9' - 48 = 9
)l.split("[A-Z]").filter(""<)
digunakan untuk menghilangkan""
nilai jikal
dimulai dengan huruf (contoh"A1".split("[A-Z]") => Array("", 1)
:). Mungkin ada solusi yang lebih baik dan lebih pendekKasus uji:
Hasil:
Fungsi ini cukup lambat
n > 4
karena semua kombinasi harus dibuat.sumber
Java,
382365 byteGolf
Terperinci
sumber
n
input.int h(String s){int m=0;for(int c:s.toCharArray())m+=c-48;return m;}int g(String t){int d=1,c=0;for(String s:t.split("[^0-9]"))d*=h(s);for(String s:t.split("[^A-Z]"))c+=s.charAt(0)-65;return d==c?1:0;}int f(String t,int n){int m=0;if(t.length()==n)return g(t);for(int d=48;d<58;)m+=f(t+d++,n);for(int c=65;c<91;)m+=f(t+c++,n);return m;}int s(int n){return f("",n);}
( 365 bytes ) Anda dapat membandingkan versi Anda saat ini dengan yang ini untuk melihat perubahan yang saya lakukan (terlalu banyak untuk dicocokkan dengan sisa komentar ini). :)GAP , 416 byte
Tidak akan menang pada ukuran kode, dan jauh dari waktu yang konstan, tetapi menggunakan matematika untuk mempercepat banyak!
Untuk memeras ruang kosong yang tidak perlu dan mendapatkan satu baris dengan 416 byte, pipa melalui ini:
Laptop lama "dirancang untuk Windows XP" saya dapat menghitung
f(10)
dalam waktu kurang dari satu menit dan melangkah lebih jauh dalam waktu kurang dari satu jam:Bagaimana itu bekerja
Misalkan kita pertama-tama hanya ingin mengetahui jumlah plat nomor yang cocok dengan pola
LDDLLDL
, di manaL
menunjukkan suatu huruf danD
menunjukkan suatu angka. Asumsikan kita memiliki daftarl
angka sehinggal[i]
memberikan jumlah cara huruf dapat memberikan nilaii
, dan daftar serupad
untuk nilai yang kita dapatkan dari angka. Maka jumlah plat nomor sempurna dengan nilai umumi
adalah adill[i]*d[i]
, dan kami mendapatkan nomor plat nomor sempurna dengan pola kami dengan menjumlahkan ini semuai
. Mari kita tunjukkan operasi mendapatkan jumlah ini padal@d
.Sekarang bahkan jika cara terbaik untuk mendapatkan daftar ini adalah dengan mencoba semua kombinasi dan menghitung, kita dapat melakukan ini secara independen untuk huruf dan digit, melihat
26^4+10^3
case daripada26^4*10^3
case ketika kita menjalankan semua pelat yang sesuai dengan pola. Tetapi kita dapat melakukan jauh lebih baik:l
hanya daftar koefisien di(x+x^2+...+x^26)^k
manak
jumlah huruf, di sini4
.Demikian pula, kita mendapatkan jumlah cara untuk mendapatkan jumlah digit dalam rangkaian
k
digit sebagai koefisien(1+x+...+x^9)^k
. Jika ada lebih dari satu putaran digit, kita perlu menggabungkan daftar terkait dengan operasid1#d2
yang pada posisii
memiliki nilai jumlah dari semuad1[i1]*d2[i2]
tempati1*i2=i
. Ini adalah konvolusi Dirichlet, yang hanya merupakan produk jika kita menafsirkan daftar sebagai koefisien dari seri Dirchlet. Tapi kami sudah menggunakannya sebagai polinomial (seri daya terbatas), dan tidak ada cara yang baik untuk menafsirkan operasi untuk mereka. Saya pikir ketidakcocokan ini adalah bagian dari apa yang membuatnya sulit untuk menemukan formula sederhana. Mari kita gunakan pada polinomial dan gunakan notasi yang sama#
. Sangat mudah untuk menghitung ketika satu operan adalah monomial: yang kita milikip(x) # x^k = p(x^k)
. Bersamaan dengan fakta bahwa itu bilinear, ini memberikan cara yang bagus (tapi tidak sangat efisien) untuk menghitungnya.Perhatikan bahwa
k
huruf memberikan nilai paling banyak26k
, sedangkank
angka tunggal dapat memberikan nilai9^k
. Jadi kita akan sering mendapatkan kekuatan tinggi yang tidak dibutuhkan dalamd
polinomial. Untuk menghilangkannya, kita dapat menghitung modulox^(maxlettervalue+1)
. Ini memberi kecepatan besar dan, meskipun saya tidak segera menyadarinya, bahkan membantu bermain golf, karena kita sekarang tahu bahwa derajatnyad
tidak lebih besar daripada tingkatl
, yang menyederhanakan batas atas di finalSum
. Kami mendapatkan kecepatan yang lebih baik dengan melakukanmod
perhitungan pada argumen pertamaValue
(lihat komentar), dan melakukan keseluruhan#
perhitungan pada level yang lebih rendah memberikan kecepatan yang luar biasa. Tapi kami masih berusaha menjadi jawaban yang sah untuk masalah golf.Jadi kita sudah mendapat kami
l
dand
dan dapat menggunakannya untuk menghitung jumlah plat sempurna dengan polaLDDLLDL
. Itu adalah angka yang sama dengan polanyaLDLLDDL
. Secara umum, kita dapat mengubah urutan deretan digit dengan panjang berbeda sesuai keinginan,NrArrangements
memberikan jumlah kemungkinan. Dan sementara harus ada satu huruf di antara deretan angka, surat-surat lainnya tidak tetap. TheBinomial
menghitung kemungkinan ini.Sekarang tinggal menjalankan semua cara yang mungkin untuk memiliki panjang digit angka.
r
dijalankan melalui semua jumlah run,c
melalui semua jumlah total digit, danp
melalui semua partisic
denganr
puncak.Jumlah total partisi yang kita lihat adalah dua kurang dari jumlah partisi
n+1
, dan fungsi partisi bertambahexp(sqrt(n))
. Jadi sementara masih ada cara mudah untuk meningkatkan waktu berjalan dengan menggunakan kembali hasil (menjalankan melalui partisi dalam urutan yang berbeda), untuk peningkatan mendasar kita perlu menghindari melihat setiap partisi secara terpisah.Menghitungnya dengan cepat
Catat itu
(p+q)@r = p@r + q@r
. Dengan sendirinya, ini hanya membantu menghindari beberapa perkalian. Tetapi bersamaan dengan(p+q)#r = p#r + q#r
itu berarti bahwa kita dapat menggabungkan dengan polinomial penambahan sederhana yang sesuai dengan partisi yang berbeda. Kita tidak bisa menambahkan semuanya, karena kita masih perlu tahu dengan manal
kita harus@
-kombinasi, faktor mana yang harus kita gunakan, dan#
ekstensi- mana yang masih mungkin.Mari kita gabungkan semua polinomial yang sesuai dengan partisi dengan jumlah dan panjang yang sama, dan sudah memperhitungkan berbagai cara untuk mendistribusikan panjang lintasan digit. Berbeda dari yang saya berspekulasi dalam komentar, saya tidak perlu peduli dengan nilai yang digunakan terkecil atau seberapa sering digunakan, jika saya memastikan bahwa saya tidak akan memperpanjang dengan nilai itu.
Ini kode C ++ saya:
Ini menggunakan perpustakaan MP GNU. Pada debian, instal
libgmp-dev
. Kompilasi dengang++ -std=c++11 -O3 -o pl pl.cpp -lgmp -lgmpxx
. Program mengambil argumennya dari stdin. Untuk penentuan waktu, gunakanecho 100 | time ./pl
.Pada akhirnya
a[sum][length][i]
berikan jumlah carasum
digit yanglength
berjalan dapat memberikan angkai
. Selama perhitungan, pada awalm
loop, ini memberikan jumlah cara yang bisa dilakukan dengan angka lebih besar darim
. Semuanya dimulai dengana[0][0][1]=1
. Perhatikan bahwa ini adalah superset dari angka yang kita perlukan untuk menghitung fungsi untuk nilai yang lebih kecil. Jadi pada saat yang hampir bersamaan, kita dapat menghitung semua nilai hinggan
.Tidak ada rekursi, jadi kami memiliki jumlah tetap dari loop bersarang. (Level sarang terdalam adalah 6.) Setiap loop melewati sejumlah nilai yang linear dalam
n
kasus terburuk. Jadi kita hanya perlu waktu polinomial. Jika kita melihat lebih dekat pada nestedi
danj
loopextend
, kita menemukan batas atas untukj
formN/i
. Itu seharusnya hanya memberikan faktor logaritmik untukj
loop. Loop terdalam dif
(dengansumn
dll) serupa. Juga perlu diingat bahwa kami menghitung dengan angka yang tumbuh cepat.Perhatikan juga bahwa kami menyimpan
O(n^3)
angka-angka ini.Secara eksperimental, saya mendapatkan hasil ini pada perangkat keras yang wajar (i5-4590S):
f(50)
membutuhkan satu detik dan 23 MB,f(100)
membutuhkan 21 detik dan 166 MB,f(200)
perlu 10 menit dan 1,5 GB, danf(300)
perlu satu jam dan 5,6 GB. Ini menunjukkan kompleksitas waktu yang lebih baik daripadaO(n^5)
.sumber
n=5
, tidak ada kasus dengan menjalankan dua digit dan dua digit tunggal, karena dengan begitu kita tidak punya cukup surat untuk memisahkan angka. Inilah yang dilakukan tigafor
loop luar : jalankan melalui semua partisi angka yang berguna<n
. (Dan saya baru sadar saya juga mengizinkann
angka. Dengan sedikit keberuntungan optimasi lain dihitung sebagai 0).<n/2
, semua partisi berguna. Dan perhitungan yang tersisa masih membutuhkan waktu yang tidak konstan. Untuk melihat apa yang terjadi, Anda bisa menambahkanPrint(p,"\n");
di awal badanfor p...
loop. - Saya mendapat ide untuk menggunakan satu loop lebih sedikit, tetapi itu hanya akan membantu ukuran kode.mod
(yang sudah banyak membantu)Value
, mengubahnya menjadiValue(d mod x^(1+QuoInt(s(l)-1,i-1)),x^(i-1))
. Itu saja memungkinkan untuk menghitungf(15)
dalam 80 detik.Pyth, 55 byte
sumber