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]
a
yb
son secuencias finitas de la misma longitud- todos los elementos de
a
son menores quem
- todos los elementos de
b
son menores quem
- todos los elementos de
a
son diferentes y enterosa[x] >= 0
- todos los elementos de
b
son diferentes y enterosb[x] >= 0
a[x]
yb[x]
no son ambos 0 (ya que 0 ^ 0 es indeterminado)
Este es el código de golf , 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
code-golf
number
arithmetic
kukac67
fuente
fuente
m<2
luegom<3
,m<4
etc., hasta que encuentre una suma que sea igualn
. Además, pensé en tener la suma para0
no ser términos, pero ¿cuál es el resultado? m>?n = a[1]^b[1] + a[2]^b[2] + ... + a[k]^b[k]
.a
yb
son secuencias finitas de longitud0
, por lo que no hay un número enterom
que 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ñom
(en cuyo caso debe cambiar la respuesta esperada allí0
) o el número entero positivo más pequeñom
.Respuestas:
GolfScript (59 caracteres)
Demostración en línea
Esto utiliza la recursividad para enumerar los valores alcanzables para un determinado
m
y busca el primerom
que funciona. Está ligeramente inspirado por la respuesta de xnor pero es bastante diferente en la implementación.Disección
fuente
Python, 120
La función
f
es una función auxiliar que comprueba sin
puede no ser expresada como una suma de potencias con bases distinto deA
y exponentes deB
. Utiliza una estrategia recursiva natural:n
debe 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 disminuimosn
en la cantidad correspondiente.La función
g
es la función principal. Busca unm
que funcione.M
es el conjunto de valores permitidos hastam-1
. Eliminamos0
de los exponentes permitidos para detener0**0
(que Python evalúa a 1) de ser utilizado. Esto no duele nada porque0**x
es inútil0
para todos los demásx
.fuente
n and all()
an*all()
.Python 2, 138 bytes
(Gracias a @Jakube por todos los consejos)
Nunca he aprendido tanto sobre el
itertools
mó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óndek
está el número de términos en la solución[0, 1, ... m-1]
tamañok
), luego sumando y verificando si tenemosn
Tenga en cuenta que iteramos
k
hastam-1
: aunque técnicamente losm
términos son posibles en total, siempre hay una solución conm-1
términos que0^0
no están permitidos y0^b
no contribuyen en nada. Esto es realmente importante porque0^0
Python 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^0
como 1, por ejemplo3^2 + 1^1 + 0^0 = 11
. Dado que solo generamos hastam-1
términos, debe haber algunosj
que no estamos usando como base (aquíj = 2
). Podemos intercambiar la base 0 paraj
obtener una solución válida, aquí3^2 + 1^1 + 2^0 = 11
.Si hubiéramos iterado en todos los
m
términos, entonces podríamos haber obtenido soluciones incorrectas comom = 2
forn = 2
, via0^0 + 1^1 = 2
.fuente
imap(pow,C,D) ... for C,D in
itertools
mientras hablamos: PI ya tiene otro ahorro -tee
.imap
, cuando haymap
? -1 bytetee
ya esn=2
. Guarda 2 bytes.map
con más de un iterable, y de hecho, esta pregunta me trae muchas novedades.GolfScript (
9084 bytes)Demostración en línea
Disección
El truco más elegante es el manejo del estuche especial para
0
.fuente
Haskell,
143130Ejemplo 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.fuente
>>=
lugar deconcatMap
. son iguales pero con los argumentos invertidos.Python: 166 caracteres
Explicación
La función
f
crea todos los enteros posibles, que se pueden expresar como la suma de potencias de números enr
. Si comienza conr = [0]
. Si alguno de esos enteros es igual an
, devuelve la longitud der
, 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 permutacionesr
de longitudj
. Para cada uno calculo la suma de potencias.fuente
JavaScript (ES6) 219
224Funció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
El tercer nivel
every
se usa para comprimir la matriz a de bases yb de exponentes (no hayzip
función en JavaScript). Utilizandoevery
para detenerse temprano cuando hay una solución que no utiliza todos los elementos en las dos matrices.Prueba en la consola FireFox / FireBug
Salida
fuente