Combien de cubes peuvent être construits

20

tâche

Votre tâche consiste à construire une structure avec cubes. Le volume des cubes suit la séquence suivante (en bas -> en haut)n

n3,(n−1)3,(n−2)3,...,13

contribution

Le volume total de la structure ( ).V

production

valeur de ( ), c'est-à-dire: le nombre total de cubes.n

V=n3+(n-1)3+....+13

Remarques

  • L'entrée sera toujours un entier.
  • Parfois, il n'est pas possible de suivre la séquence, c'est-à-dire que: ne représente pas une valeur spécifique pour . Dans ce cas, retournez -1, ou une valeur fausse de votre choix (la cohérence est cependant requise).nVn
  • C'est le code-golf donc la réponse la plus courte en octets pour chaque langue gagne.
  • Aucune réponse ne sera marquée comme acceptée pour la raison susmentionnée.

demandes

  • C'est mon premier défi sur le site, alors soyez indulgent avec moi et pardonnez (et parlez-moi) des erreurs que j'ai faites.
  • Veuillez fournir un lien pour que votre code puisse être testé.
  • Si vous le pouvez, veuillez écrire une explication sur le fonctionnement de votre code, afin que les autres puissent comprendre et apprécier votre travail.

exemples

input  : 4183059834009
output : 2022

input  : 2391239120391902
output : -1

input  : 40539911473216
output : 3568

Merci à @Arnauld pour le lien vers ceci:

N'est-ce pas agréable.

Lien vers l'original: Lien

code-golf math Utilisateur Any3nymous
la source
2
Ceci est un premier défi joliment écrit. Cependant, je vous conseille fortement d'ajouter quelques cas de test.
Arnauld
1
@Arnauld, ok travailler dessus maintenant et merci :)
Utilisateur Any3nymous
OEIS A000537
JayCe
Pouvez-vous expliquer comment l'entrée 4183059834009donne la sortie 2022?
DimChtz
2
@ SuperJedi224 AFAIK, la règle par défaut est "quelle que soit la plage du type entier naturel de votre langue", bien sûr sans utiliser une petite plage pour une échappatoire - du moins c'est ce que j'ai supposé dans ma réponse: o
Felix Palmen

Réponses:

19

JavaScript (ES7), 31 octets

Une formule directe. Retourne 0s'il n'y a pas de solution.

v=>(r=(1+8*v**.5)**.5)%1?0:r>>1

Essayez-le en ligne!

Comment?

La somme de la première n cubes est donnée par:Snn

Sn=(n(n+1)2)2=(n2+n2)2

(Ceci est A000537 . Cette formule peut facilement être prouvée par induction. Voici une belle représentation graphique de )S5

Réciproquement, si est la somme des x premiers cubes, l'équation suivante admet une solution entière positive:vX

(X2+X2)2=v

Parce que est positif, cela conduit à:(X2+X)/2

X2+X-2v=0

Dont la solution positive est donnée par:

Δ=1+8vX=-1+Δ2

Si est un entier, il est garanti qu'il est impair, carΔlui-même est impair. Par conséquent, la solution peut être exprimée comme suit:r=ΔΔ

X=⌊r2⌋

Commenté

v =>                    // v = input
  ( r =                 //
    (1 + 8 * v ** .5)   // delta = 1 + 8.sqrt(v)
    ** .5               // r = sqrt(delta)
  ) % 1 ?               // if r is not an integer:
    0                   //   return 0
  :                     // else:
    r >> 1              //   return floor(r / 2)

Version récursive, 36 35 octets

Retourne NaNs'il n'y a pas de solution.

f=(v,k=1)=>v>0?1+f(v-k**3,k+1):0/!v

Essayez-le en ligne!

Commenté

f = (v,                   // v = input
        k = 1) =>         // k = current value to cube
  v > 0 ?                 // if v is still positive:
    1 +                   //   add 1 to the final result
    f(                    //   do a recursive call with:
      v - k ** 3,         //     the current cube subtracted from v
      k + 1               //     the next value to cube
    )                     //   end of recursive call
  :                       // else:
    0 / !v                //   add either 0/1 = 0 if v is zero, or 0/0 = NaN if v is
                          //   non-zero (i.e. negative); NaN will propagate all the
                          //   way to the final output
Arnauld
la source
Bonjour, j'ai créé un lien de réponse (à ma propre question) , puisque vous avez publié en premier, je voulais vous demander est-ce que je peux publier deux fois dans la même langue?
Utilisateur Any3nymous
@ Any3nymoususer Publier plusieurs réponses dans la même langue est parfaitement bien. Répondre à son propre défi ne devrait pas se faire avant quelques jours, mais je suppose que c'est maintenant OK.
Arnauld
Oh, dans ce cas, merci de me le dire :)
Utilisateur Any3nymous
7

05AB1E , 6 octets

ÝÝOnIk

Essayez-le en ligne!

Réponse de Port of Jonathan's Jelly. Prendre la somme cumulée de [0 ... n] , carré chacune et l'indice de V .

05AB1E , 7 octets

ÝÝ3mOIk

Essayez-le en ligne!

Comment ça fonctionne

ÝÝ3mOIk – Full program.
ÝÝ      – Yield [[0], [0, 1], [0, 1, 2], ... [0, 1, 2, ... V]].
  3mO   – Raise to the 3rd power.
     Ik – And find the index of the input therein. Outputs -1 if not found.

Variante 8-octets: ÝÝÅΔ3mOQ.

M. Xcoder
la source
Je n'ai aucune idée pourquoi les deux 3mOet le nOtravail ... Probablement mentionner également -1 est la valeur falsifiée.
Urne de poulpe magique
5

Gelée ,  5  4 octets

RIJi

Un lien monadique, cède 0sinon impossible.

Essayez-le en ligne! trop inefficace pour les cas de test! (Espace O (V): p)

Voici une version à 8 octets qui effectue d'abord une racine cubique de V pour la rendre O (V ^ (1/3)) à la place. En utilisant cette version à 8 octets, voici une suite de tests

Comment?

∑je=1je=nje3=(∑je=1je=nje)2
RIJi - Link: integer, V
R    - range of v -> [1,2,3,...,V]
 Ä   - cumulative sums -> [1,3,6,...,(1+2+3+...+V)]
  ²  - square -> [1,9,36,...,(1+2+3++...+V)²] ( =[1³,1³+2³,1³+2³+3³,...,(1³+2³+3³+...+V³)] )
   i - first 1-based index of v? (0 if not found)
Jonathan Allan
la source
Est-ce valable? car il ne peut pas gérer l'entrée affichée dans les cas de test? (Je n'ai aucune idée)
Utilisateur Any3nymous
1
C'est valide, c'est juste la plage qui donne une erreur de mémoire pour ces cas de test. Essayez des valeurs plus petites comme36
M. Xcoder
1
@ FiveCrayFish973 oui, il est tout à fait normal de sacrifier l'utilisabilité / l'efficacité / etc. pour le nombre d'octets dans le code-golf (sauf si la spécification impose certaines limites). Voir la version 9 octets pour celle qui fonctionne pour vos cas de test.
Jonathan Allan
@JonathanAllan cool, je ne savais pas ce que les règles de cette communauté suggèrent. Si c'est valide, c'est valide. Cheers
Utilisateur Any3nymous
Dommage IJise comporte comme ²⁼( Ị, en d'autres termes).
Erik the Outgolfer
4

Elixir , 53 octets

&Enum.find_index 0..&1,fn n->&1*4==n*n*(n+1)*(n+1)end

Essayez-le en ligne!

Réponse de Port of Jonathan's Jelly.

Elixir , 74 octets

fn v->Enum.find_index 0..v,&v==Enum.sum Enum.map(0..&1,fn u->u*u*u end)end

Essayez-le en ligne!

Certainement sous-optimal. Mais je ne suis qu'un débutant en Elixir! :) Renvoie les nilvaleurs "invalides" de V.

M. Xcoder
la source
3

Japt, 7 octets

o³å+ bU

Essayez-le

Explication

            :Implicit input of integer U
o           :Range [0,U)
 ³          :Cube each
  å+        :Cumulatively reduce by addition
     bU     :0-based index of U

Alternative

Çõ³xÃbU

Essayez-le

Hirsute
la source
3

Cubix , 27 octets (ou volume 27?)

Semble comme le bon endroit pour cette langue.

[email protected]<s)s;;q\.>s-.?/

Essayez-le en ligne!

Cela encapsule sur un cube 3x3x3 comme suit

      I @ .
      1 O W
      3 0 p
W p P < s ) s ; ; q \ .
> s - . ? / . . . . . .
. . . . . . . . . . . .
      . . .
      . . .
      . . .

Regardez-le courir

Il force les forces brutes essentielles en éloignant les cubes de l'entrée. S'il aboutit à zéro, sortez nsinon s'il y a un résultat négatif, imprimez 0 et quittez.

MickyT
la source
2

Perl 6 , 30 29 26 octets

-4 octets grâce à Jo King

{first :k,.sqrt,[\+] ^1e4}

Essayez-le en ligne!

Solution de force brute pour n <10000. Utilise l'équation de la réponse de Jonathan Allan. 37 Solution de 36 octets pour un n plus grand ( -1 octet grâce à Jo King ):

{!.[*-1]&&$_-2}o{{$_,*-$++³...1>*}}

Essayez-le en ligne!

Retourne Falses'il n'y a pas de solution.

Explication

               o  # Combination of two anonymous Blocks
                {                 }  # 1st Block
                 {               }   # Reset anonymous state variable $
                  $_,*-$++³...1>*    # Sequence n,n,n-1³,n-1³-2³,... while positive
{             }  # 2nd Block
 !.[*-1]&&       # Return False if last element is non-zero
          $_-2   # Return length of sequence minus two otherwise
nwellnhof
la source
Pour la force brute, vous pouvez faire 0..$_pour être valide pour tous les nombres, même si cela expire sur les plus grands. Pour le golf normal, vous pouvez retirer le .de la première et de changer la seconde de 0>=*la1>*
Jo Roi
26 octets
Jo King
2

JavaScript (Node.js) , 28 octets

a=>a**.5%1?0:(2*a**.5)**.5|0

Essayez-le en ligne!

Je sais que c'est ma propre question et tout, mais j'ai eu une meilleure réponse (pour cette langue) puis est présent, alors j'ai posté. J'espère que ça va

Utilisateur Any3nymous
la source
1

Matlab, 27 octets

@(v)find(cumsum(1:v).^2==v)

Renvoie le nsi existe ou une matrice vide sinon.

Comment ça fonctionne

            1:v            % Creates a 1xV matrix with values [1..V]
     cumsum(   )           % Cumulative sum
                .^2        % Power of 2 for each matrix element
                   ==v     % Returns a 1xV matrix with ones where equal to V
find(                 )    % Returns a base-1 index of the first non-zero element

Essayez-le en ligne!

Remarque Il échoue pour les grands en vraison de limitations de mémoire.

DimChtz
la source
1

dc , 19 octets

4*dvvdddk*+d*-0r^K*

L'entrée et la sortie proviennent de la pile, renvoie 0 si aucune solution.

Essayez-le en ligne!

Explication

S'il y a une solution n, l'entrée est ((n^2+n)^2)/4. Nous allons calculer une solution d'essai comme n=sqrt(sqrt(4*input)), en utilisant par défaut dc 0 la précision décimale pour les racines carrées, puis de comparer (n^2+n)^2à 4*inputvoir si elle est en fait une solution.

4*dvv         Calculate a trial solution n (making a copy of 4*input for later use)
dddk          Store the trial solution in the precision and make a couple copies of it
*+d*          Calculate (n^2+n)^2
-             Subtract from our saved copy of 4*input - now we have 0 iff n is a solution
0r^           Raise 0 to that power - we now have 1 if n is a solution, 0 if not
K*            Multiply by our saved trial solution

L'avant-dernière ligne s'appuie sur le fait non évident que dc, 0^x=0pour tout non nul x(même négatif x!) Mais 0^0=1.

Sophia Lechner
la source
1

Python 3 , 53 48 octets

f=lambda V,n=1:V>0and f(V-n**3,n+1)or(not V)*n-1

Essayez-le en ligne!

-3 octets de Jo King

Retourne -1sans réponse.

Fonctionne uniquement n=997avec les limites de récursivité par défaut.

Prend à plusieurs reprises des cubes de plus en plus gros du volume jusqu'à ce qu'il arrive à zéro (succès, retour du nombre de cubes supprimés), ou un nombre négatif (pas de réponse).

Explication:

f=lambda V,n=1: # f is a recursive lambda taking the volume and the cube size (defaulting to 1)

               V>0and               # if the volume is positive
                      f(V-n**3,n+1) # then we are not to the right cube size yet, try again with n+1, removing the volume of the nth cube

                                   or # if V is not positive
                                     (not V)*n-1
                         # case V == 0:
                         # (not V)*n == n; return n-1, the number of cubes
                         # case V < 0:
                         # (not V)*n == 0; return -1, no answer
pizzapants184
la source
and/orou les listes sont généralement plus courtes que if/else. 50 octets
Jo King
@JoKing Merci! J'ai également obtenu deux octets de plus.
pizzapants184
not V=> V==0ouV>-1
Jo King
0

gvm (commit 2612106 ) bytecode, 70 59 octets

(-11 octets en multipliant dans une boucle au lieu d'écrire le code pour multiplier deux fois)

Hexdump:

> hexdump -C cubes.bin
00000000  e1 0a 00 10 00 1a 03 d3  8a 00 f6 2a fe 25 c8 d3  |...........*.%..|
00000010  20 02 2a 04 0a 01 1a 02  00 00 20 08 4a 01 fc 03  | .*....... .J...|
00000020  d1 6a 02 52 02 cb f8 f4  82 04 f4 e8 d1 6a 03 0a  |.j.R.........j..|
00000030  03 fc d5 a8 ff c0 1a 00  a2 00 c0                 |...........|
0000003b

Essais:

> echo 0 | ./gvm cubes.bin
0
> echo 1 | ./gvm cubes.bin
1
> echo 2 | ./gvm cubes.bin
-1
> echo 8 | ./gvm cubes.bin
-1
> echo 9 | ./gvm cubes.bin
2
> echo 224 | ./gvm cubes.bin
-1
> echo 225 | ./gvm cubes.bin
5

Pas vraiment un faible score, juste utiliser cette belle question pour tester gvmici;) Le commit est plus ancien que la question bien sûr. Notez qu'il s'agit d'une machine virtuelle 8 bits, donc en utilisant du code ne gérant que la plage de nombres naturels non signés 0-255, les cas de test donnés dans la question ne fonctionneront pas.

Assemblé manuellement à partir de ceci:

0100  e1         rud                     ; read unsigned decimal
0101  0a 00      sta     $00             ; store to $00 (target sum to reach)
0103  10 00      ldx     #$00            ; start searching with n = #0
0105  1a 03      stx     $03             ; store to $03 (current cube sum)
0107  d3         txa                     ; X to A
                   loop:
0108  8a 00      cmp     $00             ; compare with target sum
010a  f6 2a      beq     result          ; equal -> print result
010c  fe 25      bcs     error           ; larger -> no solution, print -1
010e  c8         inx                     ; increment n
010f  d3         txa                     ; as first factor for power
0110  20 02      ldy     #$02            ; multiply #02 times for ...
0112  2a 04      sty     $04             ; ... power (count in $04)
                   ploop:
0114  0a 01      sta     $01             ; store first factor to $01 ...
0116  1a 02      stx     $02             ; ... and second to $02 for multiplying
0118  00 00      lda     #$00            ; init product to #0
011a  20 08      ldy     #$08            ; loop over 8 bits
                   mloop1:
011c  4a 01      lsr     $01             ; shift right first factor
011e  fc 03      bcc     noadd1          ; shifted bit 0 -> skip adding
0120  d1         clc                     ; 
0121  6a 02      adc     $02             ; add second factor to product
                   noadd1:
0123  52 02      asl     $02             ; shift left second factor
0125  cb         dey                     ; next bit
0126  f8 f4      bpl     mloop1          ; more bits -> repeat
0128  82 04      dec     $04             ; dec "multiply counter" for power
012a  f4 e8      bne     ploop           ; not 0 yet -> multiply again
012c  d1         clc
012d  6a 03      adc     $03             ; add power to ...
012f  0a 03      sta     $03             ; ... current cube sum
0131  fc d5      bcc     loop            ; repeat unless adding overflowed
                   error:
0133  a8 ff      wsd     #$ff            ; write signed #$ff (-1)
0135  c0         hlt                     ; 
                   result:
0136  1a 00      stx     $00             ; store current n to $00
0138  a2 00      wud     $00             ; write $00 as unsigned decimal
013a  c0         hlt

edit : je viens de corriger un bug dans gvm; sans ce correctif, a gvmessayé de lire les programmes binaires en mode texte , ce qui pourrait casser (le code ci-dessus ne contient aucun 0xdoctet donc ne se cassera pas sur les fenêtres sans ce correctif).

Felix Palmen
la source
0

K (oK) , 21 octets

{(,_r%2)@1!r:%1+8*%x}

Essayez-le en ligne!

Réponse de Port of Arnauld JS .

Comment:

{(,_r%2)@1!r:%1+8*%x} # Main function, argument x
             %1+8*%x  # sqrt(1+(8*(sqrt(x)))
           r:         # Assign to r
         1!           # r modulo 1
        @             # index the list:
 (,_r%2)              # enlist (,) the floor (_) of r modulo 2.

la fonction retournera (_r%2)ssi 1!r == 0, sinon elle retournera null ( 0N). Cela est dû au fait que l'élément unique de la liste a l'index 0, et essayer d'indexer cette liste avec un nombre différent de 0 retournera null.

J. Sallé
la source