Suma los poderes a n

14

Direcciones

Escriba un programa que, dado un entero de entrada n ( n >= 0), produzca el entero positivo más pequeño m donde:

  • n = a[1]^b[1] + a[2]^b[2] + a[3]^b[3] + ... + a[k]^b[k]
  • ay bson secuencias finitas de la misma longitud
  • todos los elementos de ason menores quem
  • todos los elementos de bson menores quem
  • todos los elementos de ason diferentes y enterosa[x] >= 0
  • todos los elementos de bson diferentes y enterosb[x] >= 0
  • a[x]y b[x]no son ambos 0 (ya que 0 ^ 0 es indeterminado)

Este es el , por lo que gana menos bytes.

Ejemplos

In 0 -> Out 1
Possible Sum: 

In 1 -> Out 2
Possible Sum: 1^0

In 2 -> Out 3
Possible Sum: 2^1

In 3 -> Out 3
Possible Sum: 2^1 + 1^0

In 6 -> Out 4
Possible Sum: 2^2 + 3^0 + 1^1

In 16 -> Out 5
Possible Sum: 2^4

In 17 -> Out 4
Possible Sum: 3^2 + 2^3

In 23 -> Out 6
Possible Sum: 5^1 + 3^0 + 2^4 + 1^3

In 24 -> Out 5
Possible Sum: 4^2 + 2^3

In 27 -> Out 4
Possible Sum: 3^3

In 330 -> Out 7
Possible Sum: 6^1 + 4^3 + 3^5 + 2^4 + 1^0
kukac67
fuente
¿Cómo se supone que hagamos una secuencia de enteros únicos y no negativos que tenga una suma no infinita?
fiesta
Además, el primer caso no tiene sentido porque una suma con 0 términos sería suficiente.
fiesta
@feersum No entiendo bien tu pregunta. Mi solución a esto es una búsqueda de fuerza bruta de todas las combinaciones donde m<2luego m<3, m<4etc., hasta que encuentre una suma que sea igual n. Además, pensé en tener la suma para 0no ser términos, pero ¿cuál es el resultado? m>?
kukac67
1
Para secuencias finitas, generalmente haría algo como n = a[1]^b[1] + a[2]^b[2] + ... + a[k]^b[k].
Volatilidad
1
Buena pregunta. Solo una objeción en el primer caso de prueba: ay bson secuencias finitas de longitud 0, por lo que no hay un número entero mque no satisfaga las restricciones, y dado que no hay un número entero más pequeño, la respuesta no está definida. Las posibles soluciones serían pedir el número natural más pequeño m(en cuyo caso debe cambiar la respuesta esperada allí 0) o el número entero positivo más pequeño m.
Peter Taylor

Respuestas:

2

GolfScript (59 caracteres)

~:T),{),.0{2$0-{2${{4$2$^}2*@3$\?4$+f~}%\;~}%+\;\;}:f~T&}?)

Demostración en línea

Esto utiliza la recursividad para enumerar los valores alcanzables para un determinado my busca el primero mque funciona. Está ligeramente inspirado por la respuesta de xnor pero es bastante diferente en la implementación.

Disección

~:T                  # Evaluate input and store in T (for Target)
),{                  # Search [0 1 ... T] for the first m which matches a predicate
  ),.0               #   Push [0 ... m] to the stack twice and then 0
                     #   Stack holds: possibleAs possibleBs sum
  {                  #   Define the recursive function f
    2$0-{            #     Map over A in possibleAs (except 0)
      2${            #       Map over B in possibleBs (except 0)
        {4$2$^}2*    #         Duplicate respective possibles and remove selected values
        @3$\?4$+     #         Compute sum' = sum + A^B
        f            #         Recursive call gives an array [sums]
        ~            #         Push the sums to the stack individually
        }%           #       End map: this collects the sums into a combined array
      \;             #       Pop A, leaving just the combined [sums] inside the map
      ~              #       Repeat the trick: push to the stack individually
    }%               #     End map, collecting into a combined array
                     #     Stack now holds: possibleAs possibleBs sum [sums]
    +                #     Include the original sum in the array of reachable sums
    \;\;             #     Pop possibleAs and possibleBs
  }:f                #   End function definition
  ~                  #   Evaluate the function
  T&                 #   Test whether the sums contain T
}?                   # End search
)                    # Increment to get m
Peter Taylor
fuente
6

Python, 120

f=lambda n,A,B:n*all(f(n-a**b,A-{a},B-{b})for a in A for b in B)
g=lambda n,m=1,M={0}:f(n,M-{0},M)and g(n,m+1,M|{m})or m

La función fes una función auxiliar que comprueba si npuede no ser expresada como una suma de potencias con bases distinto de Ay exponentes de B. Utiliza una estrategia recursiva natural: ndebe ser diferente de cero, e intentamos todas las opciones posibles de base y exponente y todos deben fallar. Los eliminamos de las listas permitidas y disminuimos nen la cantidad correspondiente.

La función g es la función principal. Busca un mque funcione. Mes el conjunto de valores permitidos hasta m-1. Eliminamos 0de los exponentes permitidos para detener 0**0(que Python evalúa a 1) de ser utilizado. Esto no duele nada porque 0**xes inútil 0para todos los demás x.

xnor
fuente
Probablemente podrías cambiar n and all()a n*all().
grc
@grc Ah, en realidad no necesitas el cortocircuito porque toca fondo. Gracias por la mejora
xnor
4

Python 2, 138 bytes

from itertools import*
S=lambda n,m=0,R=[]:m*any(n==sum(map(pow,*C))for k in R for C in product(*tee(permutations(R,k))))or S(n,m+1,R+[m])

(Gracias a @Jakube por todos los consejos)

Nunca he aprendido tanto sobre el itertoolsmódulo como lo he aprendido de esta pregunta. El último caso lleva aproximadamente un minuto.

Comenzamos buscando desde m = 1 e incrementando hasta obtener una solución. Para buscar una solución, iteramos sobre:

  • k = 0 to m-1, dónde k está el número de términos en la solución
  • Toda combinación posible de términos (al comprimir dos permutaciones de subconjuntos de [0, 1, ... m-1]tamañok ), luego sumando y verificando si tenemosn

Tenga en cuenta que iteramos khasta m-1: aunque técnicamente los mtérminos son posibles en total, siempre hay una solución con m-1términos que 0^0no están permitidos y0^b no contribuyen en nada. Esto es realmente importante porque 0^0Python lo trata como 1, lo que parece un problema, ¡pero resulta que no importa!

Este es el por qué.

Supongamos que una solución encontrada erróneamente usa 0^0como 1, por ejemplo 3^2 + 1^1 + 0^0 = 11. Dado que solo generamos hasta m-1términos, debe haber algunos jque no estamos usando como base (aquí j = 2). Podemos intercambiar la base 0 para jobtener una solución válida, aquí3^2 + 1^1 + 2^0 = 11 .

Si hubiéramos iterado en todos los mtérminos, entonces podríamos haber obtenido soluciones incorrectas como m = 2for n = 2, via 0^0 + 1^1 = 2.

Sp3000
fuente
Buena esa. Sin embargo, puede guardar 4 bytes utilizando imap. imap(pow,C,D) ... for C,D in
Jakube
@Jakube En realidad estoy buscando en el documento itertoolsmientras hablamos: PI ya tiene otro ahorro - tee.
Sp3000
Yo también. Además, mi error. ¿Por qué alguien sugeriría imap, cuando hay map? -1 byte
Jakube
El parámetro predeterminado para teeya es n=2. Guarda 2 bytes.
Jakube
@Jakube Ahaha gracias. Esta es probablemente la primera vez que lo he usado mapcon más de un iterable, y de hecho, esta pregunta me trae muchas novedades.
Sp3000
4

GolfScript ( 90 84 bytes)

[0.,.]](~:T),(+{:x;{:|2,{:c)|=x),^{c[1$x]=:A^x^:-;[|~-+@A-?+@A+@]}%}/+~}%.[]*T&}?)\;

Demostración en línea

Disección

[0.,.]             # Base case: [sum As Bs] is [0 [] []]
](~:T              # Collect it in an array of cases; fetch parameter, eval, store in T.
),(+               # Create array [1 2 ... T 0]. Putting 0 at the end means that it won't
                   # be reached except when T is 0, and nicely handles that special case.
{                  # Loop over the values from that array...
  :x;              #   ...assigning each in turn to x (and popping it from the stack)
  {                #   Stack holds array of [sum As Bs] cases; map them...

    :|             #     Store [sum As Bs] in |
    2,{:c          #     For c in [0 1]...
      )|=x),^      #       Get [0 1 ... x]^ either As or Bs, depending on c
      {            #       Map these legal new As or Bs respectively...
        c[1$x]=:A  #         Work out which of that value or x is the new A
        ^x^:-;     #         And the other one is the new B
        [          #         Begin gathering in an array
          |~       #           Push sum As Bs to the stack
          -+       #           Add - to Bs to get Bs'
          @A-?+    #           Rotate sum to top and add A^- to get sum'
          @A+      #           Rotate As to top and add A to get As'
          @        #           Final rotation to put elements in the right order
        ]          #         Gather in array [sum' As' Bs']
      }%           #       End map
    }/             #     End for
    +~             #     Push all the elements corresponding to x^B and A^x on to the stack
  }%               #   End map, collecting the untouched [sum As Bs] and all the new
                   #   [sum' As' Bs'] arrays into a new array of reached cases.
  .[]*T&           #   Flatten a copy of that array and filter to values equal to T.
                   #   This gives a truthy value iff we've found a way to make T.
}?                 # Loop until we get a truthy value, and push the corresponding x
)\;                # Increment to get the value of m and discard the array of cases

El truco más elegante es el manejo del estuche especial para 0.

Peter Taylor
fuente
Estoy muy feliz de que CJam esta vez no sea mucho más corto que el estándar python = P
flawr
@flawr, esto es GolfScript, no CJam. CJam probablemente puede ser un poco más corto porque tiene incorporado un producto cartesiano. Y podría ser que la idea de xnor de una función recursiva también proporcione GolfScript más corto.
Peter Taylor
Oh, lo siento, solo los confundí =)
error
4

Haskell, 143 130

import Data.List
p n=head$[1..]>>=(\m->[m|let x=permutations[0..m-1]>>=inits,a<-x,b<-x,sum(zipWith(\x y->x^y*signum(x+y))a b)==n])

Ejemplo de uso: p 23-> 6.

Esta es una simple búsqueda de fuerza bruta. Para cada lista, [0..0], [0..1], [0..2] ... [0..∞]tome todos los segmentos iniciales de las permutaciones (por ejemplo, [0..2]: permutaciones:, [012], [102], [210], [120], [201], [021]segmentos iniciales para la primera permutación:, [0], [01], [012]2da:, [1], [10], [102]etc.). Para cada combinación de 2 de esas listas, calcule la suma de poderes. Detente cuando el primero sea igual a n.

nimi
fuente
deberías usar en >>=lugar de concatMap. son iguales pero con los argumentos invertidos.
orgulloso Haskeller
@proudhaskeller: ¡Sí, gracias!
nimi
2

Python: 166 caracteres

from itertools import*;p=permutations
f=lambda n,r=[0]:any(n==sum(map(lambda x,y:(x+y>0)*x**y,a,b))for j in r for a,b in product(p(r,j),p(r,j)))*1or 1+f(n,r+[len(r)])

Explicación

La función fcrea todos los enteros posibles, que se pueden expresar como la suma de potencias de números en r. Si comienza con r = [0]. Si alguno de esos enteros es igual a n, devuelve la longitud de r, de lo contrario se llama recursivamente con un extendidor .

El cálculo de todos los enteros, que se puede expresar como suma, se realiza con dos bucles. El primer ciclo es el for j in r, que nos dice la longitud de la expresión (2 ^ 3 + 1 ^ 2 tiene longitud 2). El bucle interno itera sobre todas las combinaciones de permutaciones rde longitud j. Para cada uno calculo la suma de potencias.

Jakube
fuente
2

JavaScript (ES6) 219 224

Función recursiva. Comenzando con m = 1, intento todas las combinaciones de enteros 1..m para bases y 0..m para exponentes (0 base es inútil dado 0 ^ 0 == indefinido).
Si no se encuentra una solución, aumente m e intente nuevamente.
Caso especial para la entrada 0 (de todos modos, en mi opinión, es un error en las especificaciones)

La función C genera recursivamente todas las combinaciones de una matriz de longitud dada, de modo que

C(3, [1,2,3]) --> [[3,2,1], [3,1,2], [2,3,1], [2,1,3], [1,3,2], [1,2,3]]

El tercer nivel everyse usa para comprimir la matriz a de bases yb de exponentes (no hay zipfunción en JavaScript). Utilizando everypara detenerse temprano cuando hay una solución que no utiliza todos los elementos en las dos matrices.

F=(n,j=1,k=[],
  C=(l,a,o=[],P=(l,a,i=l)=>{
    for(l||o.push(a);i--;)
      e=[...a],P(l-1,e.concat(e.splice(i,1)))
  })=>P(l,a)||o
)=>n&&C(k.push(j++),k)[E='every'](a=>C(j,[0,...k])[E](b=>a[E](x=>t-=Math.pow(x,b.pop()),t=n)))
?F(n,j,k):j

Prueba en la consola FireFox / FireBug

;[0,1,2,3,6,16,17,23,24,27,330].map(x=>[x,F(x)])

Salida

[[0, 1], [1, 2], [2, 3], [3, 3], [6, 4], [16, 5], [17, 4], [23, 6], [ 24, 5], [27, 4], [330, 7]]

edc65
fuente