26
\$\begingroup\$

Given a number from 1 to 24, output the kissing number to the best of current knowledge (some numbers will have more than one acceptable output). Knowledge of geometry is not essential as the outputs are all listed below.

From the Wikipedia page on the Kissing Number Problem:

a kissing number is defined as the number of non-overlapping unit spheres that can be arranged such that they each touch another given unit sphere

That is, given one unit sphere, how many more unit spheres can touch it without any of them overlapping? The question will be asked in N dimensional space, where a sphere is understood to be an N-1 dimensional sphere.

For example:

  • in 2 dimensional space, a unit circle can touch 6 other unit circles.
  • in 3 dimensional space, a unit sphere can touch 12 other unit spheres.

The Wikipedia page lists values for 1 to 24 dimensional space. However, some of these are not yet known accurately, so only a lower and upper bound are given. The table is reproduced here so that it will remain fixed, regardless of any future narrowing of the ranges due to new proofs. Solutions are judged against this fixed table, even if the Wikipedia page is modified in future.

Table of bounds

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

Input

The dimension: An integer from 1 to 24 (inclusive).

Here "integer" indicates that the input will have no fractional part - it may be 2 or 3 but never 2.5. A solution may still take input as a float, or a string, for example.

Output

A number in the relevant range, from the lower limit to the upper limit for that input (inclusive).

The output must be deterministic (always the same for the same input).

The output must be integer. For example, for input 5 the possible valid outputs are 40, 41, 42, 43, 44. Note this is a restriction on the value, not the type. It is acceptable to return a float, provided it has zero fractional part. For example, 41.5 would not be valid, but 41.0 would be valid.

Scoring

This is . Your score is the number of bytes in your code. For each language, the winner is the solution with the lowest score.

\$\endgroup\$
  • 6
    \$\begingroup\$ Really cool approximation problem. \$\endgroup\$ – qwr Jul 13 '18 at 1:33
11
\$\begingroup\$

Julia 0.6, 52 bytes

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

Try it online!

How?

Machine learning! (Kinda. Maybe. Not really.)

First, from plotting the lower and upper limit data against N, and some manual trial and error, it seemed like an exponential function could fit well for N >= 8. After some attempts at manually finding this function, I resorted to using a parameter tuning function to tune \$ a * e^{b K} + c \$ (where K = 8 to 24) to find a, b, and c such that the expression gave values that lie within the correct range for each K (with successively smaller range of possible values and correspondingly higher precisions for a, b, c in different runs of the function). There were a few such set of values, though none of them could fit the N=24 case exactly, so I went with one that had 0 c and hardcoded the value for N=24.

For lower N, from 1 to 7, I was hoping to find some simpler expression or polynomial, but couldn't find any that fit. So back to fitting \$ a * e^{b K} + c \$ , this time for K = 1 to 7 (though I didn't really think an exponential would be a right fit in this case, based on visual plot trends). Thankfully, there were parameters a, b, c that could give correct values throughout the range here (at least to within a ceil call).

\$\endgroup\$
  • 6
    \$\begingroup\$ I wouldn't consider a gridsearch to be machine learning. It is brute force if anything. \$\endgroup\$ – qwr Jul 13 '18 at 1:29
  • 5
    \$\begingroup\$ But it's in MLBase!!! J/k, the lines around ML are blurry as always, but this probably is too basic to deserve the label machine learning. Then again, it's always useful to get a buzzword in! \$\endgroup\$ – sundar - Reinstate Monica Jul 13 '18 at 1:41
  • \$\begingroup\$ when we say Machine Learning, we mainly think of polynomials with n=2 or regexps \$\endgroup\$ – Oct18 is day of silence on SE Jul 13 '18 at 21:37
  • 2
    \$\begingroup\$ when I say machine learning, I think of neural nets, decision trees, HMMs, perceptron... \$\endgroup\$ – qwr Jul 13 '18 at 22:20
  • \$\begingroup\$ @qwr I'm very late, but regression is indeed considered a part of machine learning, in addition to all of those things. (And more! SVMs, etc.) \$\endgroup\$ – Quintec Sep 30 '18 at 1:48
7
\$\begingroup\$

x86, 62 59 53 50 bytes

My solution uses a byte lookup table and shifting by 2 (no FP computations). Dimensions 9 through 23 provide enough leeway for the shifting. Input in eax and output in ecx.

-3 by swapping eax and ecx since cmp $imm, %al is shorter than cmp $imm, %cl.

-4 by not treating the N=24 case separately but applying the adjustment to all times 1024 cases.

-2 by not returning early (stupid)

-3 by using table as offset and movzbl instead of zeroing with 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 (table in .text instead of .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                                             |\.|
\$\endgroup\$
  • 1
    \$\begingroup\$ The table is read-only, so normally you'd put it in .rodata, not .data anyway. (Or on Windows, apparently .rdata). The .rodata section gets linked as part of text segment. \$\endgroup\$ – Peter Cordes Jul 16 '18 at 19:25
  • 1
    \$\begingroup\$ And BTW, normal people write shl, especially when your number is unsigned (you used movzbl to load it, not movsbl). Of course sal is just another name for the same opcode. gcc emits sal, but it's pretty rare to see it in hand-written code. \$\endgroup\$ – Peter Cordes Jul 16 '18 at 19:31
7
\$\begingroup\$

JavaScript (ES6), 60 bytes

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

Try it online!

How?

The last term \$a_{24}=196560\$ is hard-coded.

All other terms are computed recursively, using:

$$\begin{cases}a_1=2\\a_{n+1}=a_n\times\dfrac{24}{q_n}\end{cases}$$

where \$q_n\$ is defined as:

$$\begin{cases}q_1=8\\q_2=12\\q_3=12\\q_4=13\\q_5=14\\q_6=14\\q_7=13\\q_n=16,&\text{for }n>7\end{cases}$$

leading to the following ratios:

$$3,2,2,\frac{24}{13},\frac{12}{7},\frac{12}{7},\frac{24}{13},\frac{3}{2},\frac{3}{2},\ldots,\frac{3}{2}$$

The final result is eventually floored and returned.

Results summary

Approximated results are given with 2 decimal places.

  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 
\$\endgroup\$
  • 1
    \$\begingroup\$ The first thing I saw was bitwise operators inside a recursive JavaScript function; the first thing I thought was "What is Arnauld up to..." \$\endgroup\$ – MattH Jul 13 '18 at 14:37
  • \$\begingroup\$ Really nice table. Did you make it manually? \$\endgroup\$ – qwr Jul 13 '18 at 22:05
  • 1
    \$\begingroup\$ @qwr Yes, that's mostly some Notepad++ editing. I just used a script to generate the values in the first 4 columns. \$\endgroup\$ – Arnauld Jul 13 '18 at 22:38
4
\$\begingroup\$

Jelly, 29 26 bytes

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

Try it online!

How it works

“~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.
\$\endgroup\$
1
\$\begingroup\$

JavaScript (Node.js), 120 99 bytes

Dropped 21 bytes. Big reduction thanks to tsh's suggestion to add a hole to the start of the array (saving two bytes going from n-1 to n, and aiming for round numbers within the lower- and upper-bounds, thus shrinking them from fixed-point notation like 1154 to exponential notation like 2e3.

Again, my original goal was to show how light the "dumb" way would be (eg not using any real math, like Arnauld's answer. It's impressive that there was still room to shrink it without any transformations or calculations.

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]

Try it online!

Twice the length of Arnauld's answer, 0 amount of the complexity.

JavaScript (Node.js), 129 128 bytes

(-1 byte thanks to suggestion to use 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]

Try it online!

To meet the demands of being interesting, I stole the logic from the x86 answer, and built the array from that. Making it 9 bytes longer. But slightly more interesting.

\$\endgroup\$
  • \$\begingroup\$ yawns at least try something interesting \$\endgroup\$ – qwr Jul 13 '18 at 4:05
  • \$\begingroup\$ I thought demonstrating the most straightforward approach (and thus technically the longest reasonable length) was pretty interesting. Arnauld's is quite possibly the shortest you can get in JS, yet the longest is only twice the bytes. \$\endgroup\$ – Anthony Jul 13 '18 at 4:07
  • 1
    \$\begingroup\$ The point of the byte lookup table is to maybe use a bytestring or just something like "02060c1828487ef0" where each entry is one byte or 2 characters in hex if you prefer. Storing the numbers directly in decimal takes up to 3 characters. Also use bitshifting... \$\endgroup\$ – qwr Jul 13 '18 at 6:05
  • 2
    \$\begingroup\$ You should at least remove f=, change (x) to x, add a hole and change x-1 to x. TIO; and maybe round them up TIO 99 bytes \$\endgroup\$ – tsh Jul 13 '18 at 9:33
  • 5
    \$\begingroup\$ Welcome to PPCG! :) \$\endgroup\$ – Shaggy Jul 13 '18 at 11:22
1
\$\begingroup\$

Runic, 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

(Note that the lower right corner should be counted for bytes: they are implicitly filled with spaces.)

TIO's exe needs an update that this answer relies on (and I'm patching up some other holes before asking Dennis to rebuild). But plugging a value in (be sure to add whitespace on lines 2 and 3 if using more than one character for the value on the first line). Here's the easiest way to write the values needed:

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

Try it online!

Functionally this is a port of sundar's Julia answer (but Runic doesn't have a command for pushing e to the stack (or really, any decimal value), so an approximation was needed). The approximation for e for inputs less than 8 is more precise, as the loss of precision resulted in values lying outside the allowable range of outputs (e.g. 7 would produce 125). Ceil() was accomplished by converting to a character and then back to a number (this failed for exceptionally large values, so at 40k I had it divide by 100, do the conversion to and back, then multiply by 100 again).

There's probably some room to simplify the arrangement (e.g. running the entry point vertically, below, or finding a way to compress the approximations for e), but I'm happy with just being able to do the calculation.

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

Interpreter Update:

With the push fixing input reading, Runic now has several math functions and the ability to parse strings as doubles. That will vastly simplify this answer, but I will leave it as is to show off the effort I put into it (I added the single-argument Math functions and string parsing shortly after posting: I'd already had Sin/Cos/Tan on my to-do list, but hadn't considered Exp, Abs, Log, etc. and was running out of characters). TIO should update in the next 24-48 hours, depending on when Dennis sees it.

212,+16,+1c2*,+1cX,+ would reduce to -> 1'eA with this interpreter update. A pops a character and a value and performs a Math operation on that value based on the character popped (e in this case is Exp() and Exp(1) returns e).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.