Factoring factorials

Question

Today in my statistics class, I found that some factorials can be simplified when multiplied together! For example: 5! * 3! = 5! *3*2 = 5! *6 = 6!

Your job:

Given a string containing only Arabic numbers and exclamation points, simplify my factorial to its shortest possible string, in the least amount of bytes for your language, code golf style.

Input

A string containing only Arabic numbers and exclamation points. The factorials for the input won't be bigger than 200!. Factorials will not have more than one factorial per number. Input may be taken as a list of integers.

Output

A possibly shortened string, that has the equivalent value on the input. Order is unimportant. Factorial notation is a must, but you aren't required to use more than one factorial symbol per number.

Test cases

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!

Best of luck

Answer 1

Jelly,  17  18 bytes

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

A monadic link taking and returning a list of the numbers (sticks to the one factorial per number option)

Try it online!

How?

A golfed (although independently written) version of Pietu1998's solution.

!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)

Answer 2

Jelly, 19 bytes

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

Try it online!

Quick and dirty. Very slow, even the 23!2!3!2! test case is a stretch. I/O as lists of integers.

Explanation

,!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.

Answer 3

Clean, 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]]

Try it online!

This takes an [Int], determines the prime factors of the result, and reduces over the factors to find the smallest representation, using the largest factor at any stage as a baseline value for the next factorial term. It won't complete some test cases on TIO, but it is fairly* fast, and can run them all in under 3 minutes on a midrange laptop.

* for an O((prod(N)!)^sum(N)) complexity algorithm

Answer 4

><>, 66 bytes

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

Try it online!

Not efficient, doesn't find the smallest string, and the interpreter doesn't deal very well with extremely large numbers. But at least I tried? Takes input as a list of numbers through the -v flag.

First it calculates the value of the input by factorialising each number and multiplying them together. Then it finds the largest factorial that divides cleanly into the total and outputs it. Repeat until it either gets a prime, (which it outputs) or a 1 and exits the program. Because of this, it sometimes doesn't find the shortest representation of the number, for example, the test case 7!2!2!7!2!2!2!2! returns 10!224 instead of 8!8! because it finds the total is divisible by 10! first.

Answer 5

Ruby, 240 237 233 bytes

This is incredibly inefficient

Accepts an array of ints as input

Returns a string and chooses the shortest option between, say, '720!','6!!' and '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]}

Try it online!