Factoring factoriales

16

¡Hoy en mi clase de estadísticas, descubrí que algunos factoriales se pueden simplificar cuando se multiplican! Por ejemplo:5! * 3! = 5! *3*2 = 5! *6 = 6!

Tu trabajo:

Dada una cadena que contiene solo números arábigos y signos de exclamación, simplifique mi factorial a su cadena más corta posible, en la menor cantidad de bytes para su idioma, código de estilo de golf.

Entrada

Una cadena que contiene solo números arábigos y signos de exclamación. ¡Los factoriales para la entrada no serán mayores que 200 !. Los factoriales no tendrán más de un factorial por número. La entrada puede tomarse como una lista de enteros.

Salida

Una cadena posiblemente acortada, que tiene el valor equivalente en la entrada. El orden no es importante. La notación factorial es imprescindible, pero no es necesario que use más de un símbolo factorial por número.

Casos de prueba

In: 3!2!2!  
Out: 4! 

In 2!3!2!0! 
Out: 4! 

In: 7!2!2!7!2!2!2!2! 
Out: 8!8! 

In: 23!3!2!2! 
Out: 24!  
Also: 4!!

In: 23!3!2!2!2! 
Out: 24!2!

In: 127!2!2!2!2!2!2!2! 
Out: 128!

In: 32!56!29!128!  
Out: 29!32!56!128!

La mejor de las suertes

tuskiomi
fuente
Dado que el producto vacío es 1 es la salida para, digamos 1!1!solo una cadena vacía?
Jonathan Allan
@JonathanAllan 1! 1! ¡Reduce a 1! O 0!
tuskiomi
Lo que luego se reduce a la cadena vacía: /
Jonathan Allan
@JonathanAllan Voy a decir que 1 no es igual a una cadena vacía
tuskiomi

Respuestas:

5

Jalea ,  17  18 bytes

!P
ÇṗLÇ⁼¥ÐfÇḢḟ1ȯ0F

Un enlace monádico que toma y devuelve una lista de los números (se adhiere a la opción factorial por número)

Pruébalo en línea!

¿Cómo?

Una versión de golf (aunque escrita independientemente) de la solución de Pietu1998.

!P - Link 1, product of factorials: list
!  - factorial (vectorises)
 P - product

ÇṗLÇ⁼¥ÐfÇḢḟ1ȯ0F - Main link: list                       e.g. [3,2,2]
Ç               - call the last link (1) as a monad           24
  L             - length                                      3
 ṗ              - Cartesian power      [[1,1,1],[1,1,2],...,[1,1,24],...,[24,24,24]]
        Ç       - call the last link (1) as a monad           24
      Ðf        - filter keep if:
     ¥          -   last two links as a dyad:
   Ç            -     call the last link (1) as a monad     [1,2,...,24!,...,24!^3]
    ⁼           -     equal?
         Ḣ      - head
          ḟ1    - filter out any ones
            ȯ0  - or with zero (for the empty list case)
              F - flatten (to cater for the fact that zero is not yet a list)
Jonathan Allan
fuente
1
Me parece bastante claro: no estamos obligados a usarlo, pero podemos hacerlo si queremos.
Jonathan Allan
1
@tuskiomi El pie de página solo está formateando la salida de la lista para mayor claridad ... como un programa completo (en lugar de como una función), el código imprimirá el formato de Jelly de una lista (nada para vacío y sin encerrar [] para listas de longitud 1) .
Jonathan Allan
1
@tuskiomi TIO tiene límites ;-) pero creo que funciona teóricamente.
Erik the Outgolfer
1
@tuskiomi el poder cartesiano daría como resultado una lista de 23! ^ 4 listas. Se quedará sin tiempo (límite de 60 segundos en TIO) si no hay memoria.
Jonathan Allan
1
N! ^ M donde N es el producto y M es el número de términos (¡y también en el espacio!)
Jonathan Allan
3

Jalea , 19 bytes

,!P€E
SṗLçÐfµḢḟ1ȯ1F

Pruébalo en línea!

Rápido y sucio. Muy lento, incluso el 23!2!3!2!caso de prueba es un estiramiento. E / S como listas de enteros.

Explicación

,!P€E    Helper link. Arguments: attempt, original
,        Make the array [attempt, original].
         Example: [[1,1,1,4], [2,3,2,0]]
 !       Take the factorial of each item.
         Example: [[1,1,1,24], [2,6,2,1]]
  P€     Take the product of each sublist.
         Example: [24, 24]
    E    Check if the values are equal.

SṗLçÐfµḢḟ1ȯ1F   Main link. Arguments: original
S               Find the sum S of the integers in the input.
  L             Find the number N of integers in the input.
 ṗ              Generate all lists containing N integers from 1 to S.
   çÐf          Take the lists whose factorial-product is the same as the original.
       Ḣ        Take the first match. This is the one with the most ones.
        ḟ1      Remove any ones.
          ȯ1    If there were only ones, return a one instead.
            F   Turn into a list if needed.
PurkkaKoodari
fuente
Podemos usar listas como E / S
Jonathan Allan
@JonathanAllan Oh, eso aparentemente no fue editado en el OP
PurkkaKoodari
Mi 17 parece aún más lento ...
Jonathan Allan
Oh, es demasiado similar - tio.run/##y0rNyan8/…
Jonathan Allan
@JonathanAllan Adelante y publícalo, me parece diferente a pesar de que el algoritmo es esencialmente el mismo.
PurkkaKoodari
2

Limpio , 397 ... 317 bytes

import StdEnv,StdLib
c=length
f c m=sortBy c o flatten o map m
%n=f(>)@[2..n]
@1=[]
@n#f=[i\\i<-[2..n]|n/i*i==n&&and[i/j*j<i\\j<-[2..i-1]]]
=f++ @(n/prod f)
?l=group(f(>)%l)
$l=hd(f(\a b=c a<c b)(~(?l))[0..sum l])
~[]_=[[]]
~i n=[[m:k]\\m<-take n[hd(i!!0++[0])..],k<- ~[drop(c a)b\\a<-group(%m)&b<-i|b>a]n|i== ?[m:k]]

Pruébalo en línea!

Esto toma un valor [Int], determina los factores primos del resultado y reduce los factores para encontrar la representación más pequeña, utilizando el factor más grande en cualquier etapa como valor de referencia para el siguiente término factorial. No completará algunos casos de prueba en TIO, pero es bastante * rápido y puede ejecutarlos en menos de 3 minutos en una computadora portátil de rango medio.

* para un O((prod(N)!)^sum(N))algoritmo de complejidad

Οurous
fuente
Caso de prueba: 6, 2, 2
tsh
@tsh Corregido ahora. No estaba ordenando por la longitud más pequeña, sino por el primer miembro más grande basado en una suposición errónea.
Agradable
1

> <> , 66 bytes

1}:?\~l1=?v{!
-:?!\:{*}1
v?( 4:{/}1<o"!"n-1
{:,} :{/?%}:+1
\:1-?n;

Pruébalo en línea!

No es eficiente, no encuentra la cadena más pequeña y el intérprete no maneja muy bien con números extremadamente grandes. Pero al menos lo intenté? Toma datos como una lista de números a través de la -vbandera.

Primero, calcula el valor de la entrada factorizando cada número y multiplicándolos juntos. Luego encuentra el factorial más grande que se divide limpiamente en el total y lo genera. Repita hasta que obtenga un primo (que emite) o un 1 y salga del programa. Debido a esto, a veces no encuentra la representación más corta del número, por ejemplo, el caso de prueba7!2!2!7!2!2!2!2! devuelve en 10!224lugar de 8!8!porque encuentra que el total es divisible por 10. primero.

Jo King
fuente
1

Rubí , 240 237 233 bytes

Esto es increíblemente ineficiente.

Acepta una matriz de entradas como entrada

Devuelve una cadena y elige la opción más corta entre, digamos '720!', '6!!'y'3!!!'

->i{f=->n{n>0?n*f[n-1]:1}
s=->a{eval a.map{|i|f[i]}*?*}
r=->e,a=[2]{e==s[a]?a:s[a]<=e&&(r[e,a[0..-2]+[a[-1]+1]]||r[e,a+[2]])}
j=->v{v.join(?!)+?!}
u=r[s[i]]
while j[g=u.map{|i|i&&r[i]?[r[i],p]:i}.flatten].size<j[u].size;u=g;end
j[u]}

Pruébalo en línea!

Asone Tuhid
fuente