Welcher Weihnachtstag ist heute?

27

Vorwort

In dem bekannten Weihnachtslied The Twelve Days of Christmas werden dem Erzähler täglich mehrere Geschenke überreicht. Das Lied ist kumulativ - in jedem Vers wird ein neues Geschenk hinzugefügt, dessen Menge um eins höher ist als die des vorangegangenen Geschenks. Ein Rebhuhn, zwei Turteltauben, drei französische Hühner und so weiter.

In jedem Vers N können wir die kumulative Summe der bisher im Lied vorhandenen Geschenke berechnen, indem wir die N- te tetraedrische Zahl ermitteln , die die folgenden Ergebnisse liefert:

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

Zum Beispiel hatten wir nach Vers 4 4 * (1 Rebhuhn) , 3 * (2 Turteltauben) , 2 * (3 französische Hühner) und 1 * (4 rufende Vögel) . Wenn wir diese addieren, erhalten wir 4(1) + 3(2) + 2(3) + 1(4) = 20.

Die Herausforderung

Ihre Aufgabe ist es, ein Programm oder eine Funktion zu schreiben, die bei einer positiven Ganzzahl, die die Anzahl der Geschenke 364 ≥ p ≥ 1 darstellt , bestimmt, welcher Tag (Vers) von Weihnachten es ist.

Wenn zum Beispiel p = 286 ist , sind wir am 11. Weihnachtstag. Wenn jedoch p = 287 ist , dann hat die nächste Ladung Geschenke begonnen, was bedeutet, dass es der 12. Tag ist.

Mathematisch bedeutet dies, die nächste tetraedrische Zahl zu finden und ihre Position in der gesamten Folge der tetraedrischen Zahlen zurückzugeben.

Regeln:

  • Das ist , also gewinnt die kürzeste Lösung (in Bytes).
  • Es gelten Standard-Golflöcher.
  • Wenn es um Tage geht, muss Ihr Programm 1-indiziert sein.
  • Ihre Einreichung muss ein vollständiges Programm oder eine Funktion sein - aber kein Ausschnitt.

Testfälle

1   ->  1
5   ->  3
75  ->  7
100 ->  8
220 ->  10
221 ->  11
364 ->  12
FlipTack
quelle
5
Für den Fall, dass es jemandem hilft, ist die n-te tetraedrische Zahl auch die Summe der ersten n Dreieckszahlen.
DJMcMayhem
Dies könnte helfen: x=>{while(x>p)p+=r+=++i;return i}Ich bin sicher, dass es in einer Sprache wie JavaScript kürzer gemacht werden kann.
12. Mai,
1
Dies ist die früheste Weihnachtsherausforderung aller Zeiten, oder? :)
insertusernamehere

Antworten:

7

Gelee , 7 6 Bytes

-1 Byte dank Dennis (benutze vektorisiertes Minimum,, «und ersten Index, i)

R+\⁺«i

TryItOnline

Wie?

Nicht allzu effizient - berechnet die 1. bis n-te Tetraederzahl in einer Liste und gibt den auf 1 basierenden Index der ersten Zahl zurück, der gleich oder größer ist.

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)

Zurück 7 byters abgesenkten Bereich verwendet [0,1,2,3,...,n-1]und Zählen tetrahedrals weniger als n:
Ḷ+\⁺<µS,
Ḷ+\⁺<ḅ1,
Ḷ+\⁺<ċ1, und
Ḷ+\⁺<¹S

Jonathan Allan
quelle
19

Python , 27 Bytes

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

Probieren Sie es online!

Eine direkte Formel mit einer gewissen Kurvenanpassung, die der ursprünglichen von Level River St. entspricht.

Die verschobene Gleichung i**3-i==n*6ist i**3==n*6für große nahe i. Es löst sich auf i=(n*6)**(1/3). Nehmen Sie den Boden die Runden nach Bedarf herunter, um das Off-by-One zu kompensieren.

Es gibt jedoch 6 Eingaben an Grenzen, bei denen der Fehler unter einer Ganzzahl liegt, über der er liegen sollte. All dies kann durch leichtes Erhöhen des Exponenten behoben werden, ohne dass weitere Fehler auftreten.


Python , 38 Bytes

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

Die Formel n=i*(i+1)*(i+2)/6für tetraedrische Zahlen kann besser geschrieben werden i+1als n*6=(i+1)**3-(i+1). Also finden wir die niedrigsten ifür die i**3-i<n*6. Jedes Mal, wenn wir iab 1 inkrementieren , werden die rekursiven Aufrufe 1zur Ausgabe hinzugefügt. Ausgehend von, i=1anstatt i=0die Verschiebung zu kompensieren.

xnor
quelle
Nett. Ich dachte darüber nach, auf diese Weise Golf zu spielen, aber ich habe es nicht getan. Trotzdem werde ich versuchen zu wechseln; Unsere Antworten werden immer noch anders sein.
0WJYxW9FMN
1
Woah. Dein neues ist unglaublich.
0WJYxW9FMN
1
Die 26-Byte-Version schlägt für 364 fehl, was aus dem Testbereich ausgeschlossen ist. **.33359arbeitet für ein zusätzliches Byte.
Dennis
@ Tennis Danke. Python-Exklusivserien schlagen wieder zu!
Xnor
1
lambda n:n**.3336//.5501spart ein paar Bytes.
Dennis
10

J , 12 Bytes

2>.@-~3!inv]

Es gibt vielleicht eine bessere Möglichkeit, dies zu tun, aber dies ist eine wunderbare Gelegenheit, die in J integrierte Funktionsumkehrung zu verwenden.

Probieren Sie es online!

Wie es funktioniert

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
quelle
7

Gelee , 7 Bytes

R‘c3<¹S

Probieren Sie es online!

Wie es funktioniert

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
quelle
2
Manchmal frage ich mich, was kann Jelly nicht ?
Sombrero Chicken
1
Eines Tages wird jemand wie "Code Golf, ein MMO mit vollem Funktionsumfang" sein und Dennis wird "Jelly, 29 Bytes" oder so etwas Dummes posten.
CorsiKa
6

JavaScript (ES6), 33 Byte

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

Basierend auf der rekursiven Formel:

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

Der zweite Ausdruck kann auch geschrieben werden als ...

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

... das ist das, was wir hier verwenden.

a(i - 1)wird tatsächlich in der kVariablen gespeichert und an die nächste Iteration übergeben, bis k >= n.

Testfälle

Arnauld
quelle
Das ist schleichend kurz! Gut gemacht.
FlipTack
@FlipTack Mein erster Versuch basierte auf der von Ihnen verwendeten Formel. Ich musste meine Pläne ändern. ;-)
Arnauld
6

Ruby, 26 Bytes

Bearbeiten: alternative Version, noch 26 Bytes

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

Originalfassung

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

Nutzt die Tatsache, dass T(x) = x(x+1)(x+2)/6 = ((x+1)**3-(x+1))/6 was sehr nahe ist (x+1)**3/6.

Die Funktion multipliziert einfach mit 6, findet eine leicht überarbeitete Version der Kubikwurzel (ja, es sind 5 Dezimalstellen erforderlich) und gibt das Ergebnis abgeschnitten auf eine Ganzzahl zurück.

Testprogramm und Ausgabe

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
quelle
0.3336scheint für die original version zu funktionieren. (Edit:
Egal
5

JavaScript, 36 33 Bytes

-3 bytes dank luke

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

Dies ist eine unbenannte Lambda-Funktion, die zugewiesen funcund mit aufgerufen werden kann func(220)(), wie in diesem Meta-Beitrag beschrieben . Meine ursprüngliche Funktion ohne Curry sieht folgendermaßen aus:

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

Diese Antwort basiert auf der Tatsache, dass die x- te Tetraedernummer mit der folgenden Funktion gefunden werden kann:

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

Die Übermittlung funktioniert durch rekursives Erhöhen iund Finden tetrahedral(i), bis sie größer oder gleich istn (der Anzahl der gegebenen Geschenke) ist.

Wird wie erwartet mit einem Argument aufgerufen i = undefinedund ist daher nicht größer als n. Dies bedeutet, dass f(n,-~i)ausgeführt und -~undefinedausgewertet wird 1, wodurch die Rekursion ausgelöst wird.


Testschnipsel:

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
quelle
Ich wollte genau die gleiche Antwort posten. Schlagen Sie mich um 2 Minuten. Gut gemacht!
Luke
Sie können maximal 3 Bytes von currying sparen: n=>g=i=>n<=i/6*++i*++i?i-2:g(~-i). Du würdest es so nennen f(2)().
Luke
@ Luke guter Ort, meine Curry-Funktion war nicht so kurz. Bist du sicher, dass du das nicht als deine eigene Antwort posten möchtest?
FlipTack
Nein, ich würde es tun, wenn wir eine andere Formel verwenden würden, aber jetzt sind unsere Lösungen nahezu identisch. Ich würde dir lieber helfen, das gleiche Level wie Arnauld zu erreichen. ;-)
Luke
3
i=>n<=iSchön ;-)
ETHproductions
3

MATL , 12 11 Bytes

`G@H+IXn>}@

Probieren Sie es online!

Erläuterung

`       % 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
quelle
2

05AB1E , 10 Bytes

XµNÌ3c¹‹_½

Probieren Sie es online!

Erläuterung

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
quelle
1
Wow, binom ist viel schlauer als [N2Ý+P6÷¹Q#N>, nett.
Magic Octopus Urn
2

Pyke, 11 Bytes

#3RL+B6f)lt

Probieren Sie es hier aus!

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

Mathematica, 26 Bytes

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

Unbenannte Funktion, die ein nichtnegatives Ganzzahlargument verwendet und eine nichtnegative Ganzzahl zurückgibt (ja, es funktioniert auch für den Tag 0). Wir wollen die kleinste Ganzzahl finden, ifür die die Eingabe #höchstens i(i+1)(i+2)/6ist. Dies ist die Formel für die Anzahl der Geschenke, die an den ersten iTagen gegeben wurden. Durch leichte algebraische Täuschung ist die Ungleichung # ≤ i(i+1)(i+2)/6gleichbedeutend mit (i+1) + 6# ≤ (i+1)^3. Die Struktur 0//.i_/;i+6#>i^3:>i+1beginnt also mit a 0und fügt 1so lange hinzu, wie der Test i+6#>i^3erfüllt ist. (...)-1&subtrahiert dann 1am Ende (anstatt Bytes mit Klammern innerhalb der Ungleichung auszugeben).

Wenn wir die 12 Tage von Weihnachten weiterlaufen lassen, können wir ungefähr 65536 Tage verarbeiten, bevor die eingebaute Rekursionsgrenze //.den Prozess anhält ... das sind ungefähr 4,7 * 10 ^ 13 Tage oder ungefähr das Zehnfache des bisherigen Alters des Universums ....

Greg Martin
quelle
2

J 9 Bytes

I.~3!2+i.

Probieren Sie es online!

Dies ist ineffizienter als die Inverse der Fakultät, ist aber zufällig kürzer.

Wenn die Eingabe-Ganzzahl beispielsweise n = 5 ist, legen Sie den Bereich fest [2, n+1].

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

Dies sind die ersten 5 Tetraederzahlen. Der nächste Schritt besteht darin, festzustellen, zu welchem ​​Intervall (Tag) n gehört. Es gibt n + 1 = 6 Intervalle.

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

Dann gehört n = 5 zu Intervall 3 (4, 10]und das Ergebnis ist 3.

Erläuterung

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
Meilen
quelle
2

Python, 43 Bytes

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

5 Bytes dank @FlipTack und weitere 3 dank @xnor !

Loovjo
quelle
Das gibt f(220)=11, was soll sein f(220)=10.
27.
Oh, ich habe Python 2 verwendet. Dies erfordert Python 3, um eine Unterteilung der Ebenen zu vermeiden. Vielleicht können Sie aber auch auf der anderen Seite multiplizieren, um es versionsunabhängig zu machen.
27.
Ich glaube , Sie können tun and-~f(n,i+1)für and f(n,i+1)or i. Seltsamerweise ist es normalerweise kürzer, wenn Sie eine Variable rekursiv hochzählen, um sie nicht zurückzugeben, sondern die Ausgabe rekursiv zu erhöhen.
27.
2

Japt , 12 Bytes

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

Online testen! oder Überprüfen Sie alle Testfälle auf einmal

Wie es funktioniert

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

Dies ist eine Vereinfachung der Tetraederformel, die mehrere andere Antworten verwenden:

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

Durch den Ersatz x - 1von xkönnen wir dies erheblich vereinfachen:

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

Daher ist das richtige Ergebnis eins weniger als die kleinste Ganzzahl x, sodass sie (x^3 - x) / 6größer oder gleich der Eingabe ist.

13-Byte-Lösung, inspiriert von der Antwort von @ xnor :

p.3335 /.55 f

Noch ein paar Lösungen @ETHproductions und ich haben rumgespielt

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

Teste es hier .

Oliver
quelle
1

SmileBASIC, 43 Bytes

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

Iist der Tag, Rist die ith Dreieckszahl und Pist diei tetraedrische Zahl (Anzahl der Geschenke).

Ich denke, eine ähnliche Antwort in einer anderen Sprache x=>{while(x>p)p+=r+=++i;return i}könnte vielleicht ziemlich gut sein.

12Me21
quelle
Sie wollen ?Iam Ende, nicht wahr?
Nick Matteo
1

Python 3, 48 46 Bytes

f=lambda x,i=1:f(x,i+1)if(i+3)*i+2<x/i*6else i
0WJYxW9FMN
quelle
@FlipTack Argh! Ich werde es in einer Sekunde beheben ... niemand hat dagegen gestimmt, bitte.
0WJYxW9FMN
6
Sie können Abstimmungen verhindern, indem Sie Ihre Antwort löschen. Sie können die Antwort dann weiterhin bearbeiten und wiederherstellen, sobald sie behoben ist.
Laikoni
Auch dies tut immer noch nicht das, was die Herausforderung verlangt. Eine Eingabe von221 wird es zum Absturz bringen.
FlipTack
Ich habe dies mit TIO getestet und es stürzt bei allen Eingängen ab. Ist das mein Problem oder passiert das jemand anderem?
Es hat bei mir funktioniert. Ich werde es noch einmal testen.
0WJYxW9FMN
1

Mathematica, 31 25 Bytes

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

Haskell, 21 23 Bytes

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

Bearbeiten: Wie xnor betonte, funktionierte die ursprüngliche Lösung ( floor.(/0.82).(**0.4)) zwischen den Weihnachtstagen nicht

Joshua David
quelle
Dies gibt bei vielen Eingaben die falsche Antwort, zum Beispiel 221.
xnor
0

Batch, 69 Bytes

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

Berechnet manuell Tetraederzahlen.

Neil
quelle
0

R, 19 Zeichen

floor((n*6)^.33359)

basierend auf der Antwort von xnor in Python.

Mark Miller
quelle
0

QBIC , 19 Bytes

Dies stiehlt @xnors Formel:

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

Ich habe versucht, die Auflösung auf .3336 herunter zu wählen, um ein Byte zu speichern, aber das schlägt im letzten Testfall fehl.

steenbergh
quelle
0

Bash + Bc, 44 Bytes

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