16
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Since the empty product is 1 is the output for, say 1!1! just an empty string? \$\endgroup\$ – Jonathan Allan Jan 18 '18 at 20:24
  • \$\begingroup\$ @JonathanAllan 1!1! Reduces to 1! Or 0! \$\endgroup\$ – tuskiomi Jan 18 '18 at 20:26
  • \$\begingroup\$ Which then reduces to the empty string :/ \$\endgroup\$ – Jonathan Allan Jan 18 '18 at 20:26
  • \$\begingroup\$ @JonathanAllan I'm going to say 1 is not equal to as empty string \$\endgroup\$ – tuskiomi Jan 18 '18 at 20:29
5
\$\begingroup\$

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)
\$\endgroup\$
  • 1
    \$\begingroup\$ Seems clear enough to me - we are not required to use it, but can do so if we want. \$\endgroup\$ – Jonathan Allan Jan 18 '18 at 21:01
  • 1
    \$\begingroup\$ @tuskiomi The footer is just formatting the list output for clarity... as a full program (rather than as a function) the code will print Jelly's format of a list (nothing for empty & no enclosing [] for lists of length 1). \$\endgroup\$ – Jonathan Allan Jan 18 '18 at 21:42
  • 1
    \$\begingroup\$ @tuskiomi TIO has limits ;-) but I think it works theoretically. \$\endgroup\$ – Erik the Outgolfer Jan 18 '18 at 21:46
  • 1
    \$\begingroup\$ @tuskiomi the Cartesian power would result in a list of 23!^4 lists. It will run out of time (60s limit on TIO) if not memory. \$\endgroup\$ – Jonathan Allan Jan 18 '18 at 21:46
  • 1
    \$\begingroup\$ N!^M where N is the product and M is the number of terms (and in space too!!) \$\endgroup\$ – Jonathan Allan Jan 18 '18 at 21:54
3
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ We may use lists as I/O \$\endgroup\$ – Jonathan Allan Jan 18 '18 at 20:25
  • \$\begingroup\$ @JonathanAllan Oh, that wasn't apparently edited into the OP \$\endgroup\$ – PurkkaKoodari Jan 18 '18 at 20:26
  • \$\begingroup\$ My 17 seems even slower... \$\endgroup\$ – Jonathan Allan Jan 18 '18 at 20:32
  • \$\begingroup\$ Oh, it's way too similar - tio.run/##y0rNyan8/… \$\endgroup\$ – Jonathan Allan Jan 18 '18 at 20:32
  • \$\begingroup\$ @JonathanAllan Go ahead and post it, looks different to me even though the algorithm is essentially the same. \$\endgroup\$ – PurkkaKoodari Jan 18 '18 at 20:34
2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Testcase: 6, 2, 2 \$\endgroup\$ – tsh Jan 19 '18 at 5:30
  • \$\begingroup\$ @tsh Fixed now. It wasn't sorting by smallest length, but by largest first member based on a mistaken assumption. \$\endgroup\$ – Οurous Jan 19 '18 at 6:22
1
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.