Zwei Dutzend Kusszahlen

26

Geben Sie bei einer Zahl von 1 bis 24 die Kusszahl nach bestem Wissen aus (einige Zahlen haben mehr als eine akzeptable Ausgabe). Kenntnisse der Geometrie sind nicht erforderlich, da die Ergebnisse alle nachstehend aufgeführt sind.

Auf der Wikipedia-Seite zum Problem mit der Kissing Number :

Eine Kusszahl ist definiert als die Anzahl nicht überlappender Einheitskugeln, die so angeordnet werden können, dass sie jeweils eine andere Einheitskugel berühren

Das heißt, wie viele Einheitskugeln können eine Einheitskugel berühren, ohne dass sich eine davon überlappt? Die Frage wird im N-dimensionalen Raum gestellt, wobei unter einer Kugel eine N-1-dimensionale Kugel verstanden wird.

Beispielsweise:

  • Im zweidimensionalen Raum kann ein Einheitskreis 6 andere Einheitskreise berühren.
  • Im dreidimensionalen Raum kann eine Einheitskugel 12 andere Einheitskugeln berühren.

Die Wikipedia-Seite listet Werte für den 1- bis 24-dimensionalen Raum auf. Einige von diesen sind jedoch noch nicht genau bekannt, so dass nur eine untere und obere Schranke angegeben sind. Die Tabelle wird hier reproduziert, so dass sie unabhängig von einer zukünftigen Einschränkung der Bereiche aufgrund neuer Beweise unverändert bleibt. Lösungen werden an dieser festen Tabelle gemessen, auch wenn die Wikipedia-Seite in Zukunft geändert wird.

Grenztabelle

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

Eingang

Die Dimension: Eine ganze Zahl von 1 bis 24 (einschließlich).

Hier gibt "Ganzzahl" an, dass die Eingabe keinen Bruchteil hat - es kann sein 2oder 3aber nie 2.5. Eine Lösung kann Eingaben beispielsweise immer noch als Float oder als Zeichenfolge annehmen.

Ausgabe

Eine Zahl im relevanten Bereich von der Untergrenze bis zur Obergrenze für diese Eingabe (einschließlich).

Die Ausgabe muss deterministisch sein (immer dieselbe für dieselbe Eingabe).

Die Ausgabe muss eine Ganzzahl sein. Zum Beispiel für die Eingabe 5der möglichen gültigen Ausgänge sind 40, 41, 42, 43, 44. Beachten Sie, dass dies eine Einschränkung des Werts und nicht des Typs ist. Es ist akzeptabel, einen Schwimmer zurückzugeben, vorausgesetzt, er hat einen Bruchteil von Null. Zum Beispiel 41.5wäre nicht gültig, 41.0wäre aber gültig.

Wertung

Das ist . Ihre Punktzahl ist die Anzahl der Bytes in Ihrem Code. Für jede Sprache ist der Gewinner die Lösung mit der niedrigsten Punktzahl.

Trichoplax
quelle
6
Wirklich cooles Approximationsproblem.
Qwr

Antworten:

11

Julia 0,6 , 52 Bytes

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

Probieren Sie es online!

Wie?

Maschinelles lernen! (Ein bisschen. Vielleicht. Nicht wirklich. )

einebK+cc

einebK+cceil

Sundar - Setzen Sie Monica wieder ein
quelle
6
Ich würde eine Gittersuche nicht als maschinelles Lernen bezeichnen. Es ist rohe Gewalt, wenn überhaupt.
Qwr
5
Aber es ist in MLBase!!! J / k, die Linien um ML sind verschwommen wie immer, aber wahrscheinlich ist zu einfach das Etikett für maschinelles Lernen zu verdienen. Andererseits ist es immer nützlich, ein Schlagwort zu verwenden!
Sundar - Reinstate Monica
wenn wir Machine Learning sagen, wir hauptsächlich mit n von Polynomen denken = 2 oder regexps
aaaaa sagt wieder einzusetzen Monica
2
Wenn ich maschinelles Lernen sage, denke ich an neuronale Netze, Entscheidungsbäume, HMMs, Perceptron ...
qwr
@qwr Ich bin sehr spät dran, aber Regression wird in der Tat als Teil des maschinellen Lernens angesehen, zusätzlich zu all diesen Dingen. (Und mehr! SVMs usw.)
Quintec
7

x86, 62 59 53 50 Bytes

Meine Lösung verwendet eine Byte-Nachschlagetabelle und eine Verschiebung um 2 (keine FP-Berechnungen). Die Abmessungen 9 bis 23 bieten genügend Spielraum für das Schalten. Eingabe in eaxund Ausgabe in ecx.

-3 durch tauschen eaxund ecxda cmp $imm, %alist kürzer als cmp $imm, %cl.

-4 durch nicht die N = 24 separat Fall der Behandlung , aber die Anpassung an alle Zeiten 1024 Fälle anwenden.

-2 von nicht früh zurückkehren (dumm)

-3 durch Verwendung der Tabelle als Versatz und movzblanstelle von Nullstellen mitxor

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 (Tabelle in .textstatt .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
quelle
1
Die Tabelle ist schreibgeschützt. Normalerweise würden Sie sie also .rodatanicht .dataeinfügen. (Oder anscheinend unter Windows .rdata). Der .rodataAbschnitt wird als Teil des Textsegments verknüpft.
Peter Cordes
1
Und übrigens schreiben normale Leute shl, besonders wenn Ihre Nummer nicht signiert ist (Sie haben sie früher movzblgeladen, nicht movsbl). Natürlich salist es nur ein anderer Name für den gleichen Opcode. gcc gibt es aus sal, aber es ist ziemlich selten, es in handgeschriebenem Code zu sehen.
Peter Cordes
7

JavaScript (ES6), 60 Byte

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

Probieren Sie es online!

Wie?

ein24=196560

Alle anderen Ausdrücke werden rekursiv berechnet unter Verwendung von:

{ein1=2einn+1=einn×24qn

qn

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

was zu folgenden Verhältnissen führt:

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

Das Endergebnis ist schließlich unbearbeitet und wird zurückgegeben.

Zusammenfassung der Ergebnisse

Ungefähre Ergebnisse werden mit 2 Dezimalstellen angegeben.

  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
quelle
1
Das erste, was ich sah, waren bitweise Operatoren in einer rekursiven JavaScript-Funktion. Das erste, was ich dachte, war "Was hat Arnauld vor ..."
MattH
Wirklich schöner Tisch. Hast du es manuell gemacht?
Qwr
1
@qwr Ja, das sind hauptsächlich Notepad ++ - Bearbeitungen. Ich habe gerade ein Skript verwendet, um die Werte in den ersten 4 Spalten zu generieren.
Arnauld
4

Jelly , 29 26 Bytes

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

Probieren Sie es online!

Wie es funktioniert

“~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
quelle
1

JavaScript (Node.js) , 120 99 Byte

21 Bytes gelöscht. Große Reduzierung dank des Vorschlags von tsh, ein Loch am Anfang des Arrays einzufügen (zwei Bytes von n-1bis sparen nund auf runde Zahlen innerhalb der Unter- und Obergrenze abzielen, wodurch sie von der Festkommanotation wie 1154zur Exponentialnotation verkleinert werden mögen2e3 .

Mein ursprüngliches Ziel war es, zu zeigen, wie leicht die "dumme" Art sein würde (z. B. ohne echte Mathematik, wie Arnauld's Antwort). Es ist beeindruckend, dass es noch Raum gab, sie ohne Transformationen oder Berechnungen zu verkleinern.

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]

Probieren Sie es online!

Zweimal so lang wie Arnauld's Antwort, 0 Grad Komplexität.

JavaScript (Node.js) , 129 128 Byte

(-1 Byte dank Vorschlag zur Bitverschiebung)

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]

Probieren Sie es online!

Um den Anforderungen des Interesses gerecht zu werden, habe ich die Logik aus der x86-Antwort gestohlen und daraus das Array erstellt. Es 9 Bytes länger machen. Aber etwas interessanter.

Anthony
quelle
gähnt zumindest versuchen Sie etwas Interessantes
qwr
Ich fand es ziemlich interessant, den einfachsten Ansatz (und damit die technisch längste vernünftige Länge) zu demonstrieren. Arnauld's ist wahrscheinlich die kürzeste, die Sie in JS bekommen können, aber die längste ist nur doppelt so groß wie die Bytes.
Anthony
1
Der Zweck der Byte-Nachschlagetabelle besteht darin, möglicherweise einen Bytestring oder einfach so etwas wie "02060c1828487ef0" zu verwenden, wobei jeder Eintrag ein Byte oder 2 Zeichen in hexadezimaler Schreibweise enthält, wenn Sie dies vorziehen. Das direkte Speichern der Zahlen in Dezimalzahlen dauert bis zu 3 Zeichen. Verwenden Sie auch Bitshifting ...
QWR
2
Sie sollten mindestens entfernen f=, ändern (x)zu x, fügen Sie ein Loch und Änderung x-1zu x. TIO ; und vielleicht runden sie TIO 99 Bytes
tsh
5
Willkommen bei PPCG! :)
Shaggy
1

Runen, 173 Bytes

>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

(Beachten Sie, dass die untere rechte Ecke für Bytes gezählt werden sollte: Sie sind implizit mit Leerzeichen gefüllt.)

TIOs Exe benötigt ein Update , auf das sich diese Antwort stützt (und ich repariere ein paar andere Lücken, bevor ich Dennis auffordere, es wieder aufzubauen). Fügen Sie jedoch einen Wert ein (stellen Sie sicher, dass Sie in den Zeilen 2 und 3 Leerzeichen einfügen, wenn Sie mehr als ein Zeichen für den Wert in der ersten Zeile verwenden). So schreiben Sie die benötigten Werte am einfachsten:

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

Probieren Sie es online!

Funktionell ist dies eine Portierung der Julia-Antwort von Sundar (aber Runic hat keinen Befehl zum Verschieben eauf den Stack (oder wirklich einen Dezimalwert), sodass eine Annäherung erforderlich war). Die Näherung für eEingaben unter 8 ist genauer, da der Genauigkeitsverlust zu Werten führt, die außerhalb des zulässigen Bereichs der Ausgaben liegen (z. B. 7125 ergeben würden).Ceil()wurde durch Konvertieren in ein Zeichen und dann zurück in eine Zahl erreicht (dies schlug bei außergewöhnlich großen Werten fehl, so dass ich es bei 40k durch 100 teilen ließ, die Konvertierung in und zurück durchführte und dann wieder mit 100 multiplizierte).

Wahrscheinlich gibt es einige Zimmer , die Anordnung zu vereinfachen (zB den Einstiegspunkt vertikal verlaufende , unten oder die Suche nach einem Weg , um die Annäherungen zu komprimieren e), aber ich bin glücklich , mit nur in der Lage sein zu tun , um die Berechnung.

/?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 Bytes.

Dolmetscher Update:

Mit der Push-Fixing-Eingabe verfügt Runic nun über mehrere mathematische Funktionen und die Möglichkeit, Zeichenfolgen doppelt zu analysieren. Das wird diese Antwort erheblich vereinfachen, aber ich werde es so belassen, wie es ist, um den Aufwand zu demonstrieren, den ich in sie gesteckt habe meine To-Do-Liste, hatte aber Exp, Abs, Log usw. nicht berücksichtigt und hatte keine Charaktere mehr). TIO sollte in den nächsten 24-48 Stunden aktualisiert werden, je nachdem, wann Dennis es sieht.

212,+16,+1c2*,+1cX,+würde sich 1'eAmit diesem Interpreter-Update auf -> reduzieren . AFügt ein Zeichen und einen Wert hinzu und führt eine mathematische Operation für diesen Wert basierend auf dem aufgetauchten Zeichen durch ( ein diesem Fall ist Exp()undExp(1) gibt e zurück ).

Draco18s
quelle