Producto de dígitos

10

Para un número entero positivo dado N, escriba un programa completo para encontrar la M natural mínima de manera que el producto de los dígitos de M sea igual a N. N es menor que 1,000,000,000. Si no existe M, imprima -1. Su código no debería tomar más de 10 segundos para cualquier caso.

Sample Inputs
1
3
15
10 
123456789
32
432
1296

Sample Outputs
1
3
35
25
-1
48
689
2899
fR0DDY
fuente
44
1dar 1es un caso de prueba importante.
Peter Taylor
1
Debería agregar casos más complejos, como los tres que he usado a continuación: 32, 432, 1296. A menos que lo deje como un ejercicio para el codificador.
mellamokb
@ s-mark 26, eh. Número más pequeño
fR0DDY
Creo que también deberíamos probar los obvios 387420489 (9 ^ 9) y 1000000000 por diversión.
asoundmove
2
Debido a que esta es una pregunta antigua y el OP está inactivo, esto es solo una nota para publicaciones futuras: "10 segundos" no está claro de acuerdo con el estándar actual (¿en qué máquina?)
usuario202729

Respuestas:

4

Golfscript, 45 43 40 caracteres

~9{{1$1$%!{\1$/1$}*}12*(}8*>{];-1}*]$1or

Reemplaza la versión que no agrupaba pequeños números primos en poderes y guarda 8 caracteres al hacerlo. Nota: 12 = piso (9 log 10 / log 5).

Agradecimientos: dos personajes salvados al robar un truco de @mellamokb; 3 guardados con una pista de @Nabb.

Peter Taylor
fuente
1
¡Qué! ¿Puedes escribir Golfscript sin probarlo? +1, se ve bien, excepto 123456789, lleva más de 1 minuto en mi máquina y he cancelado el proceso. 12345dame -1, por lo que podría funcionar 123456789también si pudiera esperar el tiempo suficiente.
USTED
@ S.Mark, gracias. Parece que no puedo salir con el ingenuo algoritmo de factorización.
Peter Taylor
@ Peter: da respuestas incorrectas para casos más complejos. 32 -> 22222, debería ser 48. 432 -> 2222333, debería ser 689. 1296 -> 22223333, debería ser 2899. etc.
mellamokb
@mellamokb, buen punto. Creo que tendré que reescribir y probar.
Peter Taylor
Wow, 17 caracteres menos. Necesito un mejor algoritmo, jajaja!
mellamokb
6

Javascript ( 84 78 76 74 72 70 68)

n=prompt(m="");for(i=9;i-1;)n%i?i--:(m=i+m,n/=i);alert(n-1?-1:m?m:1)

http://jsfiddle.net/D3WgU/7/

Editar: idea de entrada / salida prestada de otra solución y lógica de salida más corta.

Edición 2: guardado 2 caracteres al eliminar llaves innecesarias en el forbucle.

Edición 3: Guardado 2 caracteres reescribiendo el whilebucle como una ifdeclaración con i++.

Edición 4: Guarde 2 caracteres moviéndose y reduciendo las operaciones i.

Edición 5: Convierta la declaración if en formato ternario ahorrando 2 caracteres más.

Edición 6: guarde 2 caracteres moviéndose i--a la parte verdadera de ternary, elimine ++i.

mellamokb
fuente
Has contado caracteres solo para la función. ¿Es este un programa completo? ¿Puedes ejecutarlo aquí ideone.com
FR0DDY
1
parece que hay una entrada similar para javascript con spidermonkey en ideone que vinculó - ideone.com/samples#sample_lang_112
USTED
@ fR0DDY: OK, ahora es un programa completo :)
mellamokb
Finalmente reduje el mío a 69 caracteres, pero ahora puedes hacerlo también con el mismo tipo de idea y esa promptcosa.
Ry-
m?m:1=>m||1
l4m2
4

JavaScript, 88 72 78 74 69 68

for (s = '', i = 2, m = n = prompt (); i <m; i ++) while (! (n% i)) {if (i> 9) {alert (-1); E ( )} n / = i; s + = i} alerta (s)
4 caracteres más largos, pero en realidad un script ejecutable (a diferencia de una función).

Editar: Usando ideas del otro JavaScript, puedo reducirlo a esto:

for(s='',i=9,n=prompt();i>1;i--)for(;!(n%i);n/=i)s=i+s;alert(n-1?-1:s?s:1)

¡Finalmente! Una solución de 69 caracteres, solo usa 1 para loop;)

for(s='',i=9,n=prompt();i>1;n%i?i--:[n/=i,s=i+s]);alert(n-1?-1:s?s:1)

De acuerdo, afeitado una coma.

for(i=9,n=prompt(s='');i>1;n%i?i--:[n/=i,s=i+s]);alert(n-1?-1:s?s:1)
Ry-
fuente
Mismo problema que la solución GolfScript. Falla en las entradas 32, 432 y 1296. Hay una razón por la cual comienzo en 9 y retrocedo, y concateno desde la derecha en lugar de la izquierda.
mellamokb
También falla para la entrada 1. Tiene que hacer un caso especial para manejar 1.
mellamokb
Me perdí la parte "mínima", cambió.
Ry-
@minitech: todavía no funciona para la entrada '1'. jajaja, nuestras respuestas son casi idénticas :-)
mellamokb
¡Ah, conseguí hacerlo 2 caracteres más corto que el tuyo! : D
Ry-
4

awk ( 63 61 59 58 57)

{for(i=9;i>1;$1%i?i--:($1/=i)<o=i o);print 1<$1?-1:o?o:1}
asoundmove
fuente
Estamos llamando al programa solo para una entrada. Se dan múltiples entradas solo para verificar la corrección.
fR0DDY
3

Perl (75) (72)

$ d = shift; mapa {$ m = $ _. $ m, $ d / = $ _ hasta $ d% $ _} reverso 2..9; imprimir $ d-1? -1: $ m || 1

inspirado en el código javascript de mellamokb; destinado a ejecutarse con un parámetro

perl chino goth
fuente
¿No sería más corto si usara stdin en lugar de un parámetro?
asoundmove
3

GolfScript ( 60 57)

~[{9,{)}%{\.@%!},)\;.@@/.9>2$1>&}do])[.])@@{1>},+\9>[-1]@if$

~{9,{)}%{\.@%!},)\;.@@/.9>2$1>&}do])[.])@@{1>},+$\9>-1@if

Editar

Ok, creo que esta versión da la salida correcta para cada caso ahora :-)

Editar 2

Afeitado 3 caracteres por sugerencias de @ Peter.

mellamokb
fuente
La razón por la que comenté anteriormente que 1dar 1es un caso de prueba importante es que es un caso especial desagradable, el único número para el que 1aparece el dígito en la salida. Y me temo que rompe tu código.
Peter Taylor
También se rompe para números divisibles por números primos mayores que 9.
Peter Taylor
@ Peter: OK, inténtalo de nuevo. Creo que esta versión funciona para todos los casos de prueba ahora.
mellamokb
Parece que sí. Puedes guardar un personaje de inmediato quitándolo primero [; si no tienes un [en la pila cuando evalúas un ], toma todo en la pila. Y probablemente pueda guardar dos caracteres cerca del final al no envolverlos -1en una matriz y mover el final $.
Peter Taylor
@ Peter: Gracias, ¡ahorré 3 caracteres más!
mellamokb
3

Haskell

f n=head([m|m<-[1..10^9],product(map(read.return)$show m)==n]++[-1])
Ming-Tang
fuente
Afeita un carbón cambiando (show m)a $show m.
FUZxxl
1
no debería ser m<-[1..9^9]... de lo contrario es una lista infinita ... así -1que nunca ocurrirá ... corrígeme si me equivoco.
st0le
No creo que pueda funcionar en 10 segundos ...
st0le
2

Windows PowerShell, 87

if(($n="$args")-le1){$n;exit}(-1,-join(9..2|%{for(;!($n%$_)){$_;$n/=$_}}|sort))[$n-eq1]
Joey
fuente
2

Perl (68)

$x=pop;map{$_-=11;$x/=$_,$@=-$_.$@until$x%$_}1..9;print!$x?-1:$@||1

Se parece al igual que el truco impresionante que @mellamokb usos en javascript para evitar el bucle anidado se traduciría bien en Perl pero sale mucho más detallado porque no se puede utilizar el foreachbucle de estilo por más tiempo. También es una lástima que Perl no piense mapque un bucle redosería útil.

Jasvir
fuente
2

Scala 106 caracteres:

def p(n:Int,l:Int=9):List[Int]=if(n<=9)List(n)else
if(l<2)List(-1)else
if(n%l==0)l::p(n/l,l)else
p(n,l-1)

Prueba e invocación:

scala> val big=9*9*9*8*8*8*7*7*7*5*3 
big: Int = 1920360960

scala> p(big)                        
res1: List[Int] = List(9, 9, 9, 8, 8, 8, 7, 7, 7, 5, 3)

Tiempo de respuesta: inmediatamente, <1s en CPU de 2Ghz.

usuario desconocido
fuente
2

Jalea , 18 13 10 bytes

×⁵RDP$€io-

Pruébalo en línea!

Solución de 13 bytes:

×⁵RDP$€iµ’¹¬?

Pruébalo en línea!

Explicación con entrada N:

׳R              create a range from 1 to N * 100 (replace ³ with ⁵ for a faster execution time)
   DP$           define a function ($) to get the product of the digits of a number,
      €          apply that function to each element in the list,
       iµ        get the index of the input N in the list (or 0 if it's not there), and yeild it as the input to the next link,
         ’¹¬?    conditional: if the answer is 0, then subtract one to make it -1, otherwise, yeild the answer

Solución de 18 bytes:

D×/
×⁵RÇ€i
Ç⁾-1¹¬?

Pruébalo en línea!

D×/        product of digits function, takes input M
D          split M into digits,
 ×/        reduce by multiplication (return product of digits)

×⁵RÇ€i     range / index function
×⁵R        make a range from 1 to N*10,
   ǀ      run the above function on each of the range elements,
     i     get the index of N in the result, or 0 if it's not there

Ç⁾-1¹¬?    main function:
Ç    ¬?    run the line above and check if the answer is null (0)
 ⁾-1       if it is, return "-1",
    ¹      otherwise, return the answer (identity function).

El último enlace es solo para reemplazar 0 (el valor de falsey predeterminado de Jelly, ya que todas las listas tienen un índice) con -1. Si considera que 0 es un valor correcto de falsey, el programa es de 8 bytes .

Harry
fuente
1
Algunas notas: (1) usa cada enlace auxiliar solo una vez, por lo que no hay razón para hacer un enlace auxiliar. Solo usa el $ƊƲµ. (2) Como la cadena -1y el número -1son idénticos cuando salen, el uso del número ahorra 2 bytes. (3) Pes la abreviatura de ×/. (4) Falla en la entrada 3125.
user202729
@ user202729 ¡Muchas gracias! ¡Implementé (1), (2) y (3) y ahorraron 6 bytes! Si cambié ⁵ a ³, funcionó en la entrada 3125 pero solo después de un retraso considerable. ¿Sabes si hay una manera mejor (y más corta), o si mi enfoque (que sé que definitivamente no es el más rápido en términos de complejidad temporal) es tan bueno como será?
Harry
1
Creo que _¬$debería funcionar’¹¬?
dylnan
1
o-Es aún más corto.
user202729
@dylnan Gracias, ¡me di cuenta de que debido a µque podía usar sin el $que ahorró 2 bytes! ¡Pero luego me di cuenta de o-que podía omitirlo por µcompleto y ahorrar 3 bytes!
Harry
1

Rubí (100)

n=gets.to_i;(d=1..9).map{|l|[*d].repeated_combination(l){|a|a.reduce(:*)==n&&(puts a*'';exit)}};p -1
Lars Haugseth
fuente
0

Python 2 , 89 bytes

f=lambda n,a=0,u=1,i=9:n<2and(a or 1)or-(i<2)or n%i<1and f(n/i,a+i*u,u*10)or f(n,a,u,i-1)

Pruébalo en línea!

Solo porque todavía no hay una respuesta de Python. Es realmente doloroso no tener una conversión de tipo implícita entre string e int.

Bubbler
fuente