20
\$\begingroup\$

task

Your task is to build a structure with \$n\$ cubes. The volume of cubes follow the following sequence (bottom -> top)

\$n^3, (n-1)^3, (n-2)^3,...,1^3\$

input

The total volume of the structure (\$V\$).

output

value of (\$n\$), i.e : The total number of cubes.

\$V = n^3 + (n-1)^3 + .... + 1^3\$

notes

  • Input will always be an integer.
  • Sometimes it isn't possible to follow the sequence, i.e : \$V\$ doesn't represent a specific value for \$n\$. In that event return -1, or a falsy value of your choosing (consistency is required though).
  • This is so shortest answer in bytes for each language wins.
  • No answer will be marked accepted for the above mentioned reason.

requests

  • This is my first challenge on the site so bear with me, and forgive (and tell me about) any mistakes that I made.
  • Kindly provide a link so your code can be tested.
  • If you can, kindly write an explanation on how your code works, so others can understand and appreciate your work.

examples

input  : 4183059834009
output : 2022

input  : 2391239120391902
output : -1

input  : 40539911473216
output : 3568

Thanks to @Arnauld for the link to this :

Isn't that nice.

Link to orignial : Link

\$\endgroup\$
  • 2
    \$\begingroup\$ This is a nicely written first challenge. However, I'd strongly advise to add a few test cases. \$\endgroup\$ – Arnauld Aug 26 '18 at 13:03
  • 1
    \$\begingroup\$ @Arnauld, ok working on it right now and thanks :) \$\endgroup\$ – Any3nymous user Aug 26 '18 at 13:06
  • \$\begingroup\$ OEIS A000537 \$\endgroup\$ – JayCe Aug 26 '18 at 13:10
  • \$\begingroup\$ Can you please explain how input 4183059834009 gives output 2022? \$\endgroup\$ – DimChtz Aug 26 '18 at 13:10
  • 2
    \$\begingroup\$ @SuperJedi224 AFAIK the default rule is "whatever range the natural integer type of your language has", of course without using a small range for a loophole -- at least that's what I assumed in my answer :o \$\endgroup\$ – Felix Palmen Aug 27 '18 at 10:15

17 Answers 17

19
\$\begingroup\$

JavaScript (ES7), 31 bytes

A direct formula. Returns 0 if there's no solution.

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

Try it online!

How?

The sum \$S_n\$ of the first \$n\$ cubes is given by:

$$S_n = \left(\frac{n(n+1)}{2}\right)^2 = \left(\frac{n^2+n}{2}\right)^2$$

(This is A000537. This formula can easily be proved by induction. Here is a nice graphical representation of \$S_5\$.)

Reciprocally, if \$v\$ is the sum of the first \$x\$ cubes, the following equation admits a positive, integer solution:

$$\left(\frac{x^2+x}{2}\right)^2=v$$

Because \$(x^2+x)/2\$ is positive, this leads to:

$$x^2+x-2\sqrt{v}=0$$

Whose positive solution is given by:

$$\Delta=1+8\sqrt{v}\\ x=\frac{-1+\sqrt{\Delta}}{2} $$

If \$r=\sqrt{\Delta}\$ is an integer, it is guaranteed to be an odd one, because \$\Delta\$ itself is odd. Therefore, the solution can be expressed as:

$$x=\left\lfloor\frac{r}{2}\right\rfloor$$

Commented

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)

Recursive version, 36 35 bytes

Returns NaN if there's no solution.

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

Try it online!

Commented

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
\$\endgroup\$
  • \$\begingroup\$ Hi, I created an answer (to my own question) link, since you published first I wanted to ask is it ok to publish twice in same language ? \$\endgroup\$ – Any3nymous user Aug 31 '18 at 11:41
  • \$\begingroup\$ @Any3nymoususer Posting several answers in the same language is perfectly fine. Answering its own challenge should not be done before a couple of days, but I guess that's now OK. \$\endgroup\$ – Arnauld Aug 31 '18 at 17:31
  • \$\begingroup\$ Oh, in that case thnx for telling me :) \$\endgroup\$ – Any3nymous user Aug 31 '18 at 17:41
7
\$\begingroup\$

05AB1E, 6 bytes

ÝÝOnIk

Try it online!

Port of Jonathan's Jelly answer. Take the cumulative sum of [0 ... n], square each and find the index of V.


05AB1E, 7 bytes

ÝÝ3mOIk

Try it online!

How it works

ÝÝ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.

8-byte alternative: ÝÝÅΔ3mOQ.

\$\endgroup\$
  • \$\begingroup\$ I have no idea why both 3mO and nO work... Probably also mention -1 is the falsy value. \$\endgroup\$ – Magic Octopus Urn Aug 30 '18 at 16:46
6
\$\begingroup\$

R, 42 40 bytes

-2 bytes thanks to Giuseppe

function(v,n=((1+8*v^.5)^.5-1)/2)n*!n%%1

Try it online!

Port of Arnauld's JavaScript answer. Also returns 0 if there's no solution.

\$\endgroup\$
5
\$\begingroup\$

Jelly,  5  4 bytes

RIJi

A monadic link, yields 0 if not possible.

Try it online! way too inefficient for the test cases! (O(V) space :p)

Here is an 8-byte version that performs a cube-root of V first to make it O(V^(1/3)) instead. Using that 8-byte version here is a test-suite

How?

$$\sum_{i=1}^{i=n}i^3=\left(\sum_{i=1}^{i=n}i\right)^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)
\$\endgroup\$
  • \$\begingroup\$ Is this valid ? since it can't handle input shown in test cases ? (I haven't got any idea) \$\endgroup\$ – Any3nymous user Aug 26 '18 at 13:26
  • 1
    \$\begingroup\$ It is valid, it's just the range that gives a memory error for those test cases. Try smaller values like 36 \$\endgroup\$ – Mr. Xcoder Aug 26 '18 at 13:27
  • 1
    \$\begingroup\$ @FiveCrayFish973 yes, it's quite normal to sacrifice usability/efficiency/etc for byte-count in code-golf (unless the spec enforces some limits). See the 9-byte version for one that works for your test cases. \$\endgroup\$ – Jonathan Allan Aug 26 '18 at 13:37
  • \$\begingroup\$ @JonathanAllan cool, I wasn't aware on what the rules of this community suggest. If it's valid, it's valid. Cheers \$\endgroup\$ – Any3nymous user Aug 26 '18 at 13:38
  • \$\begingroup\$ Too bad IJi behaves like ²⁼ (, in other words). \$\endgroup\$ – Erik the Outgolfer Aug 26 '18 at 17:57
4
\$\begingroup\$

Elixir, 53 bytes

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

Try it online!

Port of Jonathan's Jelly answer.


Elixir, 74 bytes

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

Try it online!

Definitely sub-optimal. But I am just an Elixir newbie! :) Returns nil for "invalid" values of V.

\$\endgroup\$
3
\$\begingroup\$

Japt, 7 bytes

o³å+ bU

Try it


Explanation

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

Alternative

Çõ³xÃbU

Try it

\$\endgroup\$
3
\$\begingroup\$

Cubix, 27 bytes (or volume 27?)

Seems like the right place for this language.

I@.1OW30pWpP<s)s;;q\.>s-.?/

Try it online!

This wraps onto a 3x3x3 cube as follows

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

Watch it run

It essential brute forces by taking increasing cubes away from the input. If it results in zero, output n otherwise if there is a negative result, print 0 and exit.

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

Perl 6, 30 29 26 bytes

-4 bytes thanks to Jo King

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

Try it online!

Brute-force solution for n < 10000. Uses the equation from Jonathan Allan's answer. 37 36 bytes solution for larger n (-1 byte thanks to Jo King):

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

Try it online!

Returns False if there's no solution.

Explanation

               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
\$\endgroup\$
  • \$\begingroup\$ For the brute force, you could do 0..$_ to be valid for all numbers, even if it will time out on larger ones. For normal golfing, you can remove the . from the first one and change the second from 0>=* to 1>* \$\endgroup\$ – Jo King Aug 27 '18 at 5:53
  • \$\begingroup\$ 26 bytes \$\endgroup\$ – Jo King Aug 28 '18 at 5:55
2
\$\begingroup\$

JavaScript (Node.js), 28 bytes

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

Try it online!

I know it's my own question and all, but I had a better answer (for this lang) then is present, so I posted. Hope it's ok

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

APL (Dyalog), 18 bytes

{o×⍵≥o←⍵⍳⍨+\3*⍨⍳⍵}

Try it online!

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

Matlab, 27 bytes

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

Returns the n if exists or an empty matrix if not.

How it works

            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

Try it Online!

Note It fails for large v due to memory limitations.

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

Python 3, 60 bytes

lambda V:[*[(n*-~n/2)**2for n in range(V+1)],V].index(V)%-~V

Try it online!

-6 thanks to Mr. Xcoder.

If we can throw an error in case there's no \$n\$ for a particular \$V\$, we can get this down to 51 bytes:

lambda V:[(n*-~n/2)**2for n in range(V+1)].index(V)

Try it online!

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

Perl 6, 33 bytes

{$!+>1 if ($!=sqrt 1+8*.sqrt)%%1}

Try it online!

This uses Arnauld's method. Returns an Empty object if the number is not valid.

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

dc, 19 bytes

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

Input and output is from the stack, returns 0 if no solution.

Try it online!

Explanation

If there's a solution n, the input is ((n^2+n)^2)/4. So we'll calculate a trial solution as n=sqrt(sqrt(4*input)), using dc's default 0 decimal place precision for square roots, then compare (n^2+n)^2 to 4*input to see if it's actually a 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

The penultimate line relies on the non-obvious fact that to dc, 0^x=0 for all nonzero x (even negative x!) but 0^0=1.

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

Python 3, 53 48 bytes

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

Try it online!

-3 bytes from Jo King

Returns -1 for no answer.

Only works up to n=997 with the default recursion limits.

Repeatedly takes bigger and bigger cubes from the volume until it arrives at zero (success, return number of cubes removed), or a negative number (no answer).

Explanation:

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
\$\endgroup\$
  • \$\begingroup\$ and/or or lists are usually shorter than if/else. 50 bytes \$\endgroup\$ – Jo King Aug 27 '18 at 6:07
  • \$\begingroup\$ @JoKing Thanks! I got two more bytes off also. \$\endgroup\$ – pizzapants184 Aug 28 '18 at 4:53
  • \$\begingroup\$ not V => V==0 or V>-1 \$\endgroup\$ – Jo King Aug 28 '18 at 5:33
0
\$\begingroup\$

gvm (commit 2612106) bytecode, 70 59 bytes

(-11 bytes by multiplying in a loop instead of writing the code for multiplying twice)

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

Test runs:

> 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

Not really a low score, just using this nice question for testing gvm here ;) The commit is older than the question of course. Note this is an 8bit virtual machine, so using some code handling only the natural unsigned number range 0-255, the test cases given in the question won't work.

Manually assembled from this:

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: I just fixed a bug in gvm; without this fix, gvm tried to read binary programs in text mode, which might break (code above doesn't contain any 0xd bytes so won't break on windows without this fix).

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

K (oK), 21 bytes

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

Try it online!

Port of Arnauld's JS answer.

How:

{(,_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.

the function will return (_r%2) iff 1!r == 0, else it returns null (0N). That is due to the single element in the list having index 0, and trying to index that list with any number other than 0 will return null.

\$\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.