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\$
6
  • 2
    \$\begingroup\$ This is a nicely written first challenge. However, I'd strongly advise to add a few test cases. \$\endgroup\$
    – Arnauld
    Aug 26, 2018 at 13:03
  • 1
    \$\begingroup\$ @Arnauld, ok working on it right now and thanks :) \$\endgroup\$
    – user82328
    Aug 26, 2018 at 13:06
  • \$\begingroup\$ OEIS A000537 \$\endgroup\$
    – JayCe
    Aug 26, 2018 at 13:10
  • \$\begingroup\$ Can you please explain how input 4183059834009 gives output 2022? \$\endgroup\$
    – DimChtz
    Aug 26, 2018 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\$ Aug 27, 2018 at 10:15

17 Answers 17

18
\$\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\$
3
  • \$\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\$
    – user82328
    Aug 31, 2018 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, 2018 at 17:31
  • \$\begingroup\$ Oh, in that case thnx for telling me :) \$\endgroup\$
    – user82328
    Aug 31, 2018 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\$
1
  • \$\begingroup\$ I have no idea why both 3mO and nO work... Probably also mention -1 is the falsy value. \$\endgroup\$ Aug 30, 2018 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\$
3
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\$
5
  • \$\begingroup\$ Is this valid ? since it can't handle input shown in test cases ? (I haven't got any idea) \$\endgroup\$
    – user82328
    Aug 26, 2018 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, 2018 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\$ Aug 26, 2018 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\$
    – user82328
    Aug 26, 2018 at 13:38
  • \$\begingroup\$ Too bad IJi behaves like ²⁼ (, in other words). \$\endgroup\$ Aug 26, 2018 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\$
2
  • \$\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, 2018 at 5:53
  • \$\begingroup\$ 26 bytes \$\endgroup\$
    – Jo King
    Aug 28, 2018 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\$
0
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\$
0
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\$
3
  • \$\begingroup\$ and/or or lists are usually shorter than if/else. 50 bytes \$\endgroup\$
    – Jo King
    Aug 27, 2018 at 6:07
  • \$\begingroup\$ @JoKing Thanks! I got two more bytes off also. \$\endgroup\$ Aug 28, 2018 at 4:53
  • \$\begingroup\$ not V => V==0 or V>-1 \$\endgroup\$
    – Jo King
    Aug 28, 2018 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