27
\$\begingroup\$

Preface

In the well known carol, The Twelve Days of Christmas, the narrator is presented with several gifts each day. The song is cumulative - in each verse, a new gift is added, with a quantity one higher than the gift before it. One Partridge, Two Turtle Doves, Three French Hens, and so on.

At any given verse, N, we can calculate the cumulative sum of presents so far in the song by finding the Nth tetrahedral number, which gives the results:

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

For example, after verse 4, we've had 4*(1 partridge), 3*(2 turtle doves), 2*(3 French hens) and 1*(4 calling birds). By summing these, we get 4(1) + 3(2) + 2(3) + 1(4) = 20.

The Challenge

Your task is to write a program or function which, given a positive integer representing the number of presents 364 ≥ p ≥ 1, determines which day (verse) of Christmas it is.

For example, if p = 286, we are on the 11th day of Christmas. However, if p = 287, then the next load of presents has begun, meaning it is the 12th day.

Mathematically, this is finding the next tetrahedral number, and returning its position in the whole sequence of tetrahedral numbers.

Rules:

  • This is , so the shortest solution (in bytes) wins.
  • Standard golfing loopholes apply.
  • When it comes to days, your program must be 1-indexed.
  • Your submission must be a full program or a function - but not a snippet.

Test Cases

1   ->  1
5   ->  3
75  ->  7
100 ->  8
220 ->  10
221 ->  11
364 ->  12
\$\endgroup\$
  • 5
    \$\begingroup\$ Just in case it helps anyone, the n'th tetrahedral number is also the sum of the first n triangular numbers. \$\endgroup\$ – DJMcMayhem Jan 27 '17 at 17:52
  • \$\begingroup\$ This might help: x=>{while(x>p)p+=r+=++i;return i}, I'm sure it can be made shorter in a language like JavaScript. \$\endgroup\$ – 12Me21 Jan 27 '17 at 18:09
  • 1
    \$\begingroup\$ This is the earliest Christmas challenge ever, right? :) \$\endgroup\$ – insertusernamehere Jan 29 '17 at 19:29

24 Answers 24

7
\$\begingroup\$

Jelly, 7 6 bytes

-1 byte thanks to Dennis (use vectorised minimum, «, and first index, i)

R+\⁺«i

TryItOnline

How?

Not all that efficient - calculates the 1st through to nth tetrahedral numbers in order in a list and returns the 1-based index of the first that is equal to or greater.

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)

Previous 7 byters using lowered range [0,1,2,3,...,n-1] and counting tetrahedrals less than n:
Ḷ+\⁺<µS,
Ḷ+\⁺<ḅ1,
Ḷ+\⁺<ċ1, and
Ḷ+\⁺<¹S

\$\endgroup\$
19
\$\begingroup\$

Python, 27 bytes

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

Try it online!

A direct formula with some curve-fitting, same as the original one found by Level River St.

The shifted equation i**3-i==n*6 is close to i**3==n*6 for large i. It solves to i=(n*6)**(1/3). Taking the floor the rounds down as needed, compensating for the off-by-one.

But, there are 6 inputs on boundaries where the error takes it below an integer it should be above. All of these can be fixed by slightly increasing the exponent without introducing further errors.


Python, 38 bytes

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

The formula n=i*(i+1)*(i+2)/6 for tetrahedral numbers can be more nicely written in i+1 as n*6=(i+1)**3-(i+1). So, we find the lowest i for which i**3-i<n*6. Each time we increment i starting from 1, the recursive calls adds 1 to the output. Starting from i=1 rather than i=0 compensates for the shift.

\$\endgroup\$
  • \$\begingroup\$ Nice. I thought about golfing mine this way, but I didn't do it. Nevertheless, I'll try shifting; our answers will still be different. \$\endgroup\$ – 0WJYxW9FMN Jan 27 '17 at 21:10
  • 1
    \$\begingroup\$ Woah. Your new one is amazing. \$\endgroup\$ – 0WJYxW9FMN Jan 27 '17 at 21:17
  • 1
    \$\begingroup\$ The 26-byte version fails for 364, which is excluded from the test range. **.33359 works for one extra byte. \$\endgroup\$ – Dennis Jan 27 '17 at 21:33
  • \$\begingroup\$ @Dennis Thanks. Python exclusive ranges strike again! \$\endgroup\$ – xnor Jan 27 '17 at 21:34
  • 1
    \$\begingroup\$ lambda n:n**.3336//.5501 saves a few bytes. \$\endgroup\$ – Dennis Jan 27 '17 at 21:47
10
\$\begingroup\$

J, 12 bytes

2>.@-~3!inv]

There might be a golfier way to do this, but this is a lovely opportunity to use J's built-in function inversion.

Try it online!

How it works

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.
\$\endgroup\$
9
\$\begingroup\$

Python, 22 bytes

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

Heavily inspired by @xnor's Python answer.

Try it online!

\$\endgroup\$
7
\$\begingroup\$

Jelly, 7 bytes

R‘c3<¹S

Try it online!

How it works

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.
\$\endgroup\$
  • 2
    \$\begingroup\$ Sometimes I wonder, what can Jelly not do? \$\endgroup\$ – Sombrero Chicken Jan 28 '17 at 14:06
  • 1
    \$\begingroup\$ One of these days someone is going to be like "Code Golf a fully featured MMO" and Dennis is going to post "Jelly, 29 bytes" or something stupid like that. \$\endgroup\$ – corsiKa Jan 28 '17 at 21:47
6
\$\begingroup\$

JavaScript (ES6), 33 bytes

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

Based on the recursive formula:

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

The second expression can also be written as ...

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

... which is the one that we are using here.

a(i - 1) is actually stored in the k variable and passed to the next iteration until k >= n.

Test cases

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

\$\endgroup\$
  • \$\begingroup\$ This is sneakily short! Good job. \$\endgroup\$ – FlipTack Jan 27 '17 at 17:46
  • \$\begingroup\$ @FlipTack My first attempt was based on the formula you used. I had to change my plans. ;-) \$\endgroup\$ – Arnauld Jan 27 '17 at 17:47
6
\$\begingroup\$

Ruby, 26 bytes

Edit: alternate version, still 26 bytes

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

Original version

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

Uses the fact that T(x) = x(x+1)(x+2)/6 = ((x+1)**3-(x+1))/6 which is very close to (x+1)**3/6.

The function simply multiplies by 6, finds a slightly tweaked version of the cube root (yes 5 decimal places are required) and returns the result truncated to an integer.

Test program and output

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]
\$\endgroup\$
  • \$\begingroup\$ 0.3336 seems to work for the original version. (Edit: Never mind, Dennis points out I was forgetting about 364.) \$\endgroup\$ – xnor Jan 27 '17 at 21:31
5
\$\begingroup\$

JavaScript, 36 33 bytes

-3 bytes thanks to Luke (making the function curried)

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

This is an unnamed lambda function which can be assigned to func and called with func(220)(), as described in this meta post. My original, non-curried function looks like this:

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

This answer uses the fact that xth tetrahedral number can be found with the following function:

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

The submission works by recursively increasing i, and finding tetrahedral(i), until it's larger than or equal to n (the number of presents given).

When called with one argument as expected, i = undefined, and therefore is not larger than n. This means f(n,-~i) is executed, and -~undefined evaluates to 1, which sets off the recursion.


Test Snippet:

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

\$\endgroup\$
  • \$\begingroup\$ I was about to post the exact same answer. Beat me by 2 mins. Good job! \$\endgroup\$ – Luke Jan 27 '17 at 17:23
  • \$\begingroup\$ You can save 3 bytes by currying: n=>g=i=>n<=i/6*++i*++i?i-2:g(~-i). You'd call it like f(2)(). \$\endgroup\$ – Luke Jan 27 '17 at 18:17
  • \$\begingroup\$ @Luke good spot, my curried function wasn't so short. Are you sure you don't want to post that as your own answer? \$\endgroup\$ – FlipTack Jan 27 '17 at 18:24
  • \$\begingroup\$ Nah, I'd do it if we were using a different formula, but now our solutions are nearly identical. I'd rather help you get on the same level as Arnauld. ;-) \$\endgroup\$ – Luke Jan 27 '17 at 18:29
  • 3
    \$\begingroup\$ i=>n<=i Beautiful ;-) \$\endgroup\$ – ETHproductions Jan 27 '17 at 18:48
3
\$\begingroup\$

MATL, 12 11 bytes

`G@H+IXn>}@

Try it online!

Explanation

`       % 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)
\$\endgroup\$
2
\$\begingroup\$

05AB1E, 10 bytes

XµNÌ3c¹‹_½

Try it online!

Explanation

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
\$\endgroup\$
  • 1
    \$\begingroup\$ Wow, binom is much smarter than [N2Ý+P6÷¹Q#N>, nice one. \$\endgroup\$ – Magic Octopus Urn Jan 27 '17 at 19:18
2
\$\begingroup\$

Pyke, 11 bytes

#3RL+B6f)lt

Try it here!

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

Mathematica, 26 bytes

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

Unnamed function taking a nonnegative integer argument and returning a nonnegative integer (yeah, it works for day 0 too). We want to find the smallest integer i for which the input # is at most i(i+1)(i+2)/6, which is the formula for the number of gifts given on the first i days. Through mild algebraic trickery, the inequality # ≤ i(i+1)(i+2)/6 is equivalent to (i+1) + 6# ≤ (i+1)^3. So the structure 0//.i_/;i+6#>i^3:>i+1 starts with a 0 and keeps adding 1 as long as the test i+6#>i^3 is satisfied; then (...)-1& subtracts 1 at the end (rather than spend bytes with parentheses inside the inequality).

If we let the 12 Days of Christmas continue, we can handle about 65536 days before the built-in recursion limit for //. halts the process ... that's about 4.7 * 10^13 days, or about ten times the age of the universe thus far....

\$\endgroup\$
2
\$\begingroup\$

J, 9 bytes

I.~3!2+i.

Try it online!

This is more inefficient than using the inverse of factorial but happens to be shorter.

For example, if the input integer is n = 5, make the range [2, n+1].

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

These are the first 5 tetrahedral numbers. The next step is to determine which interval (day) n belongs to. There are n+1 = 6 intervals.

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

Then n = 5 belongs to interval 3 which is (4, 10] and the result is 3.

Explanation

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
\$\endgroup\$
2
\$\begingroup\$

Python, 43 bytes

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

Saved 5 bytes thanks to @FlipTack and another 3 thanks to @xnor!

\$\endgroup\$
  • \$\begingroup\$ This gives f(220)=11, which should be f(220)=10. \$\endgroup\$ – xnor Jan 27 '17 at 20:43
  • \$\begingroup\$ Oh, I was using Python 2. This needs Python 3 to avoid floor division, though perhaps you can multiply on the other side instead to make it version-agnostic. \$\endgroup\$ – xnor Jan 27 '17 at 20:47
  • \$\begingroup\$ I think you can do and-~f(n,i+1) for and f(n,i+1)or i. Strangely, it's usually shorter when you're counting up a variable recursively not to return it, but to instead increment the output recursively. \$\endgroup\$ – xnor Jan 27 '17 at 20:51
2
\$\begingroup\$

Japt, 12 bytes

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

Test it online! or Verify all test cases at once

How it works

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

This is a simplification of the tetrahedral formula several other answers are using:

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

By substituting x - 1 for x, we can simplify this considerably:

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

Therefore, the correct result is one less than the smallest integer x such that (x^3 - x) / 6 is greater than or equal to the input.

13-byte solution, inspired by @xnor's answer:

p.3335 /.55 f

A few more solutions @ETHproductions and I played around with

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

Test it here.

\$\endgroup\$
1
\$\begingroup\$

SmileBASIC, 43 bytes

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

I is the day, R is the ith triangular number, and P is the ith tetrahedral number (number of presents).

I think a similar answer in another language, perhaps: x=>{while(x>p)p+=r+=++i;return i} could be pretty good.

\$\endgroup\$
  • \$\begingroup\$ You want ?I at the end, don't you? \$\endgroup\$ – Nick Matteo Jan 27 '17 at 18:19
1
\$\begingroup\$

Python 3, 48 46 bytes

f=lambda x,i=1:f(x,i+1)if(i+3)*i+2<x/i*6else i
\$\endgroup\$
  • \$\begingroup\$ @FlipTack Argh! I'll fix it in a sec... nobody downvote, please. \$\endgroup\$ – 0WJYxW9FMN Jan 27 '17 at 17:44
  • 6
    \$\begingroup\$ You can prevent any downvoting by deleting your answer. You will then still be able to edit the answer and undelete it once it's fixed. \$\endgroup\$ – Laikoni Jan 27 '17 at 17:48
  • \$\begingroup\$ Also, this still doesn't do what the challenge asks. An input of 221 will crash it. \$\endgroup\$ – FlipTack Jan 27 '17 at 18:14
  • \$\begingroup\$ I've tested this on TIO and it crashes on all inputs. Is this my problem or is this happening to anyone else? \$\endgroup\$ – user63571 Jan 27 '17 at 19:14
  • \$\begingroup\$ It worked for me. I'll test it again. \$\endgroup\$ – 0WJYxW9FMN Jan 27 '17 at 21:02
1
\$\begingroup\$

Mathematica, 31 25 bytes

Floor@Root[x^3-x-6#+6,1]&
\$\endgroup\$
1
\$\begingroup\$

Haskell, 21 23 bytes

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

Edit: As xnor pointed out, the original solution (floor.(/0.82).(**0.4)) didn't work between the days of christmas

\$\endgroup\$
  • \$\begingroup\$ This gives the wrong answer on many inputs, for example 221. \$\endgroup\$ – xnor Jan 28 '17 at 22:32
0
\$\begingroup\$

Batch, 69 bytes

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

Manually calculates tetrahedronal numbers.

\$\endgroup\$
0
\$\begingroup\$

Pyth 11 bytes

/^Q.3335.55

Try it online!

pretty much just translated Dennis' answer into Pyth

\$\endgroup\$
0
\$\begingroup\$

R, 19 characters

floor((n*6)^.33359)

based on xnor's answer in Python.

\$\endgroup\$
0
\$\begingroup\$

QBIC, 19 bytes

This steals @xnor 's formula:

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

I tried dialing down the resolution to .3336 to save a byte, but that fails on the final testcase.

\$\endgroup\$
0
\$\begingroup\$

Bash + bc, 44 bytes

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.