Przedmowa

W znanej kolędie Dwanaście dni świąt Bożego Narodzenia narrator otrzymuje codziennie kilka prezentów. Piosenka jest kumulatywna - w każdym wersecie dodawany jest nowy prezent, o jeden wyższy od prezentu przed nim. Jedna kuropatwa, dwie gołębie żółwiowe, trzy francuskie kury i tak dalej.

W dowolnym wierszu N możemy obliczyć łączną sumę prezentów do tej pory w piosence, znajdując N- tą liczbę czworościenną , która daje wyniki:

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

Na przykład po wersecie 4 mieliśmy 4 * (1 kuropatwa) , 3 * (2 turkawki) , 2 * (3 kury francuskie) i 1 * (4 wzywające ptaki) . Sumując je, otrzymujemy 4(1) + 3(2) + 2(3) + 1(4) = 20.

Wyzwanie

Twoim zadaniem jest napisanie programu lub funkcji, która przy dodatniej liczbie całkowitej reprezentującej liczbę prezentów 364 ≥ p ≥ 1 , określa, który dzień (wiersz) Bożego Narodzenia jest.

Na przykład, jeśli p = 286 , jesteśmy w 11. dniu świąt Bożego Narodzenia. Jeśli jednak p = 287 , rozpoczęło się kolejne ładowanie prezentów, co oznacza, że ​​jest to 12 dzień.

Matematycznie znajduje to kolejną liczbę czworościenną i zwraca jej pozycję w całej sekwencji liczb czworościennych.

Zasady:

• To jest golf golfowy , więc wygrywa najkrótsze rozwiązanie (w bajtach).
• Obowiązują standardowe luki w grze w golfa.
• Jeśli chodzi o dni, twój program musi mieć indeks 1.
• Twoje zgłoszenie musi być pełnym programem lub funkcją - ale nie fragmentem kodu.

Przypadki testowe

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

Galaretka , 7 6 bajtów

-1 bajt dzięki Dennisowi (użyj minimum wektorowego «i pierwszego indeksu i)

R+\⁺«i

TryItOnline

W jaki sposób?

Nie wszystko tak wydajne - oblicza od 1 do n-tej liczby czworościennej w kolejności na liście i zwraca indeks oparty na 1 pierwszej, która jest równa lub większa.

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)

Poprzednia 7 byters użyciem obniżony zakres [0,1,2,3,...,n-1]mniej i liczenia tetrahedrals niż n:
Ḷ+\⁺<µS,
Ḷ+\⁺<ḅ1,
Ḷ+\⁺<ċ1i
Ḷ+\⁺<¹S

Python , 27 bajtów

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

Wypróbuj online!

Bezpośrednia formuła z pewnym dopasowaniem krzywej, taka sama jak oryginalna znaleziona przez Level River St.

Przesunięte równanie i**3-i==n*6jest zbliżone do i**3==n*6dużego i. To rozwiązuje i=(n*6)**(1/3). W razie potrzeby zabiera głos w dół, kompensując efekt off-by-one.

Ale istnieje 6 danych wejściowych na granicach, gdzie błąd umieszcza go poniżej liczby całkowitej, którą powinien być powyżej. Wszystkie te można naprawić poprzez nieznaczne zwiększenie wykładnika bez wprowadzania dalszych błędów.

Python , 38 bajtów

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

Wzór n=i*(i+1)*(i+2)/6na liczby czworościenne można ładniej zapisać i+1jako n*6=(i+1)**3-(i+1). Tak więc znajdujemy najniższą idla której i**3-i<n*6. Za każdym razem, gdy zwiększamy iod 1, rekurencyjne wywołania zwiększają 1wynik. Zaczynając od, i=1zamiast i=0kompensować zmianę.

J , 12 bajtów

2>.@-~3!inv]

Może to być bardziej golfowy sposób, ale jest to świetna okazja, aby użyć wbudowanej funkcji inwersji J.

Wypróbuj online!

Jak to działa

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 bajty

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

Mocno zainspirowany odpowiedzią Python @ xnor .

Wypróbuj online!

Galaretka , 7 bajtów

R‘c3<¹S

Wypróbuj online!

Jak to działa

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 bajty

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

Na podstawie rekurencyjnej formuły:

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

Drugie wyrażenie można również zapisać jako ...

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

... którego tu używamy.

a(i - 1)jest faktycznie przechowywany w kzmiennej i przekazywany do następnej iteracji do k >= n.

Przypadki testowe

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

Rubinowy, 26 bajtów

Edycja: wersja alternatywna, wciąż 26 bajtów

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

Orginalna wersja

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

Wykorzystuje to, T(x) = x(x+1)(x+2)/6 = ((x+1)**3-(x+1))/6co jest bardzo blisko (x+1)**3/6.

Funkcja po prostu mnoży przez 6, znajduje nieco ulepszoną wersję pierwiastka kostki (tak, wymagane jest 5 miejsc po przecinku) i zwraca wynik obcięty do liczby całkowitej.

Program testowy i wyjście

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 bajtów

-3 bajty dzięki Lukeowi (funkcja curry)

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

Jest to nienazwana funkcja lambda, którą można przypisać funci wywołać func(220)()zgodnie z opisem w tym poście . Moja oryginalna funkcja bez curry wygląda następująco:

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

Ta odpowiedź wykorzystuje fakt, że x- ta liczba czworościenna może być znaleziona za pomocą następującej funkcji:

Przesyłanie polega na rekurencyjnym zwiększaniu ii znajdowaniu tetrahedral(i), aż będzie większe lub równe n(podanej liczbie prezentów).

Po wywołaniu z jednym argumentem zgodnie z oczekiwaniami i = undefined, a zatem nie jest większy niż n. Oznacza to, że f(n,-~i)jest wykonywany i -~undefinedocenia 1, co uruchamia rekurencję.

Fragment testowy:

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 bajtów

`G@H+IXn>}@

Wypróbuj online!

Wyjaśnienie

`       % 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 bajtów

XµNÌ3c¹‹_½

Wypróbuj online!

Wyjaśnienie

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

Pyke, 11 bajtów

#3RL+B6f)lt

Wypróbuj tutaj!

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

Mathematica, 26 bajtów

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

Nienazwana funkcja przyjmująca nieujemną liczbę całkowitą i zwracająca nieujemną liczbę całkowitą (tak, działa również na dzień 0). Chcemy znaleźć najmniejszą liczbę całkowitą, idla której dane wejściowe #są co najwyżej i(i+1)(i+2)/6, czyli wzór na liczbę prezentów podanych w pierwszych idniach. Poprzez łagodną algebraiczną sztuczkę nierówność # ≤ i(i+1)(i+2)/6jest równoważna (i+1) + 6# ≤ (i+1)^3. Struktura 0//.i_/;i+6#>i^3:>i+1zaczyna się od a 0i dodaje, 1dopóki test i+6#>i^3jest spełniony; następnie (...)-1&odejmuje 1na końcu (zamiast wydawać bajty z nawiasami wewnątrz nierówności).

Jeśli pozwolimy, aby 12 Dni Świąt Bożego Narodzenia trwało dalej, możemy obsłużyć około 65536 dni przed wbudowanym limitem rekurencji, aby //.zatrzymać proces ... to około 4,7 * 10 ^ 13 dni lub około dziesięciokrotnie wiek wszechświata do tej pory ....

J , 9 bajtów

I.~3!2+i.

Wypróbuj online!

Jest to bardziej nieefektywne niż użycie odwrotności silni, ale zdarza się, że jest krótsze.

Na przykład, jeśli wejściowa liczba całkowita wynosi n = 5, określ zakres [2, n+1].

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

Są to pierwsze 5 liczb czworościennych. Następnym krokiem jest określenie, do którego przedziału (dnia) n należy. Istnieje n +1 = 6 przedziałów.

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

Zatem n = 5 należy do przedziału 3, który jest, (4, 10]a wynikiem jest 3.

Wyjaśnienie

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 bajty

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

Zaoszczędź 5 bajtów dzięki @FlipTack i kolejne 3 dzięki @xnor !

Japt , 12 bajtów

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

Przetestuj online! lub Zweryfikuj wszystkie przypadki testowe jednocześnie

Jak to dział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

Jest to uproszczenie formuły czworościennej, z której korzysta kilka innych odpowiedzi:

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

Podstawiając x - 1do x, możemy znacznie uprościć ten:

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

Dlatego poprawny wynik jest o jeden mniejszy od najmniejszej liczby całkowitej xtakiej, która (x^3 - x) / 6jest większa lub równa wartości wejściowej.

Roztwór 13-bajtowy, zainspirowany @ XNOR za odpowiedź :

p.3335 /.55 f

Jeszcze kilka rozwiązań @ETHproductions i bawiłem się

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:ß

Sprawdź to tutaj .

SmileBASIC, 43 bajty

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

Ijest dniem, Rjest itrzecią liczbą trójkątną i Pjest iczwartą liczbą czworościenną (liczbą prezentów).

Myślę, że podobna odpowiedź x=>{while(x>p)p+=r+=++i;return i}może być w innym języku: może być całkiem dobra.

Python 3, 48 46 bajtów

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

Mathematica, 31 25 bajtów

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

Haskell, 21 23 bajtów

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

Edycja: Jak wskazał xnor, oryginalne rozwiązanie ( floor.(/0.82).(**0.4)) nie działało między świętami Bożego Narodzenia

Partia, 69 bajtów

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

Ręcznie oblicza liczby czworościanów.

Pyth 11 bajtów

/^Q.3335.55

Wypróbuj online!

właściwie przetłumaczono odpowiedź Dennisa na Pytha

R, 19 znaków

floor((n*6)^.33359)

na podstawie odpowiedzi Xnora w Python.

QBIC , 19 bajtów

To kradnie formułę @xnor:

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

Próbowałem obniżyć rozdzielczość do .3336, aby zapisać bajt, ale to nie powiedzie się na końcowym przypadku testowym.

Bash + bc, 44 bajty

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