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\$
4
  • \$\begingroup\$ Since the empty product is 1 is the output for, say 1!1! just an empty string? \$\endgroup\$ Commented Jan 18, 2018 at 20:24
  • \$\begingroup\$ @JonathanAllan 1!1! Reduces to 1! Or 0! \$\endgroup\$
    – tuskiomi
    Commented Jan 18, 2018 at 20:26
  • \$\begingroup\$ Which then reduces to the empty string :/ \$\endgroup\$ Commented Jan 18, 2018 at 20:26
  • \$\begingroup\$ @JonathanAllan I'm going to say 1 is not equal to as empty string \$\endgroup\$
    – tuskiomi
    Commented Jan 18, 2018 at 20:29

5 Answers 5

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\$
11
  • 1
    \$\begingroup\$ Seems clear enough to me - we are not required to use it, but can do so if we want. \$\endgroup\$ Commented Jan 18, 2018 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\$ Commented Jan 18, 2018 at 21:42
  • 1
    \$\begingroup\$ @tuskiomi TIO has limits ;-) but I think it works theoretically. \$\endgroup\$ Commented Jan 18, 2018 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\$ Commented Jan 18, 2018 at 21:46
  • 1
    \$\begingroup\$ N!^M where N is the product and M is the number of terms (and in space too!!) \$\endgroup\$ Commented Jan 18, 2018 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\$
6
  • \$\begingroup\$ We may use lists as I/O \$\endgroup\$ Commented Jan 18, 2018 at 20:25
  • \$\begingroup\$ @JonathanAllan Oh, that wasn't apparently edited into the OP \$\endgroup\$ Commented Jan 18, 2018 at 20:26
  • \$\begingroup\$ My 17 seems even slower... \$\endgroup\$ Commented Jan 18, 2018 at 20:32
  • \$\begingroup\$ Oh, it's way too similar - tio.run/##y0rNyan8/… \$\endgroup\$ Commented Jan 18, 2018 at 20:32
  • \$\begingroup\$ @JonathanAllan Go ahead and post it, looks different to me even though the algorithm is essentially the same. \$\endgroup\$ Commented Jan 18, 2018 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\$
2
  • \$\begingroup\$ Testcase: 6, 2, 2 \$\endgroup\$
    – tsh
    Commented Jan 19, 2018 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
    Commented Jan 19, 2018 at 6:22
1
\$\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\$
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\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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