Hari Natal yang manakah itu?

27

Kata pengantar

Dalam lagu Natal yang terkenal, The Twelve Days of Christmas , narator dihadiahi beberapa hadiah setiap hari. Lagu ini bersifat kumulatif - di setiap ayat, hadiah baru ditambahkan, dengan jumlah yang lebih tinggi dari hadiah sebelumnya. Satu Partridge, Dua Merpati Penyu, Tiga Ayam Perancis, dan seterusnya.

Pada setiap ayat tertentu, N , kita dapat menghitung jumlah kumulatif hadiah sejauh ini dalam lagu dengan menemukan nomor tetrahedral ke- N , yang memberikan hasil:

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

Misalnya, setelah ayat 4, kami memiliki 4 * (1 ayam hutan) , 3 * (2 burung merpati) , 2 * (3 ayam Perancis) dan 1 * (4 burung pemanggil) . Dengan menjumlahkan ini, kita dapatkan 4(1) + 3(2) + 2(3) + 1(4) = 20.

Tantangan

Tugas Anda adalah menulis sebuah program atau fungsi yang, diberi bilangan bulat positif yang mewakili jumlah hadiah 364 ≥ p ≥ 1 , menentukan hari (ayat) Natal mana yang tepat.

Sebagai contoh, jika p = 286 , kita berada pada hari Natal ke-11. Namun, jika p = 287 , maka muatan hadiah berikutnya telah dimulai, artinya ini adalah hari ke-12.

Secara matematis, ini menemukan nomor tetrahedral berikutnya, dan mengembalikan posisinya di seluruh urutan nomor tetrahedral.

Aturan:

  • Ini adalah , sehingga solusi terpendek (dalam byte) menang.
  • Berlaku celah golf standar.
  • Dalam hal berhari-hari, program Anda harus diindeks 1.
  • Kiriman Anda harus berupa program atau fungsi lengkap - tetapi bukan cuplikan.

Uji Kasus

1   ->  1
5   ->  3
75  ->  7
100 ->  8
220 ->  10
221 ->  11
364 ->  12
FlipTack
sumber
5
Hanya dalam kasus itu membantu siapa pun, n'th jumlah tetrahedral juga jumlah dari pertama n angka segitiga.
DJMcMayhem
Ini mungkin membantu x=>{while(x>p)p+=r+=++i;return i}:, saya yakin itu bisa dibuat lebih pendek dalam bahasa seperti JavaScript.
12Me21
1
Ini adalah tantangan Natal paling awal, bukan? :)
insertusernamehere

Jawaban:

7

Jelly , 7 6 byte

-1 byte berkat Dennis (gunakan vektorised minimum «,, dan indeks pertama, i)

R+\⁺«i

TryItOnline

Bagaimana?

Tidak semua yang efisien - menghitung angka tetrahedral ke-1 sampai ke n secara berurutan dalam daftar dan mengembalikan indeks berbasis-1 dari yang pertama yang sama atau lebih besar.

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)

Sebelumnya 7 byters menggunakan berbagai menurunkan [0,1,2,3,...,n-1]dan menghitung tetrahedrals kurang dari n:
Ḷ+\⁺<µS,
Ḷ+\⁺<ḅ1,
Ḷ+\⁺<ċ1, dan
Ḷ+\⁺<¹S

Jonathan Allan
sumber
19

Python , 27 byte

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

Cobalah online!

Formula langsung dengan beberapa kurva-fitting, sama seperti yang asli yang ditemukan oleh Level River St.

Persamaan bergeser i**3-i==n*6dekat dengan i**3==n*6untuk besar i. Itu teratasi i=(n*6)**(1/3). Turunkan lantai putaran sesuai kebutuhan, mengimbangi off-by-one.

Tapi, ada 6 input pada batas di mana kesalahan membawanya di bawah bilangan bulat itu harus di atas. Semua ini dapat diperbaiki dengan sedikit meningkatkan eksponen tanpa memperkenalkan kesalahan lebih lanjut.


Python , 38 byte

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

Rumus n=i*(i+1)*(i+2)/6untuk angka tetrahedral dapat ditulis dengan lebih baik i+1sebagai n*6=(i+1)**3-(i+1). Jadi, kita menemukan terendah iyang i**3-i<n*6. Setiap kali kami menambah imulai dari 1, panggilan rekursif menambah 1output. Mulai dari i=1alih-alih i=0mengkompensasi pergeseran.

Tidak
sumber
Bagus. Saya berpikir tentang golf milik saya dengan cara ini, tetapi saya tidak melakukannya. Meskipun demikian, saya akan mencoba menggeser; jawaban kita akan tetap berbeda.
0WJYxW9FMN
1
Wow. Yang baru Anda luar biasa.
0WJYxW9FMN
1
Versi 26-byte gagal untuk 364, yang dikecualikan dari rentang pengujian. **.33359bekerja untuk satu byte tambahan.
Dennis
@Dennis Terima kasih. Rentang eksklusif Python menyerang lagi!
xnor
1
lambda n:n**.3336//.5501menghemat beberapa byte.
Dennis
10

J , 12 byte

2>.@-~3!inv]

Mungkin ada cara golf untuk melakukan ini, tetapi ini adalah kesempatan yang bagus untuk menggunakan fungsi inversi bawaan J.

Cobalah online!

Bagaimana itu bekerja

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.
Dennis
sumber
7

Jelly , 7 byte

R‘c3<¹S

Cobalah online!

Bagaimana itu bekerja

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.
Dennis
sumber
2
Kadang-kadang saya heran, apa yang bisa Jelly tidak lakukan?
Sombrero Chicken
1
Suatu hari seseorang akan menjadi seperti "Code Golf MMO berfitur lengkap" dan Dennis akan memposting "Jelly, 29 byte" atau sesuatu yang bodoh seperti itu.
corsiKa
6

JavaScript (ES6), 33 byte

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

Berdasarkan rumus rekursif:

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

Ekspresi kedua juga dapat ditulis sebagai ...

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

... yang mana yang kita gunakan di sini.

a(i - 1)sebenarnya disimpan dalam kvariabel dan diteruskan ke iterasi berikutnya hinggak >= n .

Uji kasus

Arnauld
sumber
Ini sangat singkat! Kerja bagus.
FlipTack
@FlipTack Upaya pertama saya didasarkan pada rumus yang Anda gunakan. Saya harus mengubah rencana saya. ;-)
Arnauld
6

Ruby, 26 byte

Sunting: versi alternatif, masih 26 byte

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

Versi asli

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

Menggunakan fakta T(x) = x(x+1)(x+2)/6 = ((x+1)**3-(x+1))/6yang sangat dekat (x+1)**3/6.

Fungsi ini hanya dikalikan dengan 6, menemukan versi yang sedikit tweak dari akar kubus (ya 5 tempat desimal diperlukan) dan mengembalikan hasilnya terpotong ke integer.

Program uji dan keluaran

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]
Level River St
sumber
0.3336tampaknya berfungsi untuk versi asli. (Sunting: Tidak apa-apa, Dennis menunjukkan saya lupa tentang 364.)
xnor
5

JavaScript, 36 33 byte

-3 bytes terima kasih kepada Luke (membuat fungsinya digulung)

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

Ini adalah fungsi lambda tanpa nama yang dapat ditugaskan funcdan dipanggil dengan func(220)(), seperti yang dijelaskan dalam pos meta ini . Fungsi asli saya, non-kari terlihat seperti ini:

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

Jawaban ini menggunakan fakta bahwa bilangan tetrahedral ke- X dapat ditemukan dengan fungsi berikut:

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

Pengajuan bekerja dengan meningkatkan i, dan menemukan secara rekursiftetrahedral(i) , sampai lebih besar atau sama dengan n(jumlah hadiah yang diberikan).

Ketika dipanggil dengan satu argumen seperti yang diharapkan i = undefined,, dan karenanya tidak lebih besar dari n. Ini berarti f(n,-~i)dieksekusi, dan -~undefineddievaluasi menjadi 1, yang memicu rekursi.


Cuplikan Tes:

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)()));

FlipTack
sumber
Saya akan memposting jawaban yang sama persis. Kalahkan saya 2 menit lagi. Kerja bagus!
Luke
Anda dapat menyimpan 3 byte dengan currying: n=>g=i=>n<=i/6*++i*++i?i-2:g(~-i). Anda akan menyebutnya seperti f(2)().
Luke
@ Lukas tempat yang bagus, fungsi kari saya tidak begitu pendek. Apakah Anda yakin tidak ingin memposting itu sebagai jawaban Anda sendiri?
FlipTack
Nah, saya akan melakukannya jika kami menggunakan formula yang berbeda, tetapi sekarang solusi kami hampir identik. Saya lebih suka membantu Anda mendapatkan pada tingkat yang sama dengan Arnauld. ;-)
Luke
3
i=>n<=iCantik ;-)
ETHproduk
3

MATL , 12 11 byte

`G@H+IXn>}@

Cobalah online!

Penjelasan

`       % 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)
Luis Mendo
sumber
2

05AB1E , 10 byte

XµNÌ3c¹‹_½

Cobalah online!

Penjelasan

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
Emigna
sumber
1
Wow, binom jauh lebih pintar daripada [N2Ý+P6÷¹Q#N>, bagus.
Magic Octopus Urn
2

Pyke, 11 byte

#3RL+B6f)lt

Coba di sini!

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

Mathematica, 26 byte

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

Fungsi yang tidak disebutkan namanya mengambil argumen integer nonnegatif dan mengembalikan integer nonnegatif (ya, berfungsi juga untuk hari 0itu). Kami ingin mencari bilangan bulat terkecil iyang input #paling banyak i(i+1)(i+2)/6, yang merupakan formula untuk jumlah hadiah yang diberikan pada pertama ihari. Melalui tipuan aljabar ringan, ketimpangan # ≤ i(i+1)(i+2)/6setara dengan (i+1) + 6# ≤ (i+1)^3. Jadi struktur 0//.i_/;i+6#>i^3:>i+1dimulai dengan a 0dan terus menambahkan 1selama tes i+6#>i^3puas; lalu (...)-1&kurangi1 di akhir (daripada menghabiskan byte dengan tanda kurung di dalam ketidaksetaraan).

Jika kita membiarkan 12 Hari Natal berlanjut, kita dapat menangani sekitar 65536 hari sebelum batas rekursi //.bawaan untuk menghentikan proses ... itu sekitar 4,7 * 10 ^ 13 hari, atau sekitar sepuluh kali usia alam semesta sejauh ini ....

Greg Martin
sumber
2

J , 9 byte

I.~3!2+i.

Cobalah online!

Ini lebih tidak efisien daripada menggunakan kebalikan faktorial tetapi kebetulan lebih pendek.

Misalnya, jika bilangan bulat input adalah n = 5, buat kisaran [2, n+1].

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

Ini adalah 5 angka tetrahedral pertama. Langkah selanjutnya adalah menentukan interval (hari) n milik. Ada n +1 = 6 interval.

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

Kemudian n = 5 milik interval 3 yaitu(4, 10] dan hasilnya 3.

Penjelasan

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
mil
sumber
2

Python, 43 byte

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

Disimpan 5 byte berkat @FlipTack dan 3 lainnya berkat @xnor !

Loovjo
sumber
Ini memberi f(220)=11, yang seharusnya f(220)=10.
xnor
Oh, saya menggunakan Python 2. Ini membutuhkan Python 3 untuk menghindari pembagian lantai, meskipun mungkin Anda dapat melipatgandakannya di sisi lain sebagai gantinya membuatnya versi-agnostik.
xnor
Saya pikir Anda bisa melakukan and-~f(n,i+1)untuk and f(n,i+1)or i. Anehnya, biasanya lebih pendek ketika Anda menghitung variabel secara rekursif untuk tidak mengembalikannya, tetapi untuk meningkatkan output secara rekursif.
xnor
2

Japt , 12 byte

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

Uji secara online! atau Verifikasi semua kasus uji sekaligus

Bagaimana itu bekerja

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

Ini adalah penyederhanaan rumus tetrahedral yang digunakan beberapa jawaban lain:

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

Dengan mengganti x - 1untuk x, kita dapat menyederhanakan ini jauh:

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

Oleh karena itu, hasil yang benar adalah satu kurang dari bilangan bulat terkecil xsehingga(x^3 - x) / 6 lebih besar atau sama dengan input.

Solusi 13-byte, terinspirasi oleh jawaban @ xnor :

p.3335 /.55 f

Beberapa lebih banyak solusi @ ETHproductions dan saya bermain-main dengan

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

Uji di sini .

Oliver
sumber
1

SmileBASIC, 43 byte

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

Iadalah hari, Radalah ibilangan segitiga th, dan Pmerupakani nomor tetrahedral (jumlah hadiah).

Saya pikir jawaban yang sama dalam bahasa lain, mungkin: x=>{while(x>p)p+=r+=++i;return i}bisa sangat bagus.

12Me21
sumber
Anda ingin ?Ipada akhirnya, bukan?
Nick Matteo
1

Python 3, 48 46 byte

f=lambda x,i=1:f(x,i+1)if(i+3)*i+2<x/i*6else i
0WJYxW9FMN
sumber
@FlipTack Argh! Saya akan memperbaikinya dalam detik ... tidak ada yang downvote, tolong.
0WJYxW9FMN
6
Anda dapat mencegah downvoting dengan menghapus jawaban Anda. Anda masih dapat mengedit jawaban dan membatalkan penghapusan setelah diperbaiki.
Laikoni
Juga, ini masih tidak melakukan apa yang diminta tantangan. Input 221akan crash itu.
FlipTack
Saya sudah menguji ini pada TIO dan crash pada semua input. Apakah ini masalah saya atau ini terjadi pada orang lain?
Itu berhasil untuk saya. Saya akan mengujinya lagi.
0WJYxW9FMN
1

Mathematica, 31 25 byte

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

Haskell, 21 23 byte

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

Sunting: Seperti xnor tunjukkan, solusi asli ( floor.(/0.82).(**0.4)) tidak berfungsi antara hari-hari Natal

Joshua David
sumber
Ini memberikan jawaban yang salah pada banyak masukan, misalnya 221.
xnor
0

Batch, 69 byte

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

Secara manual menghitung angka tetrahedronal.

Neil
sumber
0

R, 19 karakter

floor((n*6)^.33359)

berdasarkan jawaban xnor di Python.

Mark Miller
sumber
0

QBIC , 19 byte

Ini mencuri rumus @xnor:

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

Saya mencoba menekan resolusi ke .3336 untuk menghemat satu byte, tetapi gagal di testcase akhir.

steenbergh
sumber
0

Bash + bc, 44 byte

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