Factoriels factoriels

16

Aujourd'hui dans ma classe de statistiques, j'ai trouvé que certaines factorielles peuvent être simplifiées lorsqu'elles sont multipliées ensemble! Par exemple:5! * 3! = 5! *3*2 = 5! *6 = 6!

Votre travail:

Étant donné une chaîne contenant uniquement des nombres arabes et des points d'exclamation, simplifiez mon factoriel à sa chaîne la plus courte possible, dans le moins d'octets pour votre langue, codez le style de golf.

Contribution

Une chaîne contenant uniquement des nombres arabes et des points d'exclamation. Les factorielles pour l'entrée ne dépasseront pas 200!. Les factorielles n'auront pas plus d'une factorielle par nombre. L'entrée peut être considérée comme une liste d'entiers.

Production

Une chaîne éventuellement raccourcie, qui a la valeur équivalente sur l'entrée. L'ordre est sans importance. La notation factorielle est un must, mais vous n'êtes pas obligé d'utiliser plus d'un symbole factoriel par nombre.

Cas de test

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!

Bonne chance

tuskiomi
la source
Puisque le produit vide est 1 est la sortie pour, disons 1!1!juste une chaîne vide?
Jonathan Allan
@JonathanAllan 1! 1! Réduit à 1! Ou 0!
tuskiomi
Ce qui se réduit alors à la chaîne vide: /
Jonathan Allan
@JonathanAllan Je vais dire que 1 n'est pas égal à une chaîne vide
tuskiomi

Réponses:

5

Gelée ,  17  18 octets

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

Un lien monadique prenant et retournant une liste des nombres (s'en tient à l'option un factoriel par nombre)

Essayez-le en ligne!

Comment?

Une version golfée (bien qu'écrite indépendamment) de la solution 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
la source
1
Cela me semble assez clair - nous ne sommes pas tenus de l'utiliser, mais nous pouvons le faire si nous le voulons.
Jonathan Allan
1
@tuskiomi Le pied de page ne fait que formater la sortie de la liste pour plus de clarté ... en tant que programme complet (plutôt qu'en tant que fonction), le code imprimera le format de Jelly d'une liste (rien pour vide et pas de clôture [] pour les listes de longueur 1) .
Jonathan Allan
1
@tuskiomi TIO a des limites ;-) mais je pense que cela fonctionne théoriquement.
Erik the Outgolfer
1
@tuskiomi le pouvoir cartésien donnerait une liste de 23! ^ 4 listes. Il manquera de temps (limite 60s sur TIO) sinon mémoire.
Jonathan Allan
1
N! ^ M où N est le produit et M est le nombre de termes (et dans l'espace aussi !!)
Jonathan Allan
3

Gelée , 19 octets

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

Essayez-le en ligne!

Rapide et sale. Très lent, même le 23!2!3!2!cas de test est un tronçon. E / S sous forme de listes d'entiers.

Explication

,!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
la source
Nous pouvons utiliser des listes comme E / S
Jonathan Allan
@JonathanAllan Oh, cela n'a apparemment pas été modifié dans l'OP
PurkkaKoodari
Mon 17 semble encore plus lent ...
Jonathan Allan
Oh, c'est beaucoup trop similaire - tio.run/##y0rNyan8/…
Jonathan Allan
@JonathanAllan Allez-y et postez-le, il me semble différent même si l'algorithme est essentiellement le même.
PurkkaKoodari
2

Nettoyer , 397 ... 317 octets

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

Essayez-le en ligne!

Cela prend un [Int], détermine les facteurs premiers du résultat et réduit les facteurs pour trouver la plus petite représentation, en utilisant le plus grand facteur à n'importe quel stade comme valeur de référence pour le prochain terme factoriel. Il ne terminera pas certains cas de test sur TIO, mais il est assez * rapide et peut les exécuter tous en moins de 3 minutes sur un ordinateur portable de milieu de gamme.

* pour un O((prod(N)!)^sum(N))algorithme de complexité

Οurous
la source
Testcase: 6, 2, 2
tsh
@tsh Fixé maintenant. Il n'était pas trié par la plus petite longueur, mais par le plus grand premier membre basé sur une hypothèse erronée.
Οurous
1

> <> , 66 octets

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

Essayez-le en ligne!

Pas efficace, ne trouve pas la plus petite chaîne et l'interpréteur ne gère pas très bien les nombres extrêmement grands. Mais au moins j'ai essayé? Prend l'entrée comme une liste de nombres à travers le -vdrapeau.

Il calcule d'abord la valeur de l'entrée en factorisant chaque nombre et en les multipliant ensemble. Ensuite, il trouve la plus grande factorielle qui se divise proprement dans le total et le produit. Répétez jusqu'à ce qu'il obtienne un nombre premier (qu'il sort) ou un 1 et quitte le programme. Pour cette raison, il ne trouve parfois pas la représentation la plus courte du nombre, par exemple, le cas de test 7!2!2!7!2!2!2!2!retourne 10!224au lieu de 8!8!car il trouve que le total est divisible par 10! premier.

Jo King
la source
1

Rubis , 240 237 233 octets

C'est incroyablement inefficace

Accepte un tableau d'entiers en entrée

Renvoie une chaîne et choisit l'option la plus courte entre, disons '720!', '6!!'et'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]}

Essayez-le en ligne!

Asone Tuhid
la source