Два десятка приближения числа поцелуев

26

Если задано число от 1 до 24, выведите число поцелуев, насколько вам известно (некоторые числа будут иметь более одного приемлемого результата). Знание геометрии не является обязательным, поскольку все результаты перечислены ниже.

Со страницы Википедии о проблеме числа поцелуев :

число поцелуев определяется как число неперекрывающихся единичных сфер, которые могут быть расположены таким образом, чтобы они каждый касались другой данной единичной сферы

То есть, учитывая, что одна единичная сфера, сколько еще единичных сфер может коснуться ее, не перекрывая ни одну из них? Вопрос будет задан в N-мерном пространстве, где под сферой понимается N-1-мерная сфера.

Например:

  • в двухмерном пространстве единичный круг может касаться 6 других единичных кругов.
  • в трехмерном пространстве единичная сфера может касаться 12 других единичных сфер.

На странице Википедии перечислены значения от 1 до 24 пространств. Однако некоторые из них еще не известны точно, поэтому даны только нижняя и верхняя границы. Таблица воспроизводится здесь так, чтобы она оставалась фиксированной, независимо от будущего сужения диапазонов из-за новых доказательств. Решения оцениваются по этой фиксированной таблице, даже если страница Википедии будет изменена в будущем.

Таблица границ

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

вход

Размерность: целое число от 1 до 24 (включительно).

Здесь «целое число» указывает, что входные данные не будут иметь дробной части - это может быть 2или 3никогда 2.5. Решение может по-прежнему принимать ввод в виде числа с плавающей запятой или, например, строки.

Выход

Число в соответствующем диапазоне, от нижнего предела до верхнего предела для этого входа (включительно).

Вывод должен быть детерминированным (всегда одинаковым для одного и того же ввода).

Вывод должен быть целым числом. Например, для ввода 5возможных действительных выходов 40, 41, 42, 43, 44. Обратите внимание, что это ограничение по значению, а не по типу. Допустимо возвращать число с плавающей запятой, если оно имеет нулевую дробную часть. Например, 41.5не будет действительным, но 41.0будет действительным.

счет

Это . Ваша оценка - это количество байтов в вашем коде. Для каждого языка победителем является решение с самым низким баллом.

Trichoplax
источник
6
Действительно крутая задача аппроксимации.
Qwr

Ответы:

11

Юлия 0.6 , 52 байта

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

Попробуйте онлайн!

Как?

Машинное обучение! (Вроде. Может быть. Не совсем. )

a*ебК+сc

a*ебК+сceil

sundar - Восстановить Монику
источник
6
Я бы не считал поиск по сетке машинным обучением. Это грубая сила, если что-нибудь.
Qwr
5
Но это в MLBase!!! Дж / к, линии вокруг ML размыты как всегда, но это, вероятно , слишком просто, чтобы заслужить машинное обучение на этикетке. Опять же, всегда полезно вставить модное слово в!
sundar - Восстановить Монику
когда мы говорим «Машинное обучение», мы в основном думаем о полиномах с n = 2 или регулярных выражениях
ааааа говорит, что восстановите Монику
2
когда я говорю о машинном обучении, я думаю о нейронных сетях, деревьях решений, HMM, персептроне ...
QWR
@qwr Я очень опоздал, но регрессия действительно считается частью машинного обучения, в дополнение ко всем этим вещам. (И еще! SVM и т. Д.)
Quintec
7

x86, 62 59 53 50 байт

Мое решение использует таблицу поиска байтов и сдвиг на 2 (без вычислений FP). Размеры с 9 по 23 обеспечивают достаточную свободу для переключения. Ввод eaxи вывод в ecx.

-3 по обмену eaxи ecxтак cmp $imm, %alкак короче чем cmp $imm, %cl.

-4 не обрабатывая случай N = 24 отдельно, а применяя корректировку ко всем 1024 случаям.

-2 не возвращаясь рано (глупо)

-3 с использованием таблицы в качестве смещения и movzblвместо обнуления с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 (таблица .textвместо .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
источник
1
Таблица предназначена только для чтения, поэтому обычно ее вставляют .rodata, а не в .dataлюбом случае. (Или на винде, видимо .rdata). .rodataРаздел компонуется как часть текстового сегмента.
Питер Кордес
1
И кстати, нормальные люди пишут shl, особенно когда ваш номер не подписан (вы movzblзагружали его, а не movsbl). Конечно, salэто просто другое имя для того же кода операции. Издает gcc sal, но это довольно редко можно увидеть в рукописном коде.
Питер Кордес
7

JavaScript (ES6), 60 байт

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

Попробуйте онлайн!

Как?

a24знак равно196560

Все остальные термины вычисляются рекурсивно с использованием:

{a1знак равно2aN+1знак равноaN×24QN

QN

{Q1знак равно8Q2знак равно12Q3знак равно12Q4знак равно13Q5знак равно14Q6знак равно14Q7знак равно13QNзнак равно16,для N>7

приводя к следующим соотношениям:

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

Окончательный результат в конечном итоге сорван и возвращен.

Сводка результатов

Приближенные результаты приведены с двумя десятичными знаками.

  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
источник
1
Первое, что я увидел, это побитовые операторы внутри рекурсивной функции JavaScript; Первое, что я подумал, было: «Что
Арнаулд задумал
Действительно хороший стол. Вы сделали это вручную?
Qwr
1
@qwr Да, это в основном редактирование в Notepad ++. Я просто использовал скрипт для генерации значений в первых 4 столбцах.
Арно
4

Желе , 29 26 байт

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

Попробуйте онлайн!

Как это работает

“~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.
Деннис
источник
1

JavaScript (Node.js) , 120 99 байт

Сбросил 21 байт. Значительное сокращение благодаря предложению tsh добавить дыру в начало массива (сохраняя два байта, идущих от n-1и n, и нацеливаясь на круглые числа в пределах нижней и верхней границ, таким образом уменьшая их от записи с фиксированной точкой, как 1154до экспоненциальной записи нравится2e3 .

Опять же, моя первоначальная цель состояла в том, чтобы показать, насколько легким будет «тупой» путь (например, без использования какой-либо реальной математики, как ответ Арно. Это впечатляет, что все еще есть место, чтобы уменьшить его без каких-либо преобразований или вычислений).

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]

Попробуйте онлайн!

В два раза длиннее ответа Арно, 0 - сложность.

JavaScript (Node.js) , 129 128 байтов

(-1 байт благодаря предложению использовать битовый сдвиг)

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]

Попробуйте онлайн!

Чтобы удовлетворить требования интереса, я украл логику из ответа x86 и построил массив из этого. Делая это на 9 байт длиннее. Но немного интереснее.

Энтони
источник
зевает хотя бы попробуй что-нибудь интересное
qwr
Я думал, что демонстрация самого простого подхода (и, следовательно, технически самой длинной разумной длины) была довольно интересной. Arnauld's, возможно, самый короткий, который вы можете получить в JS, но самый длинный - всего в два раза больше байтов.
Энтони
1
Смысл таблицы поиска байтов состоит в том, чтобы, возможно, использовать строку байтов или просто что-то вроде «02060c1828487ef0», где каждая запись представляет собой один байт или 2 символа в шестнадцатеричном формате, если вы предпочитаете. Хранение чисел непосредственно в десятичном виде занимает до 3 символов. Также используйте битшифтинг ...
QWR
2
Вы должны по крайней мере удалить f=, изменить (x)на x, добавить отверстие и изменить x-1на x. TIO ; и, возможно, округлите их до 99 байтов
TIO
5
Добро пожаловать в PPCG! :)
Лохматый
1

Рунический, 173 байта

>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

(Обратите внимание, что нижний правый угол должен учитываться для байтов: они неявно заполнены пробелами.)

Исполняющему TIO требуется обновление, на которое опирается этот ответ (и я исправляю некоторые другие дыры перед тем, как попросить Денниса восстановить). Но добавьте значение (обязательно добавьте пробелы в строках 2 и 3, если в качестве значения в первой строке используется более одного символа). Вот самый простой способ записать необходимые значения:

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

Попробуйте онлайн!

Функционально это порт ответа Джулии Сундара (но у Руника нет команды для добавления eв стек (или, действительно, любого десятичного значения), поэтому необходимо было приближение). Аппроксимация для eвходов менее 8 является более точной, поскольку потеря точности привела к значениям, лежащим за пределами допустимого диапазона выходных данных (например, 7приведет к 125). Ceil()было достигнуто путем преобразования в символ, а затем обратно в число (это не удалось для исключительно больших значений, поэтому при 40k я делил его на 100, делаю преобразование в и обратно, затем умножаю на 100).

Вероятно, есть некоторая возможность упростить расположение (например, запустить точку входа вертикально, снизу или найти способ сжать аппроксимации для e), но я счастлив, что могу просто выполнить вычисление.

/?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 байт.

Обновление переводчика:

Благодаря чтению ввода с фиксацией толчка Runic теперь имеет несколько математических функций и возможность разбирать строки как двойные. Это значительно упростит этот ответ, но я оставлю его таким, чтобы оно показывало усилия, которые я вложил в него (я добавил функции Math с одним аргументом и разбор строк вскоре после публикации: я уже включил Sin / Cos / Tan мой список дел, но он не рассматривал Exp, Abs, Log и т. д., и в нем заканчивались символы). Обновление TIO должно произойти в течение следующих 24-48 часов, в зависимости от того, когда его увидит Деннис.

212,+16,+1c2*,+1cX,+сократил бы до -> 1'eAс этим обновлением интерпретатора. Aвыскакивает символ и значение и выполняет математическую операцию над этим значением на основе извлеченного символа ( eв этом случае возвращает Exp()и Exp(1)возвращает e ).

Draco18s
источник