¿Cuántos cubos se pueden construir?

20

tarea

Su tarea es construir una estructura con n cubos. El volumen de cubos sigue la siguiente secuencia (abajo -> arriba)

n3,(n1)3,(n2)3,...,13

entrada

El volumen total de la estructura ( V ).

salida

valor de ( n ), es decir: el número total de cubos.

V=n3+(n1)3+....+13

notas

  • La entrada siempre será un número entero.
  • A veces no es posible seguir la secuencia, es decir: no representa un valor específico para n . En ese caso, devuelva -1 o un valor falso de su elección (aunque se requiere coherencia).Vn
  • Este es el por lo que la respuesta más corta en bytes para cada idioma gana.
  • Ninguna respuesta se marcará como aceptada por el motivo mencionado anteriormente.

peticiones

  • Este es mi primer desafío en el sitio, así que tengan paciencia conmigo y perdonen (y cuéntenme) los errores que cometí.
  • Proporcione amablemente un enlace para que su código pueda ser probado.
  • Si puede, escriba amablemente una explicación sobre cómo funciona su código, para que otros puedan entender y apreciar su trabajo.

ejemplos

input  : 4183059834009
output : 2022

input  : 2391239120391902
output : -1

input  : 40539911473216
output : 3568

Gracias a @Arnauld por el enlace a esto:

¿No es lindo?

Enlace a original: enlace

Usuario Any3nymous
fuente
2
Este es un primer desafío bien escrito. Sin embargo, recomiendo agregar algunos casos de prueba.
Arnauld
1
@Arnauld, estoy trabajando en ello ahora mismo y gracias :)
Usuario de Any3nymous
OEIS A000537
JayCe
¿Puede explicar cómo la entrada 4183059834009da salida 2022?
DimChtz
2
@ SuperJedi224 AFAIK la regla predeterminada es "cualquier rango que tenga el tipo entero natural de su idioma", por supuesto, sin usar un rango pequeño para una escapatoria, al menos eso es lo que asumí en mi respuesta: o
Felix Palmen

Respuestas:

19

JavaScript (ES7), 31 bytes

Una fórmula directa. Devuelve 0si no hay solución.

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

Pruébalo en línea!

¿Cómo?

La suma de los primeros n cubos viene dada por:Snn

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

(Esto es A000537 . Esta fórmula se puede probar fácilmente por inducción. Aquí hay una buena representación gráfica de ).S5

Recíprocamente, si es la suma de los primeros x cubos, la siguiente ecuación admite una solución entera positiva:vX

(x2+x2)2=v

Como es positivo, esto lleva a:(x2+x)/2

x2+x2v=0

Cuya solución positiva está dada por:

Δ=1+8vx=1+Δ2

Si es un número entero, se garantiza que es impar, porqueΔ ensí es impar. Por lo tanto, la solución se puede expresar como:r=ΔΔ

x=r2

Comentado

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)

Versión recursiva, 36 35 bytes

Devuelve NaNsi no hay solución.

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

Pruébalo en línea!

Comentado

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
fuente
Hola, creé un enlace de respuesta (a mi propia pregunta) , ya que publicaste primero quería preguntar ¿está bien publicar dos veces en el mismo idioma?
Usuario de Any3nymous
@ Any3nymoususer Publicar varias respuestas en el mismo idioma está perfectamente bien. Responder a su propio desafío no debe hacerse antes de un par de días, pero supongo que ahora está bien.
Arnauld
Oh, en ese caso gracias por decirme :)
Usuario de Any3nymous
7

05AB1E , 6 bytes

ÝÝOnIk

Pruébalo en línea!

Port of Jonathan's Jelly respuesta. Tome la suma acumulada de [0 ... n] , cuadrado cada uno y encontrar el índice de V .


05AB1E , 7 bytes

ÝÝ3mOIk

Pruébalo en línea!

Cómo funciona

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

Alternativa de 8 bytes: ÝÝÅΔ3mOQ.

Sr. Xcoder
fuente
No tengo idea de por qué tanto 3mOy nOtrabajo ... Probablemente también mencione -1 es el valor falso.
Urna de pulpo mágico
5

Jalea ,  5  4 bytes

RIJi

Un enlace monádico, rinde 0si no es posible.

Pruébalo en línea! Demasiado ineficiente para los casos de prueba! (O (V) espacio: p)

Aquí hay una versión de 8 bytes que realiza una raíz cúbica de V primero para convertirla en O (V ^ (1/3)). El uso de esa versión de 8 bytes aquí es un conjunto de pruebas

¿Cómo?

yo=1yo=norteyo3=(yo=1yo=norteyo)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
fuente
¿Es esto válido? ya que no puede manejar la entrada que se muestra en los casos de prueba? (No tengo idea)
Usuario de Any3nymous
1
Es válido, es solo el rango que da un error de memoria para esos casos de prueba. Pruebe valores más pequeños como36
Sr. Xcoder
1
@ FiveCrayFish973 sí, es bastante normal sacrificar usabilidad / eficiencia / etc. por el conteo de bytes en el código de golf (a menos que la especificación imponga algunos límites). Vea la versión de 9 bytes para una que funcione para sus casos de prueba.
Jonathan Allan
@JonathanAllan genial, no estaba al tanto de lo que sugieren las reglas de esta comunidad. Si es válido, es válido. Saludos
Usuario Any3nymous
Lástima que se IJicomporte como ²⁼( en otras palabras).
Erik the Outgolfer
4

Elixir , 53 bytes

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

Pruébalo en línea!

La respuesta de Port of Jonathan's Jelly.


Elixir , 74 bytes

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

Pruébalo en línea!

Definitivamente subóptimo. ¡Pero solo soy un novato en Elixir! :) Devuelve los nilvalores "no válidos" de V.

Sr. Xcoder
fuente
3

Japt, 7 bytes

o³å+ bU

Intentalo


Explicación

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

Alternativa

Çõ³xÃbU

Intentalo

Lanudo
fuente
3

Cubix , 27 bytes (o volumen 27?)

Parece el lugar correcto para este idioma.

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

Pruébalo en línea!

Esto se envuelve en un cubo 3x3x3 de la siguiente manera

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

Míralo correr

Es esencial las fuerzas brutas al quitar cubos crecientes de la entrada. Si resulta en cero n, imprima lo contrario si hay un resultado negativo, imprima 0 y salga.

MickyT
fuente
2

Perl 6 , 30 29 26 bytes

-4 bytes gracias a Jo King

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

Pruébalo en línea!

Solución de fuerza bruta para n <10000. Utiliza la ecuación de la respuesta de Jonathan Allan. 37 Solución de 36 bytes para n más grande ( -1 byte gracias a Jo King ):

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

Pruébalo en línea!

Devoluciones Falsesi no hay solución.

Explicación

               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
fuente
Para la fuerza bruta, podría 0..$_ser válido para todos los números, incluso si se agota el tiempo en los más grandes. Para jugar al golf normal, puede eliminar el .primero y cambiar el segundo de 0>=*a1>*
Jo King
26 bytes
Jo King
2

JavaScript (Node.js) , 28 bytes

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

Pruébalo en línea!

Sé que es mi propia pregunta y todo eso, pero tenía una mejor respuesta (para este idioma) que está presente, así que publiqué. Espero que esté bien

Usuario Any3nymous
fuente
1

Matlab, 27 bytes

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

Devuelve el nif existe o una matriz vacía si no.

Cómo funciona

            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

Pruébalo en línea!

Nota Falla en grande vdebido a limitaciones de memoria.

DimChtz
fuente
1

Python 3 , 60 bytes

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

Pruébalo en línea!

-6 gracias al Sr. Xcoder .

Si podemos lanzar un error en caso de que no haya norte para un particular V, podemos reducir esto a 51 bytes:

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

Pruébalo en línea!

Erik el Outgolfer
fuente
1

dc , 19 bytes

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

La entrada y salida es de la pila, devuelve 0 si no hay solución.

Pruébalo en línea!

Explicación

Si hay una solución n, la entrada es ((n^2+n)^2)/4. Así que vamos a calcular una solución de prueba que n=sqrt(sqrt(4*input)), utilizando por defecto 0 decimal de precisión de corriente continua para las raíces cuadradas, a continuación, comparar (n^2+n)^2a 4*inputver si es realmente una solución.

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

La penúltima línea se basa en el hecho no obvio de que dc, 0^x=0para todos los que no sean cero x(¡incluso negativos x!) Pero 0^0=1.

Sophia Lechner
fuente
1

Python 3 , 53 48 bytes

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

Pruébalo en línea!

-3 bytes de Jo King

Devoluciones -1 sin respuesta.

Solo funciona hasta n=997 con los límites de recursión predeterminados.

Repetidamente toma cubos cada vez más grandes del volumen hasta que llega a cero (éxito, se devuelve el número de cubos eliminados) o un número negativo (sin respuesta).

Explicación:

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
fuente
and/oro las listas son generalmente más cortas que if/else. 50 bytes
Jo King
@JoKing ¡Gracias! Tengo dos bytes más de descuento también.
pizzapants184
not V=> V==0oV>-1
Jo King
0

gvm (commit 2612106 ) bytecode, 70 59 bytes

(-11 bytes multiplicando en un bucle en lugar de escribir el código para multiplicar dos veces)

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

Pruebas de funcionamiento:

> 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

Realmente no es un puntaje bajo, solo uso esta buena pregunta para probar gvmaquí;) El commit es más antiguo que la pregunta, por supuesto. Tenga en cuenta que esta es una máquina virtual de 8 bits, por lo que el uso de algunos códigos maneja solo el rango de números natural sin signo0-255 , los casos de prueba dados en la pregunta no funcionarán.

Ensamblado manualmente de esto:

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

editar : acabo de corregir un error en gvm; sin esta solución, gvmintenté leer programas binarios en modo de texto , lo que podría romperse (el código anterior no contiene 0xdbytes, por lo que no se romperá en Windows sin esta solución).

Felix Palmen
fuente
0

K (oK) , 21 bytes

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

Pruébalo en línea!

La respuesta JS del puerto de Arnauld .

Cómo:

{(,_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 función devolverá (_r%2)iff 1!r == 0, de lo contrario, devuelve null ( 0N). Esto se debe a que el elemento único en la lista tiene índice 0, e intentar indexar esa lista con cualquier número que no sea 0 devolverá nulo.

J. Sallé
fuente