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\$
3
  • 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, 2017 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, 2017 at 18:09
  • 2
    \$\begingroup\$ This is the earliest Christmas challenge ever, right? :) \$\endgroup\$ Jan 29, 2017 at 19:29

27 Answers 27

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\$
11
  • \$\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, 2017 at 21:10
  • 1
    \$\begingroup\$ Woah. Your new one is amazing. \$\endgroup\$
    – 0WJYxW9FMN
    Jan 27, 2017 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, 2017 at 21:33
  • \$\begingroup\$ @Dennis Thanks. Python exclusive ranges strike again! \$\endgroup\$
    – xnor
    Jan 27, 2017 at 21:34
  • 1
    \$\begingroup\$ lambda n:n**.3336//.5501 saves a few bytes. \$\endgroup\$
    – Dennis
    Jan 27, 2017 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 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\$
0
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
  • 2
    \$\begingroup\$ Sometimes I wonder, what can Jelly not do? \$\endgroup\$ Jan 28, 2017 at 14:06
  • 2
    \$\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, 2017 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\$
2
  • \$\begingroup\$ This is sneakily short! Good job. \$\endgroup\$
    – FlipTack
    Jan 27, 2017 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, 2017 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\$
1
  • \$\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, 2017 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) = \frac{x}6(x+1)(x+2)\$

The function 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\$
5
  • \$\begingroup\$ I was about to post the exact same answer. Beat me by 2 mins. Good job! \$\endgroup\$
    – Luke
    Jan 27, 2017 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, 2017 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, 2017 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, 2017 at 18:29
  • 3
    \$\begingroup\$ i=>n<=i Beautiful ;-) \$\endgroup\$ Jan 27, 2017 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
  • 1
    \$\begingroup\$ Wow, binom is much smarter than [N2Ý+P6÷¹Q#N>, nice one. \$\endgroup\$ Jan 27, 2017 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\$
0
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\$
3
  • \$\begingroup\$ This gives f(220)=11, which should be f(220)=10. \$\endgroup\$
    – xnor
    Jan 27, 2017 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, 2017 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, 2017 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\$
0
2
\$\begingroup\$

APL (Dyalog Classic), 8 bytes

+\⍣2∘⍳⍳⊢

My first time using APL, thanks to H.PWiz for shortening it into a train

Essentially a port of the Jelly answer

Explanation

+\⍣2∘⍳⍳⊢
    ∘⍳    Numbers from 1 to input inclusive
+\        Cumulative reduce with addition, gets triangular numbers
  ⍣2      Repeat (does it again) to get the tetrahedral numbers
      ⍳⊢  Index of the input in that list

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ Unfortunately I don't think this is a valid solution as it fails for p = 221. It will only work for values of p that are exactly tetrahedral numbers \$\endgroup\$
    – Jarmex
    May 12, 2020 at 1:36
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\$
1
  • \$\begingroup\$ You want ?I at the end, don't you? \$\endgroup\$ Jan 27, 2017 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\$
7
  • \$\begingroup\$ @FlipTack Argh! I'll fix it in a sec... nobody downvote, please. \$\endgroup\$
    – 0WJYxW9FMN
    Jan 27, 2017 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, 2017 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, 2017 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, 2017 at 19:14
  • \$\begingroup\$ It worked for me. I'll test it again. \$\endgroup\$
    – 0WJYxW9FMN
    Jan 27, 2017 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\$
1
  • \$\begingroup\$ This gives the wrong answer on many inputs, for example 221. \$\endgroup\$
    – xnor
    Jan 28, 2017 at 22:32
1
\$\begingroup\$

Itr, 11 bytes

#äµS¹µS>S1+

online interpreter

Explanation

#            ; read a number `n`  from standard input
 ä           ; duplicate that number
  µ          ; apply for all integers in the range [1,...,n]
   S         ; replace each element `k` of the range with the sum from 1 to `k`
    ¹        ; push all no-empty prefixes of that list
     µS      ; sum up the elements, this will give the list of the first `n` tetrahedral numbers
       >     ; vectorized comparison
        S    ; sum up, this will count the number of triangle numbers that are smaller than `n`
         1+  ; offset by one to get the right number
\$\endgroup\$
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\$
0
\$\begingroup\$

Husk, 6 bytes

V≥¹∫∫ḣ

Try it online! or Verify all test cases

Explanation

V≥¹∫∫ḣ
     ḣ range 1..n
   ∫∫  cumulative sum, twice
V      index of first element that is
 ≥¹    greater than or equal to the input 
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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