26

Dado un número del 1 al 24, envíe el número de beso al mejor conocimiento actual (algunos números tendrán más de una salida aceptable). El conocimiento de la geometría no es esencial ya que las salidas se enumeran a continuación.

De la página de Wikipedia sobre el problema del número de besos :

un número de beso se define como el número de esferas de unidades no superpuestas que se pueden organizar de manera que cada una toque otra esfera de unidad dada

Es decir, dada una esfera de unidad, ¿cuántas esferas de unidad más pueden tocarla sin que ninguna se superponga? La pregunta se hará en el espacio N dimensional, donde se entiende que una esfera es una esfera dimensional N-1.

Por ejemplo:

en un espacio de 2 dimensiones, un círculo unitario puede tocar otros 6 círculos unitarios.
En un espacio tridimensional, una esfera unitaria puede tocar otras 12 esferas unitarias.

La página de Wikipedia enumera valores para el espacio dimensional de 1 a 24. Sin embargo, algunos de estos aún no se conocen con precisión, por lo que solo se proporcionan un límite inferior y superior. La tabla se reproduce aquí para que permanezca fija, independientemente de cualquier estrechamiento futuro de los rangos debido a nuevas pruebas. Las soluciones se juzgan en función de esta tabla fija, incluso si la página de Wikipedia se modifica en el futuro.

Tabla de límites

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

Entrada

La dimensión: un entero del 1 al 24 (inclusive).

Aquí "entero" indica que la entrada no tendrá una parte fraccionaria, puede ser 2o 3nunca 2.5. Una solución aún puede tomar la entrada como flotante, o una cadena, por ejemplo.

Salida

Un número en el rango relevante, desde el límite inferior hasta el límite superior para esa entrada (inclusive).

La salida debe ser determinista (siempre la misma para la misma entrada).

La salida debe ser entera. Por ejemplo, para la entrada de 5las posibles salidas válidas son 40, 41, 42, 43, 44. Tenga en cuenta que esta es una restricción en el valor, no en el tipo. Es aceptable devolver un flotador, siempre que tenga una parte fraccional cero. Por ejemplo, 41.5no sería válido, pero 41.0sería válido.

Tanteo

Este es el código de golf . Su puntaje es el número de bytes en su código. Para cada idioma, el ganador es la solución con la puntuación más baja.

code-golf geometry approximation trichoplax
fuente

66

Problema de aproximación realmente genial.

qwr

11

Julia 0.6 , 52 bytes

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

Pruébalo en línea!

¿Cómo?

¡Aprendizaje automático! (Un poco. Tal vez. En realidad no ) .

Primero, al trazar los datos del límite inferior y superior contra N, y algunas pruebas y errores manuales, parecía que una función exponencial podría encajar bien para N> = 8. Después de algunos intentos de encontrar esta función manualmente, recurrí al uso de un parámetro función de sintonización para sintonizar (donde K = 8 a 24) para encontrar a, byc de modo que la expresión proporcione valores que se encuentren dentro del rango correcto para cada K (con un rango sucesivamente menor de valores posibles y precisiones correspondientemente más altas para a, b, c en diferentes ejecuciones de la función). Había algunos de esos conjuntos de valores, aunque ninguno de ellos podía ajustarse exactamente al caso N = 24, así que elegí uno que tenía 0 y codifiqué el valor para N = 24. $a * e^{b K} + c$ c

Para el N inferior, del 1 al 7, esperaba encontrar alguna expresión o polinomio más simple, pero no pude encontrar ninguno que se ajustara. Entonces, volviendo a ajustar , esta vez para K = 1 a 7 (aunque realmente no pensé que un exponencial sería un ajuste correcto en este caso, basado en las tendencias de la trama visual). Afortunadamente, hay eran los parámetros a, b, c que podría dar valores correctos en toda la gama aquí (al menos dentro de una llamada). $a * e^{b K} + c$ ceil

sundar - Restablecer a Monica
fuente

66

No consideraría que un gridsearch sea aprendizaje automático. Es fuerza bruta en todo caso.

qwr

55

¡Pero está adentro MLBase! J / k, las líneas alrededor de ML están borrosas como siempre, pero esto probablemente es demasiado básico para merecer el aprendizaje automático de etiquetas. Por otra parte, ¡siempre es útil tener una palabra de moda!

sundar - Restablecer Monica

cuando decimos Machine Learning, pensamos principalmente en polinomios con n = 2 o regexps

aaaaa dice que reinstalar a Monica el

2

cuando digo aprendizaje automático, pienso en redes neuronales, árboles de decisión, HMM, perceptrón ...

qwr

@qwr Llego muy tarde, pero la regresión se considera parte del aprendizaje automático, además de todas esas cosas. (¡Y más! SVM, etc.)

Quintec

7

x86, 62 59 53 50 bytes

Mi solución utiliza una tabla de búsqueda de bytes y se desplaza por 2 (sin cálculos de FP). Las dimensiones 9 a 23 proporcionan suficiente margen de maniobra para el cambio. Entrada eaxy salida en ecx.

-3 intercambiando eaxy ecxya que cmp $imm, %ales más corto que cmp $imm, %cl.

-4 al no tratar el caso N = 24 por separado pero aplicando el ajuste a todos los tiempos 1024 casos.

-2 al no regresar temprano (estúpido)

-3 usando la tabla como desplazamiento y en movzbllugar de poner a cero conxor

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 (tabla en .textlugar de .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
fuente

1

La tabla es de solo lectura, por lo que normalmente la colocaría .rodata, no de .datatodos modos. (O en Windows, aparentemente .rdata). La .rodatasección se vincula como parte del segmento de texto.

Peter Cordes

1

Y, por cierto, la gente normal escribe shl, especialmente cuando su número no está firmado (solía movzblcargarlo, no movsbl). Por supuesto, sales solo otro nombre para el mismo código de operación. emite gcc sal, pero es bastante raro verlo en código escrito a mano.

Peter Cordes

7

JavaScript (ES6), 60 bytes

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

Pruébalo en línea!

¿Cómo?

$a_{24}=196560$

Todos los demás términos se calculan recursivamente, utilizando:

{\begin{cases} a_{1} = 2 \\ a_{n + 1} = a_{n} \times \frac{24}{q_{n}} \end{cases}

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

$q_n$

{\begin{cases} q_{1} = 8 \\ q_{2} = 12 \\ q_{3} = 12 \\ q_{4 4} = 13 \\ q_{5 5} = 14 \\ q_{6 6} = 14 \\ q_{7 7} = 13 \\ q_{norte} = dieciséis, & para norte > 7 7 \end{cases}

$\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}$

conduciendo a las siguientes proporciones:

3, 2, 2, \frac{24}{13}, \frac{12}{7 7}, \frac{12}{7 7}, \frac{24}{13}, \frac{3}{2}, \frac{3}{2}, ..., \frac{3}{2}

$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}$

El resultado final finalmente se derriba y se devuelve.

Resumen de resultados

Los resultados aproximados se dan con 2 decimales.

  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
fuente

1

Lo primero que vi fue operadores bit a bit dentro de una función recursiva de JavaScript; Lo primero que pensé fue "¿Qué está haciendo Arnauld ...?"

MattH

Muy buena mesa. ¿Lo hiciste manualmente?

qwr

1

@qwr Sí, eso es principalmente una edición de Notepad ++. Acabo de usar un script para generar los valores en las primeras 4 columnas.

Arnauld

4

Jalea , 29 26 bytes

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

Pruébalo en línea!

Cómo funciona

“~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
fuente

1

JavaScript (Node.js) , 120 99 bytes

Se descartaron 21 bytes. Gran reducción gracias a la sugerencia de tsh de agregar un agujero al comienzo de la matriz (ahorrando dos bytes yendo de n-1a n, y apuntando a números redondos dentro de los límites inferior y superior, reduciéndolos así de la notación de punto fijo como 1154a la notación exponencial como 2e3.

Nuevamente, mi objetivo original era mostrar cuán ligera sería la forma "tonta" (por ejemplo, no usar ninguna matemática real, como la respuesta de Arnauld. Es impresionante que todavía hubiera espacio para reducirla sin ninguna transformación o cálculo).

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]

Pruébalo en línea!

El doble de la longitud de la respuesta de Arnauld, 0 cantidad de la complejidad.

JavaScript (Node.js) , 129 128 bytes

(-1 byte gracias a la sugerencia de usar 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]

Pruébalo en línea!

Para satisfacer las demandas de ser interesante, robé la lógica de la respuesta x86 y construí la matriz a partir de eso. Haciéndolo 9 bytes más largo. Pero un poco más interesante.

Antonio
fuente

bosteza al menos prueba algo interesante

qwr

Pensé que demostrar el enfoque más directo (y, por lo tanto, técnicamente, la longitud razonable más larga) fue bastante interesante. Arnauld es posiblemente el más corto que puede obtener en JS, pero el más largo es solo el doble de bytes.

Anthony

1

El punto de la tabla de búsqueda de bytes es quizás usar una cadena de bytes o algo así como "02060c1828487ef0" donde cada entrada es un byte o 2 caracteres en hexadecimal si lo prefiere. Almacenar los números directamente en decimal lleva hasta 3 caracteres. También use bitshifting ...

qwr

2

Al menos debe eliminar f=, cambiar (x)a x, agregar un agujero y cambiar x-1a x. Tio ; y quizás redondearlos a TIO 99 bytes

tsh

55

Bienvenido a PPCG! :)

Shaggy

1

Rúnico, 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

(Tenga en cuenta que la esquina inferior derecha debe contarse para los bytes: están llenos implícitamente de espacios).

El exe de TIO necesita una actualización en la que se base esta respuesta (y estoy reparando algunos otros agujeros antes de pedirle a Dennis que reconstruya). Pero agregue un valor (asegúrese de agregar espacios en blanco en las líneas 2 y 3 si usa más de un carácter para el valor en la primera línea). Aquí está la forma más fácil de escribir los valores necesarios:

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

Pruébalo en línea!

Funcionalmente, este es un puerto de respuesta de Sundar de Julia (pero Runic no tiene un comando para empujar ea la pila (o realmente, cualquier valor decimal), por lo que se necesitaba una aproximación). La aproximación para eentradas inferiores a 8 es más precisa, ya que la pérdida de precisión dio como resultado valores que se encuentran fuera del rango permitido de salidas (por ejemplo 7, produciría 125). Ceil()se logró mediante la conversión a un personaje y luego a un número (esto falló para valores excepcionalmente grandes, por lo que a 40k lo dividí por 100, hice la conversión hacia atrás y luego la multipliqué por 100 nuevamente).

Probablemente haya espacio para simplificar la disposición (por ejemplo, ejecutar el punto de entrada verticalmente, debajo, o encontrar una forma de comprimir las aproximaciones e), pero estoy contento de poder hacer el cálculo.

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

Actualización del intérprete:

Con la lectura de entrada de fijación de inserción , Runic ahora tiene varias funciones matemáticas y la capacidad de analizar cadenas como dobles. Eso simplificará enormemente esta respuesta, pero la dejaré como para mostrar el esfuerzo que puse en ella (agregué las funciones matemáticas de argumento único y el análisis de cadenas poco después de la publicación: ya había puesto Sin / Cos / Tan en mi lista de tareas pendientes, pero no había considerado Exp, Abs, Log, etc. y se estaba quedando sin caracteres). TIO debería actualizarse en las próximas 24-48 horas, dependiendo de cuándo lo vea Dennis.

212,+16,+1c2*,+1cX,+se reduciría a -> 1'eAcon esta actualización del intérprete. Amuestra un carácter y un valor y realiza una operación matemática sobre ese valor en función del carácter que aparece ( een este caso es Exp()y Exp(1)devuelve e ).

Draco18s
fuente

Dos docenas de aproximaciones de números de besos

Tabla de límites

Entrada

Salida

Tanteo

Respuestas:

Julia 0.6 , 52 bytes

¿Cómo?

x86, 62 59 53 50 bytes

JavaScript (ES6), 60 bytes

¿Cómo?

Resumen de resultados

Jalea , 29 26 bytes

Cómo funciona

JavaScript (Node.js) , 120 99 bytes

JavaScript (Node.js) , 129 128 bytes

Rúnico, 173 bytes

Actualización del intérprete: