Przybliżenie liczby tuzinów pocałunków

26

Biorąc pod uwagę liczbę od 1 do 24, wyślij liczbę całującą zgodnie z najlepszą obecną wiedzą (niektóre liczby będą miały więcej niż jeden akceptowalny wynik). Znajomość geometrii nie jest niezbędna, ponieważ wszystkie wyniki są wymienione poniżej.

Ze strony Wikipedii dotyczącej problemu Całowanie liczb :

liczba całująca jest zdefiniowana jako liczba nie nakładających się sfer jednostkowych, które mogą być ustawione tak, aby każda dotykała innej danej kuli jednostkowej

To znaczy, biorąc pod uwagę jedną kulę jednostkową, ile więcej kul jednostkowych może ją dotknąć bez nakładania się żadnej z nich? Pytanie zostanie zadane w przestrzeni N-wymiarowej, gdzie sfera jest rozumiana jako sfera wymiarowa N-1.

Na przykład:

  • w przestrzeni dwuwymiarowej koło jednostki może dotykać 6 innych okręgów jednostki.
  • w przestrzeni trójwymiarowej sfera jednostkowa może dotykać 12 innych sfer jednostkowych.

Strona Wikipedia zawiera wartości dla przestrzeni od 1 do 24 wymiarów. Jednak niektóre z nich nie są jeszcze dokładnie znane, dlatego podano tylko dolną i górną granicę. Tabela jest tutaj odtworzona, aby pozostała stała, niezależnie od przyszłego zawężenia zakresów z powodu nowych dowodów. Rozwiązania są oceniane na podstawie tej ustalonej tabeli, nawet jeśli strona Wikipedii zostanie w przyszłości zmodyfikowana.

Tabela granic

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

Wkład

Wymiar: Liczba całkowita od 1 do 24 (włącznie).

Tutaj „całkowita” oznacza, że wejście nie będzie mieć część ułamkową - może to być 2albo 3ale nigdy 2.5. Rozwiązanie może na przykład pobierać dane wejściowe jako zmiennoprzecinkowe lub ciąg znaków.

Wydajność

Liczba w odpowiednim zakresie, od dolnej granicy do górnej granicy dla tego wejścia (włącznie).

Wynik musi być deterministyczny (zawsze taki sam dla tego samego wejścia).

Dane wyjściowe muszą być liczbą całkowitą. Na przykład, do wprowadzania 5możliwych wyjść są ważne 40, 41, 42, 43, 44. Uwaga: jest to ograniczenie wartości, a nie typu. Dopuszczalne jest zwracanie liczby zmiennoprzecinkowej, pod warunkiem że ma zerową część ułamkową. Na przykład 41.5nie byłby ważny, ale 41.0byłby ważny.

Punktacja

To jest . Twój wynik to liczba bajtów w kodzie. Dla każdego języka zwycięzcą jest rozwiązanie o najniższym wyniku.

trichopaks
źródło
6
Naprawdę fajny problem z przybliżeniem.
qwr

Odpowiedzi:

11

Julia 0.6 , 52 bajty

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

Wypróbuj online!

W jaki sposób?

Nauczanie maszynowe! (Trochę. Może. Nie bardzo. )

aebK+cc

aebK+cceil

sundar - Przywróć Monikę
źródło
6
Nie uważam wyszukiwania sieci za uczenie maszynowe. To jest brutalna siła.
qwr
5
Ale to jest MLBase!!! J / k, linie wokół ML są rozmyte jak zawsze, ale prawdopodobnie jest to zbyt podstawowe, aby zasłużyć na uczenie maszynowe etykiet. Z drugiej strony zawsze przydatne jest wprowadzenie modnego hasła!
Sundar - Przywróć Monikę
kiedy mówimy Machine Learning, myślimy głównie o wielomianach z n = 2 lub regexps
aaaaa mówi, że przywróć Monikę
2
kiedy mówię uczenie maszynowe, myślę o sieciach neuronowych, drzewach decyzyjnych, HMM, perceptronie ...
qwr
@qwr Jestem bardzo spóźniony, ale regresja jest rzeczywiście uważana za element uczenia maszynowego, oprócz wszystkich tych rzeczy. (I więcej! SVM itp.)
Quintec
7

x86, 62 59 53 50 bajtów

Moje rozwiązanie wykorzystuje bajtową tablicę odnośników i przesuwa się o 2 (bez obliczeń FP). Wymiary od 9 do 23 zapewniają wystarczającą swobodę zmiany biegów. Wejście eaxi wyjście ecx.

-3 przez zamianę, eaxa ecxponieważ cmp $imm, %aljest on krótszy niż cmp $imm, %cl.

-4, nie traktując oddzielnie sprawy N = 24, ale stosując korektę do wszystkich przypadków 1024.

-2 nie wracając wcześniej (głupio)

-3 przy użyciu tabeli jako przesunięcia i movzblzamiast zerowania za pomocąxor

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 (tabela .textzamiast .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
źródło
1
W tabeli jest tylko do odczytu, tak normalnie, że można umieścić go w .rodatanie .datatak. (Lub najwyraźniej w systemie Windows .rdata). .rodataSekcja zostanie połączone w ramach segmentu tekstu.
Peter Cordes,
1
A tak przy okazji, normalni ludzie piszą shl, szczególnie gdy twój numer jest niepodpisany (używałeś movzblgo, nie movsbl). Oczywiście salto tylko inna nazwa tego samego kodu operacyjnego. gcc emituje sal, ale rzadko widuje się go w kodzie odręcznym.
Peter Cordes,
7

JavaScript (ES6), 60 bajtów

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

Wypróbuj online!

W jaki sposób?

a24=196560

Wszystkie pozostałe warunki są obliczane rekurencyjnie przy użyciu:

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

qn

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

prowadząc do następujących wskaźników:

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

Ostateczny wynik jest ostatecznie wyświetlany i zwracany.

Podsumowanie wyników

Przybliżone wyniki podano z dokładnością do 2 miejsc po przecinku.

  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
źródło
1
Pierwszą rzeczą, którą zobaczyłem, były bitowe operatory wewnątrz rekurencyjnej funkcji JavaScript; pierwszą rzeczą, o której pomyślałem, było „Co to jest Arnauld do ...”
MattH
Naprawdę fajny stół. Zrobiłeś to ręcznie?
qwr
1
@qwr Tak, to głównie część edycji Notepad ++. Właśnie użyłem skryptu do wygenerowania wartości w pierwszych 4 kolumnach.
Arnauld
4

Galaretka , 29 26 bajtów

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

Wypróbuj online!

Jak to działa

“~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
źródło
1

JavaScript (Node.js) , 120 99 bajtów

Usunięto 21 bajtów. Duża redukcja dzięki sugestii tsh, aby dodać dziurę na początku tablicy (oszczędzając dwa bajty przechodząc od n-1do ni dążąc do okrągłych liczb w dolnej i górnej granicy, zmniejszając je w ten sposób od notacji stałoprzecinkowej, jak 1154notacja wykładnicza jak 2e3.

Ponownie moim pierwotnym celem było pokazanie, jak lekki byłby „głupi” sposób (np. Nie używanie żadnej prawdziwej matematyki, jak odpowiedź Arnaulda. Imponujące jest to, że wciąż było miejsce, aby ją zmniejszyć bez żadnych przekształceń lub obliczeń.

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]

Wypróbuj online!

Dwa razy więcej niż odpowiedź Arnaulda, 0 stopień złożoności.

JavaScript (Node.js) , 129 128 bajtów

(-1 bajt dzięki sugestii użycia przesunięcia bitów)

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]

Wypróbuj online!

Aby spełnić wymagania bycia ciekawym, ukradłem logikę z odpowiedzi x86 i zbudowałem z niej tablicę. Dzięki temu jest o 9 bajtów dłuższy. Ale nieco bardziej interesujący.

Anthony
źródło
ziewa przynajmniej spróbuj czegoś interesującego
qwr
Pomyślałem, że zademonstrowanie najprostszego podejścia (a tym samym technicznie najdłuższej rozsądnej długości) było całkiem interesujące. Arnauld's jest prawdopodobnie najkrótszym, jaki można uzyskać w JS, ale najdłuższy to tylko dwa razy więcej bajtów.
Anthony
1
Istotą tabeli bajtów jest użycie bajtowania lub po prostu czegoś takiego jak „02060c1828487ef0”, gdzie każdy wpis ma jeden bajt lub 2 znaki szesnastkowe, jeśli wolisz. Przechowywanie liczb bezpośrednio w systemie dziesiętnym zajmuje do 3 znaków. Użyj także przesunięcia bitów ...
qwr
2
Ty powinien przynajmniej Usuń f=, zmian (x)do x, dodać dziurę i zmiany x-1do x. TIO ; a może zaokrąglić w górę 99 bajtów TIO
tsh
5
Witamy w PPCG! :)
Kudłaty
1

Runiczne, 173 bajty

>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

(Zauważ, że prawy dolny róg powinien być liczony jako bajty: są one domyślnie wypełnione spacjami).

Exe TIO potrzebuje aktualizacji, na której opiera się ta odpowiedź (i usuwam kilka innych dziur, zanim poproszę Dennisa o odbudowę). Ale podłączenie wartości (pamiętaj, aby dodać białe znaki w wierszach 2 i 3, jeśli używasz więcej niż jednego znaku dla wartości w pierwszym wierszu). Oto najprostszy sposób na zapisanie potrzebnych wartości:

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

Wypróbuj online!

Funkcjonalnie jest to port odpowiedzi Julii z Sundara (ale Runiczna nie ma komendy wypychania ena stos (lub, właściwie, żadnej wartości dziesiętnej), więc potrzebne było przybliżenie). Przybliżenie dla edanych wejściowych mniejszych niż 8 jest bardziej precyzyjne, ponieważ utrata precyzji spowodowała, że ​​wartości leżą poza dopuszczalnym zakresem wyników (np. 7Dałoby 125). Ceil()zostało osiągnięte przez konwersję na znak, a następnie z powrotem na liczbę (to nie powiodło się dla wyjątkowo dużych wartości, więc przy 40k miałem go podzielić przez 100, wykonaj konwersję do iz powrotem, a następnie pomnóż ponownie przez 100).

Prawdopodobnie jest miejsce na uproszczenie aranżacji (np. Uruchomienie punktu wejścia w pionie, poniżej lub znalezienie sposobu kompresji przybliżeń e), ale cieszę się, że mogę wykonać obliczenia.

/?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 bajtów.

Aktualizacja tłumacza:

Dzięki odczytowi wejścia ustalania push Runic ma teraz kilka funkcji matematycznych i zdolność do parsowania łańcuchów jako podwójnych. To znacznie uprości tę odpowiedź, ale zostawię ją tak, aby pochwalić się wysiłkiem, jaki w nią włożyłem (dodałem funkcje matematyczne z jednym argumentem i analizę ciągów znaków wkrótce po opublikowaniu: miałem już Sin / Cos / Tan moja lista rzeczy do zrobienia, ale nie brałem pod uwagę Exp, Abs, Log itp. i brakowało znaków) TIO powinno zaktualizować się w ciągu 24-48 godzin, w zależności od tego, kiedy Dennis to zobaczy.

212,+16,+1c2*,+1cX,+zmniejszyłby się do -> 1'eAdzięki tej aktualizacji interpretera. Awyskakuje znak i wartość i wykonuje operację matematyczną na tej wartości na podstawie wyskakującego znaku ( ew tym przypadku jest Exp()i Exp(1)zwraca e ).

Draco18s
źródło