Предисловие

В известной песне «Двенадцать дней Рождества» рассказчику ежедневно преподносят несколько подарков. Песня является кумулятивной - в каждом стихе добавляется новый подарок, количество которого на один выше, чем подарок перед ним. Одна куропатка, две горлицы, три французские курицы и так далее.

В любом данном стихе, N , мы можем вычислить кумулятивную сумму подарков на данный момент в песне, найдя N- е тетраэдрическое число , которое дает результаты:

Verse 1: 1
Verse 2: 4
Verse 3: 10
Verse 4: 20
Verse 5: 35
Verse 6: 56
Verse 7: 84
Verse 8: 120
Verse 9: 165
Verse 10: 220
Verse 11: 286
Verse 12: 364

Например, после 4-го стиха у нас было 4 * (1 куропатка) , 3 * (2 черепахи) , 2 * (3 французских курицы) и 1 * (4 призывающих птицы) . Суммируя их, мы получаем 4(1) + 3(2) + 2(3) + 1(4) = 20.

Соревнование

Ваша задача - написать программу или функцию, которая, учитывая положительное целое число, представляющее количество подарков 364 ≥ p ≥ 1 , определяет, какой это день (стих) Рождества.

Например, если р = 286 , мы находимся в 11-й день Рождества. Однако, если р = 287 , то начинается следующая загрузка подарков, то есть это 12-й день.

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

Правила:

• Это код-гольф , поэтому выигрывает самое короткое решение (в байтах).
• Применяются стандартные лазейки для игры в гольф.
• Когда дело доходит до дней, ваша программа должна быть 1-проиндексирована.
• Ваша заявка должна быть полной программой или функцией, но не фрагментом.

Тестовые случаи

1   ->  1
5   ->  3
75  ->  7
100 ->  8
220 ->  10
221 ->  11
364 ->  12

Желе , 7 6 байт

-1 байт благодаря Деннису (используйте векторизованный минимум «и первый индекс i)

R+\⁺«i

TryItOnline

Как?

Не все так эффективно - вычисляет тетраэдрические числа от 1 до n по порядку в списке и возвращает основанный на 1 индекс первого, который равен или больше.

R+\⁺«i - main link: n
R      - range                          [1,2,3,4,...,n]
 +\    - cumulative reduce by addition  [1,3,6,10,...,sum([1,2,3,4,...n])] i.e. triangle numbers
   ⁺   - duplicate previous link - another cumulative reduce by addition
                                        [1,4,10,20,...,nth tetrahedral]
    «  - min(that, n)                   [1,4,10,20,...,n,n,n]
     i - first index of n (e.g. if n=12:[1,4,10,12,12,12,12,12,12,12,12,12] -> 4)

Предыдущий 7 byters с использованием пониженного диапазона [0,1,2,3,...,n-1]и подсчетом tetrahedrals меньше п:
Ḷ+\⁺<µS,
Ḷ+\⁺<ḅ1,
Ḷ+\⁺<ċ1, и
Ḷ+\⁺<¹S

Python , 27 байт

lambda n:int((n*6)**.33359)

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

Прямая формула с некоторой подгонкой кривой, такая же, как оригинальная, найденная Level River St.

Смещенное уравнение i**3-i==n*6близко к i**3==n*6большому i. Это решает до i=(n*6)**(1/3). Принимая слово раундов вниз по мере необходимости, компенсируя один на один.

Но есть 6 входов на границах, где ошибка принимает значение ниже целого числа, которое должно быть выше. Все это можно исправить, слегка увеличив показатель степени без дополнительных ошибок.

Python , 38 байт

f=lambda n,i=1:i**3-i<n*6and-~f(n,i+1)

Формула n=i*(i+1)*(i+2)/6для тетраэдрических чисел может быть более хорошо написана i+1как n*6=(i+1)**3-(i+1). Итак, мы находим самый низкий iдля которого i**3-i<n*6. Каждый раз, когда мы увеличиваем, iначиная с 1, рекурсивные вызовы добавляют 1к выводу. Начиная с, i=1а не i=0компенсирует сдвиг.

J , 12 байт

2>.@-~3!inv]

Возможно, есть более удачный способ сделать это, но это прекрасная возможность использовать инверсию встроенной функции J.

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

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

2>.@-~3!inv]  Monadic verb. Argument: n

           ]  Right argument; yield n.
      3       Yield 3.
       !inv   Apply the inverse of the ! verb to n and 3. This yields a real number.
              x!y computes Π(y)/(Π(y-x)Π(x)), where Π is the extnsion of the 
              factorial function to the real numbers. When x and y are non-negative
              integers, this equals yCx, the x-combinations of a set of order y.
 >.@-~        Combine the ceil verb (>.) atop (@) the subtraction verb (-) with
              swapped arguments (~).
2             Call it the combined verbs on the previous result and 2.

Python , 22 байта

lambda n:n**.3335//.55

Сильно вдохновлен ответом @ xnor на Python .

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

Желе , 7 байт

R‘c3<¹S

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

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

R‘c3<¹S  Main link. Argument: n

R        Range; yield [1, ..., n].
 ‘       Increment; yield [2, ..., n+1].
  c3     Combinations; yield [C(2,3), ..., C(n+1,3)].
    <¹   Yield [C(2,3) < n, ..., C(n+1,3) < n].
      S  Sum; count the non-negative values of k for which C(k+2,3) < n.

JavaScript (ES6), 33 байта

n=>(F=k=>k<n?F(k+3*k/i++):i)(i=1)

На основе рекурсивной формулы:

a(1) = 1
a(i) = (i + 3) * a(i - 1) / i

Второе выражение также можно записать как ...

a(i) = a(i - 1) + 3 * a(i - 1) / i

... который мы используем здесь.

a(i - 1)фактически хранится в kпеременной и передается на следующую итерацию до k >= n.

Контрольные примеры

let f =

n=>(F=k=>k<n?F(k+3*k/i++):i)(i=1)

console.log(f(1));   // ->  1
console.log(f(5));   // ->  3
console.log(f(75));  // ->  7
console.log(f(100)); // ->  8
console.log(f(220)); // ->  10
console.log(f(221)); // ->  11
console.log(f(364)); // ->  12

Рубин, 26 байт

Изменить: альтернативная версия, еще 26 байтов

->n{(n**0.3333*1.82).to_i}

Оригинальная версия

->n{((n*6)**0.33355).to_i}

Использует тот факт, T(x) = x(x+1)(x+2)/6 = ((x+1)**3-(x+1))/6что очень близко к (x+1)**3/6.

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

Тестовая программа и вывод

f=->n{((n*6)**0.33355).to_i}
[1,4,10,20,35,56,84,120,165,220,286,364].map{|i|p [i,f[i],f[i+1]]}

[1, 1, 2]
[4, 2, 3]
[10, 3, 4]
[20, 4, 5]
[35, 5, 6]
[56, 6, 7]
[84, 7, 8]
[120, 8, 9]
[165, 9, 10]
[220, 10, 11]
[286, 11, 12]
[364, 12, 13]

JavaScript, 36 33 байта

-3 байта благодаря Люку (делая функцию карри)

n=>f=i=>n<=i/6*-~i*(i+2)?i:f(-~i)

Это безымянная лямбда-функция, которую можно назначать funcи вызывать func(220)(), как описано в этом мета-посте . Моя оригинальная функция без карри выглядит так:

f=(n,i)=>n<=-~i*i/6*(i+2)?i:f(n,-~i)

В этом ответе используется тот факт, что x- е тетраэдрическое число можно найти с помощью следующей функции:

Подчинение работает путем рекурсивного увеличения iи поиска tetrahedral(i), пока оно не станет больше или равно n(количество подарков).

При вызове с одним аргументом, как и ожидалось i = undefined, и, следовательно, не больше, чем n. Это средство f(n,-~i)выполняется и -~undefinedоценивает 1, что запускает рекурсию.

Тестовый фрагмент:

func = n=>f=i=>n<=i/6*-~i*(i+2)?i:f(-~i)

var tests = [1, 5, 75, 100, 220, 221, 364];
tests.forEach(n => console.log(n + ' => ' + func(n)()));

MATL , 12 11 байт

`G@H+IXn>}@

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

объяснение

`       % Do...while
  G     %   Push input, n
  @     %   Push iteration index (1-based), say m
  H     %   Push 2
  +     %   Add
  I     %   Push 3
  Xn    %   Binomial coefficient with inputs m+2, 3
  >     %   Is n greater than the binomial coefficient? If so: next iteration
}       %   Finally (execute after last iteration, before exiting the loop)
  @     %   Push last iteration index. This is the desired result
        % End (implicit)
        % Display (implicit)

05AB1E , 10 байтов

XµNÌ3c¹‹_½

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

объяснение

Xµ          # loop until counter equals 1
  NÌ3c      # binomial_coefficient(iteration_index+2,3)
      ¹     # push input
       ‹_   # not less than
         ½  # if true, increment counter
            # output last iteration index

Пайк, 11 байт

#3RL+B6f)lt

Попробуй это здесь!

#3RL+B6f)   -  while rtn <= input as i:
 3RL+       -     i+j for j in range(3)
     B      -    product(^)
      6f    -   ^/6
         lt - len(^)-1

Mathematica, 26 байтов

(0//.i_/;i+6#>i^3:>i+1)-1&

Безымянная функция, принимающая неотрицательный целочисленный аргумент и возвращающая неотрицательное целое число (да, это работает и для дня 0). Мы хотим найти наименьшее целое число, iдля которого #максимально возможное входное значение i(i+1)(i+2)/6, которое является формулой для количества подарков, полученных в первые iдни. Через легкий алгебраический обман, неравенство # ≤ i(i+1)(i+2)/6эквивалентно (i+1) + 6# ≤ (i+1)^3. Таким образом, структура 0//.i_/;i+6#>i^3:>i+1начинается с 0и продолжает добавляться 1до тех пор, пока выполняется тест i+6#>i^3; затем (...)-1&вычитает 1в конце (вместо того, чтобы тратить байты с круглыми скобками внутри неравенства).

Если мы продолжим 12 Дней Рождества, мы сможем обработать около 65536 дней до того, как встроенный предел рекурсии //.остановит процесс ... это примерно 4,7 * 10 ^ 13 дней, или примерно в десять раз больше возраста вселенной на данный момент. ....

J , 9 байт

I.~3!2+i.

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

Это более неэффективно, чем использование обратного факториала, но оказывается короче.

Например, если входное целое число равно n = 5, задайте диапазон [2, n+1].

2 3 4 5 6 choose 3
0 1 4 10 20

Это первые 5 тетраэдрических чисел. Следующим шагом является определение, к какому интервалу (дням) относится n . Есть n + 1 = 6 интервалов.

0 (-∞, 0]
1 (0, 1]
2 (1, 4]
3 (4, 10]
4 (10, 20]
5 (20, ∞)

Тогда n = 5 принадлежит интервалу 3, (4, 10]а результат равен 3.

объяснение

I.~3!2+i.  Input: integer n
       i.  Range [0, n)
     2+    Add 2 to each
   3!      Combinations nCr with r = 3
I.~        Interval index of n

Python, 43 байта

f=lambda n,i=0:n*6>-~i*i*(i+2)and-~f(n,i+1)

Сохранено 5 байтов благодаря @FlipTack и еще 3 благодаря @xnor !

Japt , 12 байт

1n@*6§X³-X}a

Проверьте это онлайн! или проверить все тестовые случаи одновременно

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

1n@*6§X³-X}a  // Implicit: U = input integer
  @       }a  // Find the smallest non-negative integer X which satisfies this condition:
      X³-X    //   (X ^ 3) - X
     §        //   is greater than or equal to
   *6         //   U * 6.
1n            // Subtract 1 from the result.
              // Implicit: output result of last expression

Это упрощение тетраэдрической формулы, которую используют несколько других ответов:

f(x) = (x)(x + 1)(x + 2)/6

Подставляя x - 1в x, мы можем упростить это значительно:

f(x) = (x - 1)(x)(x + 1) / 6
f(x) = (x - 1)(x + 1)(x) / 6
f(x) = (x^2 - 1)(x) / 6
f(x) = (x^3 - x) / 6

Следовательно, правильный результат на единицу меньше наименьшего целого числа, xтакого, что (x^3 - x) / 6больше или равно входному значению.

13-байтовое решение, вдохновленное ответом @ xnor :

p.3335 /.55 f

Еще несколько решений @ETHproductions, и я поиграл с

J+@*6§X³-X}a 
@*6§X³-X}a -1
@§X/6*°X*°X}a 
_³-V /6¨U}a -1
§(°V nV³ /6?´V:ß
§(°VV³-V /6?´V:ß

Проверьте это здесь .

SmileBASIC, 43 байта

INPUT X
WHILE X>P
I=I+1
R=R+I
P=P+R
WEND?I

Iэто день, Rэто iе треугольное число и Pявляется iй четырехгранный число (количество подарков).

Я думаю, что подобный ответ на другом языке, возможно: x=>{while(x>p)p+=r+=++i;return i}мог бы быть довольно хорошим.

Python 3, 48 46 байт

f=lambda x,i=1:f(x,i+1)if(i+3)*i+2<x/i*6else i

Mathematica, 31 25 байт

Floor@Root[x^3-x-6#+6,1]&

Haskell, 21 23 байта

floor.(**(1/3)).(*6.03)

Редактировать: Как указал xnor, оригинальное решение ( floor.(/0.82).(**0.4)) не работало между рождественскими днями

Пакетный, 69 байт

@set/an=d=t=0
:l
@set/at+=d+=n+=1
@if %t% lss %1 goto l
@echo %n%

Вручную вычисляет числа тетраэдра.

Pyth 11 байтов

/^Q.3335.55

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

в значительной степени только что перевел ответ Денниса на Pyth

R, 19 символов

floor((n*6)^.33359)

основанный на ответе Xnor в Python.

QBIC , 19 байт

Это крадет формулу @xnor:

:?int((a*6)^.33359)

Я попытался набрать разрешение до .3336, чтобы сохранить байт, но в конечном тесте это не удалось.

Bash + bc, 44 байта

bc -l <<< "f=e(.33359*l($1*6));scale=0;f/1"