Faktorial anjak piutang

16

Hari ini di kelas statistik saya, saya menemukan bahwa beberapa faktorial dapat disederhanakan ketika dikalikan bersama! Sebagai contoh:5! * 3! = 5! *3*2 = 5! *6 = 6!

Pekerjaan Anda:

Diberikan string yang hanya berisi angka-angka Arab dan tanda seru, sederhanakan faktorial saya ke string sesingkat mungkin, dengan jumlah byte terkecil untuk bahasa Anda, gaya kode golf.

Memasukkan

String yang hanya berisi angka Arab dan tanda seru. Faktorial untuk input tidak akan lebih besar dari 200 !. Faktorial tidak akan memiliki lebih dari satu faktorial per angka. Input dapat diambil sebagai daftar bilangan bulat.

Keluaran

String yang mungkin diperpendek, yang memiliki nilai setara pada input. Pesanan tidak penting. Notasi faktorial adalah suatu keharusan, tetapi Anda tidak diharuskan untuk menggunakan lebih dari satu simbol faktorial per angka.

Uji kasus

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!

Semoga berhasil

tuskiomi
sumber
Karena produk kosong adalah 1 untuk output, katakan 1!1!saja string kosong?
Jonathan Allan
@JonathanAllan 1! 1! Dikurangi menjadi 1! Atau 0!
tuskiomi
Yang kemudian direduksi menjadi string kosong: /
Jonathan Allan
@JonathanAllan saya akan mengatakan 1 tidak sama dengan string kosong
tuskiomi

Jawaban:

5

Jelly ,  17  18 byte

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

Tautan monadik yang mengambil dan mengembalikan daftar angka (menempel pada opsi satu faktorial per nomor)

Cobalah online!

Bagaimana?

Versi Pietu1998 versi pegolf (walaupun ditulis secara independen).

!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
sumber
1
Tampak cukup jelas bagi saya - kita tidak diharuskan untuk menggunakannya, tetapi dapat melakukannya jika kita mau.
Jonathan Allan
1
@tuskiomi Footer hanya memformat output daftar untuk kejelasan ... sebagai program lengkap (bukan sebagai fungsi) kode akan mencetak format daftar Jelly (tidak ada yang kosong & tanpa menyertakan [] untuk daftar panjang 1) .
Jonathan Allan
1
@tuskiomi TIO memiliki batas ;-) tapi saya pikir ini berfungsi secara teoritis.
Erik the Outgolfer
1
@ Tomkiomi kekuatan Cartesian akan menghasilkan daftar 23! ^ 4 daftar. Ini akan kehabisan waktu (batas 60-an pada TIO) jika bukan memori.
Jonathan Allan
1
N! ^ M di mana N adalah produk dan M adalah jumlah istilah (dan juga di luar angkasa !!)
Jonathan Allan
3

Jelly , 19 byte

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

Cobalah online!

Cepat dan kotor. Sangat lambat, bahkan 23!2!3!2!test case adalah peregangan. I / O sebagai daftar bilangan bulat.

Penjelasan

,!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
sumber
Kami dapat menggunakan daftar sebagai I / O
Jonathan Allan
@JonathanAllan Oh, itu tampaknya tidak diedit ke OP
PurkkaKoodari
17 anak saya sepertinya lebih lambat ...
Jonathan Allan
Oh, itu terlalu mirip - tio.run/##y0rNyan8/…
Jonathan Allan
@ JonathanAllan Silakan dan kirim, terlihat berbeda bagiku meskipun algoritme dasarnya sama.
PurkkaKoodari
2

Bersih , 397 ... 317 byte

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

Cobalah online!

Ini mengambil [Int], menentukan faktor utama dari hasil, dan mengurangi faktor untuk menemukan representasi terkecil, menggunakan faktor terbesar pada setiap tahap sebagai nilai dasar untuk istilah faktorial berikutnya. Ini tidak akan menyelesaikan beberapa kasus uji pada TIO, tetapi ini cukup * cepat, dan dapat menjalankan semuanya dalam waktu kurang dari 3 menit pada laptop kelas menengah.

* untuk O((prod(N)!)^sum(N))algoritme kompleksitas

Suram
sumber
Testcase: 6, 2, 2
tsh
@tsh Diperbaiki sekarang. Itu tidak memilah berdasarkan panjang terkecil, tetapi dengan anggota pertama terbesar berdasarkan asumsi yang salah.
Surous
1

> <> , 66 byte

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

Cobalah online!

Tidak efisien, tidak menemukan string terkecil, dan interpreter tidak berurusan dengan baik dengan jumlah yang sangat besar. Tetapi setidaknya saya mencoba? Mengambil input sebagai daftar angka melalui-v flag.

Pertama, ia menghitung nilai input dengan memfaktorkan setiap angka dan mengalikannya. Kemudian ia menemukan faktorial terbesar yang terbagi dengan bersih menjadi total dan menghasilkannya. Ulangi sampai mendapat prime, (yang dikeluarkan) atau 1 dan keluar dari program. Karena itu, kadang-kadang tidak menemukan representasi nomor terpendek, misalnya, test case 7!2!2!7!2!2!2!2!kembali, 10!224bukan 8!8!karena menemukan total dapat dibagi oleh 10! pertama.

Jo King
sumber
1

Ruby , 240 237 233 byte

Ini sangat tidak efisien

Menerima array int sebagai input

Mengembalikan string dan memilih opsi terpendek antara, katakan '720!',, '6!!'dan'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]}

Cobalah online!

Asone Tuhid
sumber