Dua lusin perkiraan angka ciuman

26

Diberi angka dari 1 hingga 24, menampilkan angka berciuman sesuai pengetahuan terkini (beberapa angka akan memiliki lebih dari satu hasil yang dapat diterima). Pengetahuan tentang geometri tidak penting karena semua output tercantum di bawah ini.

Dari halaman Wikipedia pada Masalah Nomor Berciuman :

angka ciuman didefinisikan sebagai jumlah bola unit yang tidak tumpang tindih yang dapat diatur sedemikian rupa sehingga masing-masing menyentuh bola satuan yang diberikan lainnya

Yaitu, mengingat satu unit bola, berapa banyak bola unit yang bisa menyentuhnya tanpa ada yang tumpang tindih? Pertanyaan akan ditanyakan dalam ruang dimensi N, di mana bola dipahami sebagai bola dimensi N-1.

Sebagai contoh:

  • dalam ruang 2 dimensi, sebuah lingkaran satuan dapat menyentuh 6 lingkaran satuan lainnya.
  • dalam ruang 3 dimensi, sebuah unit bola dapat menyentuh 12 bola unit lainnya.

Halaman Wikipedia mencantumkan nilai untuk ruang 1 hingga 24 dimensi. Namun, beberapa di antaranya belum diketahui secara akurat, sehingga hanya batas bawah dan atas yang diberikan. Tabel direproduksi di sini sehingga akan tetap diperbaiki, terlepas dari masa depan penyempitan rentang karena bukti baru. Solusi dinilai berdasarkan tabel tetap ini, bahkan jika halaman Wikipedia diubah di masa mendatang.

Daftar batas

Dimension   Lower bound     Upper bound
1           2               2
2           6               6
3           12              12
4           24              24
5           40              44
6           72              78
7           126             134
8           240             240
9           306             364
10          500             554
11          582             870
12          840             1357
13          1154            2069
14          1606            3183
15          2564            4866
16          4320            7355
17          5346            11072
18          7398            16572
19          10668           24812
20          17400           36764
21          27720           54584
22          49896           82340
23          93150           124416
24          196560          196560

Memasukkan

Dimensi: Integer dari 1 hingga 24 (inklusif).

Di sini "integer" menunjukkan bahwa input tidak akan memiliki bagian fraksional - mungkin 2atau 3tetapi tidak pernah 2.5. Solusi mungkin masih mengambil input sebagai float, atau string, misalnya.

Keluaran

Angka dalam rentang yang relevan, dari batas bawah ke batas atas untuk input tersebut (inklusif).

Outputnya harus deterministik (selalu sama untuk input yang sama).

Output harus bilangan bulat. Misalnya, untuk input 5output yang valid yang mungkin adalah 40, 41, 42, 43, 44. Perhatikan ini adalah batasan pada nilai, bukan tipe. Dapat diterima untuk mengembalikan pelampung, asalkan tidak ada bagian pecahan. Misalnya, 41.5tidak valid, tetapi 41.0valid.

Mencetak gol

Ini adalah . Skor Anda adalah jumlah byte dalam kode Anda. Untuk setiap bahasa, pemenangnya adalah solusi dengan skor terendah.

trichoplax
sumber
6
Masalah perkiraan yang sangat keren.
qwr

Jawaban:

11

Julia 0,6 , 52 byte

n->ceil(n<8?3.7exp(.51n)-5.1:n<24?9exp(.41n):196560)

Cobalah online!

Bagaimana?

Pembelajaran mesin! (Agak. Mungkin. Tidak juga. )

aebK+cc

aebK+cceil

sundar - Pasang kembali Monica
sumber
6
Saya tidak akan menganggap pencarian grid sebagai pembelajaran mesin. Itu adalah kekerasan jika ada.
qwr
5
Tapi ada di MLBase!!! J / k, garis-garis di sekitar ML kabur seperti biasa, tapi ini mungkin adalah terlalu dasar untuk layak pembelajaran mesin label. Dan lagi, selalu berguna untuk memasukkan kata kunci!
sundar - Reinstate Monica
ketika kita mengatakan Machine Learning, kita terutama memikirkan polinomial dengan n = 2 atau regexps
aaaaa mengatakan mengembalikan Monica
2
ketika saya mengatakan pembelajaran mesin, saya memikirkan jaring saraf, pohon keputusan, HMM, perceptron ...
qwr
@ qwr saya sangat terlambat, tetapi regresi memang dianggap sebagai bagian dari pembelajaran mesin, selain semua hal itu. (Dan banyak lagi! SVM, dll.)
Quintec
7

x86, 62 59 53 50 byte

Solusi saya menggunakan tabel pencarian byte dan bergeser dengan 2 (tanpa perhitungan FP). Dimensi 9 hingga 23 memberikan peluang yang cukup untuk pemindahan gigi. Input masuk eaxdan keluaran masuk ecx.

-3 dengan menukar eaxdan ecxkarena cmp $imm, %allebih pendek dari cmp $imm, %cl.

-4 dengan tidak memperlakukan N = 24 case secara terpisah tetapi menerapkan penyesuaian untuk semua kasus 1024.

-2 dengan tidak kembali lebih awal (bodoh)

-3 dengan menggunakan tabel sebagai offset dan movzblbukannya nol denganxor

start:
        dec     %eax                # 1-indexed table

        movzbl  table(%eax), %ecx   # return byte directly
        cmp     $8, %al
        jl      exit

        sal     $6, %ecx            # * 64 
        cmp     $19, %al
        jl      exit

        sal     $4, %ecx            # * 16
        sub     $48, %ecx

exit:   
        ret

#.data
table:  .byte   2, 6, 12, 24, 40, 72, 126, 240              # * 1
        .byte   5, 8, 10, 14, 19, 26, 41, 68, 84, 116, 167  # * 64  
        .byte   18, 28, 49, 92, 192                         # * 1024 - 48

Hexdump ( .textbukan tabel .data)

00000502  48 0f b6 88 1c 05 00 00  3c 08 7c 0d c1 e1 06 3c  |H.......<.|....<|
00000512  13 7c 06 c1 e1 04 83 e9  30 c3 02 06 0c 18 28 48  |.|......0.....(H|
00000522  7e f0 05 08 0a 0e 13 1a  29 44 54 74 a7 12 1c 31  |~.......)DTt...1|
00000532  5c c0                                             |\.|
qwr
sumber
1
Tabel ini hanya-baca, jadi biasanya Anda akan memasukkannya .rodata, bukan .data. (Atau pada Windows, tampaknya .rdata). The .rodatabagian akan dikaitkan sebagai bagian dari segmen teks.
Peter Cordes
1
Dan BTW, orang normal menulis shl, terutama ketika nomor Anda tidak ditandatangani (Anda biasa movzblmemuatnya, bukan movsbl). Tentu saja salhanya nama lain untuk opcode yang sama. memancarkan gcc sal, tetapi sangat jarang melihatnya dalam kode tulisan tangan.
Peter Cordes
7

JavaScript (ES6), 60 byte

f=(n,k=2)=>n<24?--n?f(n,k*24/(17+~'_8443223'[n])):~~k:196560

Cobalah online!

Bagaimana?

a24=196560

Semua istilah lain dihitung secara rekursif, menggunakan:

{a1=2an+1=an×24qn

qn

{q1=8q2=12q3=12q4=13q5=14q6=14q7=13qn=16,for n>7

mengarah ke rasio berikut:

3,2,2,2413,127,127,2413,32,32,...,32

Hasil akhirnya akhirnya lantai dan dikembalikan.

Ringkasan hasil

Hasil perkiraan diberikan dengan 2 tempat desimal.

  n |   a(n-1) | multiplier |      a(n) | output |          expected
----+----------+------------+-----------+--------+-------------------
  1 |      n/a |        n/a |         2 |      2 |                2
----+----------+------------+-----------+--------+-------------------
  2 |        2 |          3 |         6 |      6 |                6
  3 |        6 |          2 |        12 |     12 |               12
  4 |       12 |          2 |        24 |     24 |               24
  5 |       24 |      24/13 |     44.31 |     44 |        [40,..,44]
  6 |    44.31 |       12/7 |     75.96 |     75 |        [72,..,78]
  7 |    75.96 |       12/7 |    130.21 |    130 |      [126,..,134]
  8 |   130.21 |      24/13 |    240.39 |    240 |              240
  9 |   240.39 |        3/2 |    360.58 |    360 |      [306,..,364]
 10 |   360.58 |        3/2 |    540.87 |    540 |      [500,..,554]
 11 |   540.87 |        3/2 |    811.31 |    811 |      [582,..,870]
 12 |   811.31 |        3/2 |   1216.97 |   1216 |     [840,..,1357]
 13 |  1216.97 |        3/2 |   1825.45 |   1825 |    [1154,..,2069]
 14 |  1825.45 |        3/2 |   2738.17 |   2738 |    [1606,..,3183]
 15 |  2738.17 |        3/2 |   4107.26 |   4107 |    [2564,..,4866]
 16 |  4107.26 |        3/2 |   6160.89 |   6160 |    [4320,..,7355]
 17 |  6160.89 |        3/2 |   9241.34 |   9241 |   [5346,..,11072]
 18 |  9241.34 |        3/2 |  13862.00 |  13862 |   [7398,..,16572]
 19 | 13862.00 |        3/2 |  20793.01 |  20793 |  [10668,..,24812]
 20 | 20793.01 |        3/2 |  31189.51 |  31189 |  [17400,..,36764]
 21 | 31189.51 |        3/2 |  46784.26 |  46784 |  [27720,..,54584]
 22 | 46784.26 |        3/2 |  70176.40 |  70176 |  [49896,..,82340]
 23 | 70176.40 |        3/2 | 105264.59 | 105264 | [93150,..,124416]
----+----------+------------+-----------+--------+-------------------
 24 |           (hard-coded)            | 196560 |           196560 
Arnauld
sumber
1
Hal pertama yang saya lihat adalah operator bitwise di dalam fungsi JavaScript rekursif; hal pertama yang saya pikirkan adalah "Apa yang harus dilakukan Arnauld ..."
MattH
Meja yang sangat bagus. Apakah Anda membuatnya secara manual?
qwr
1
@ qwr Ya, itu sebagian besar pengeditan Notepad ++. Saya hanya menggunakan skrip untuk menghasilkan nilai dalam 4 kolom pertama.
Arnauld
4

Jelly , 29 26 byte

“~D=ⱮziEc+y’Dḣ+⁵÷7PĊ«“£#;’

Cobalah online!

Bagaimana itu bekerja

“~D=ⱮziEc+y’Dḣ+⁵÷7PĊ«“£#;’  Main link. Argument: n

“~D=ⱮziEc+y’                Set the return value to 485523230101001100011122.
            D               Decimal; convert the return value to base 10.
             ḣ              Head; take the first n elements of the digit list.
              +⁵            Add 10 to each element.
                ÷7          Divide the sums by 7.
                  P         Take the product.
                   Ċ        Ceil; round up to the nearest integer.
                     “£#;’  Yield 196560.
                    «       Take the minimum.
Dennis
sumber
1

JavaScript (Node.js) , 120 99 byte

Turun 21 byte. Big pengurangan berkat saran TSH untuk menambah lubang ke awal dari array (tabungan dua byte pergi dari n-1ke n, dan bertujuan untuk angka bulat dalam lebih rendah untuk dan atas-batas, sehingga menyusut mereka dari notasi fixed-point seperti 1154untuk notasi eksponensial seperti 2e3.

Sekali lagi, tujuan awal saya adalah menunjukkan betapa ringannya cara "bodoh" itu (misalnya, tidak menggunakan matematika nyata, seperti jawaban Arnauld. Sangat mengesankan bahwa masih ada ruang untuk mengecilkannya tanpa transformasi atau perhitungan.

n=>[,2,6,12,24,40,72,126,240,306,500,582,840,2e3,2e3,3e3,5e3,6e3,8e3,2e4,2e4,3e4,5e4,1e6,196560][n]

Cobalah online!

Dua kali panjang jawaban Arnauld, 0 jumlah kerumitan.

JavaScript (Node.js) , 129 128 byte

(-1 byte berkat saran untuk menggunakan bitshifting)

f=(n)=>[2,6,12,24,40,72,126,240].concat([5,8,10,14,19,26,41,68,84,116,167].map(x=>x<<6),[17,28,49,91].map(x=>x<<10),196560)[n-1]

Cobalah online!

Untuk memenuhi tuntutan menjadi menarik, saya mencuri logika dari jawaban x86, dan membangun array dari itu. Membuatnya 9 byte lebih lama. Namun sedikit lebih menarik.

Anthony
sumber
menguap setidaknya mencoba sesuatu yang menarik
qwr
Saya pikir mendemonstrasikan pendekatan yang paling mudah (dan dengan demikian secara teknis paling masuk akal) cukup menarik. Arnauld's adalah yang terpendek yang dapat Anda peroleh di JS, namun terpanjang hanya dua kali byte.
Anthony
1
Inti dari tabel pencarian byte adalah mungkin menggunakan bytestring atau hanya sesuatu seperti "02060c1828487ef0" di mana setiap entri adalah satu byte atau 2 karakter dalam hex jika Anda mau. Menyimpan angka secara langsung dalam desimal membutuhkan hingga 3 karakter. Juga gunakan bitshifting ...
qwr
2
Anda setidaknya harus menghapus f=, perubahan (x)untuk x, menambah lubang dan perubahan x-1untuk x. TIO ; dan mungkin mengumpulkannya TIO 99 byte
tsh
5
Selamat datang di PPCG! :)
Shaggy
1

Runic, 173 byte

>i:8(?D5X1+1C,*212,+16,+1c2*,+1cX,+Sp3X7+a,*5X1+a,-1+kn$;
      R:c2*(?D4X1+1C,*212,+16,+1c2*,+Sp9*1+:4XY(?Dkn$;
             R`196560`r@;              ;$*C1nk,C1L

(Perhatikan bahwa sudut kanan bawah harus dihitung untuk byte: mereka secara implisit diisi dengan spasi.)

Exe TIO membutuhkan pembaruan yang bergantung pada jawaban ini (dan saya sedang memperbaiki beberapa lubang lain sebelum meminta Dennis untuk membangun kembali). Tetapi memasukkan nilai dalam (pastikan untuk menambahkan spasi putih pada baris 2 dan 3 jika menggunakan lebih dari satu karakter untuk nilai pada baris pertama). Inilah cara termudah untuk menulis nilai yang dibutuhkan:

0-9,a-f  ->  1-15
2Xn+     ->  20+n

Cobalah online!

Secara fungsional ini adalah port jawaban Julia sundar (tetapi Runic tidak memiliki perintah untuk mendorong eke stack (atau benar-benar, nilai desimal apa pun), sehingga diperlukan pendekatan). Perkiraan untuk einput kurang dari 8 lebih tepat, karena hilangnya presisi mengakibatkan nilai-nilai berada di luar kisaran output yang diijinkan (misalnya 7akan menghasilkan 125). Ceil()dicapai dengan mengkonversi ke karakter dan kemudian kembali ke angka (ini gagal untuk nilai yang sangat besar, jadi pada 40k saya membaginya dengan 100, lakukan konversi ke dan kembali, lalu kalikan dengan 100 lagi).

Mungkin ada beberapa ruang untuk menyederhanakan pengaturan (misalnya menjalankan titik masuk secara vertikal, di bawah, atau menemukan cara untuk mengompres perkiraan untuk e), tetapi saya senang dengan hanya dapat melakukan perhitungan.

/?D5X1+1C,*212,+16,+1c2*,+1cX,+Sp3X7+a,*5X1+a,-1+kn$;
  R:c2*(?D4X1+1C,*212,+16,+1c2*,+Sp9*1+:4XY(?Dkn$;
\(8:i<   R`196560`r@;              ;$*C1nk,C1L

161 byte.

Pembaruan juru bahasa:

Dengan pembacaan input perbaikan dorong , Runic sekarang memiliki beberapa fungsi matematika dan kemampuan untuk mengurai string sebagai ganda. Itu akan sangat menyederhanakan jawaban ini, tetapi saya akan membiarkannya untuk memamerkan upaya yang saya lakukan ke dalamnya (saya menambahkan satu argumen fungsi Math dan string parsing segera setelah posting: Saya sudah memiliki Sin / Cos / Tan on daftar tugas saya, tetapi belum mempertimbangkan Exp, Abs, Log, dll. dan kehabisan karakter). TIO harus diperbarui dalam 24-48 jam ke depan, tergantung pada saat Dennis melihatnya.

212,+16,+1c2*,+1cX,+akan mengurangi menjadi -> 1'eAdengan pembaruan juru bahasa ini. Amuncul karakter dan nilai dan melakukan operasi Matematika pada nilai berdasarkan karakter muncul ( edalam hal ini adalah Exp()dan Exp(1)mengembalikan e ).

Draco18s
sumber