Факторинг факториалов

16

Сегодня в моем классе статистики я обнаружил, что некоторые факториалы могут быть упрощены при умножении вместе! Например:5! * 3! = 5! *3*2 = 5! *6 = 6!

Твоя работа:

Учитывая строку, содержащую только арабские цифры и восклицательные знаки, упростите мой факториал до самой короткой из возможных строк, наименьшее количество байтов для вашего языка, кодируйте стиль гольфа.

вход

Строка, содержащая только арабские цифры и восклицательные знаки. Факториалы для ввода не будут больше 200! Факториалы не будут иметь более одного факториала на число. Входные данные могут быть приняты как список целых чисел.

Выход

Возможно, сокращенная строка, которая имеет эквивалентное значение на входе. Заказ не важен. Факториальная запись обязательна, но вы не обязаны использовать более одного факториального символа на число.

Контрольные примеры

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!

Удачи

tuskiomi
источник
Так как пустой продукт равен 1, является ли вывод, скажем, 1!1!просто пустой строкой?
Джонатан Аллан
@JonathanAllan 1! 1! Уменьшается до 1! Или 0!
Tuskiomi
Который затем сводится к пустой строке: /
Джонатан Аллан
@JonathanAllan Я хочу сказать, что 1 не равно пустой строке
tuskiomi

Ответы:

5

Желе ,  17  18 байт

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

Монадическая ссылка, получающая и возвращающая список чисел (привязывается к одному факториалу для каждого номера)

Попробуйте онлайн!

Как?

Гольф (хотя и написано независимо) версия решения 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)
Джонатан Аллан
источник
1
Мне кажется это достаточно ясным - мы не обязаны его использовать, но можем сделать это, если захотим.
Джонатан Аллан
1
@tuskiomi Нижний колонтитул просто форматирует вывод списка для ясности ... как полная программа (а не как функция), код будет печатать формат списка Jelly (ничего для пустого и не включающего [] для списков длиной 1) ,
Джонатан Аллан
1
@tuskiomi TIO имеет ограничения ;-) но я думаю, что это работает теоретически.
Эрик Outgolfer
1
@tuskiomi, декартова сила приведет к списку из 23! ^ 4 списков. Время истекает (ограничение 60 секунд на TIO), если не память.
Джонатан Аллан
1
N! ^ M, где N - произведение, а M - количество терминов (и в пространстве тоже !!)
Джонатан Аллан
3

Желе , 19 байт

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

Попробуйте онлайн!

Быстро и грязно. Очень медленно, даже 23!2!3!2!тестовый пример растягивается. Ввод / вывод в виде списков целых чисел.

объяснение

,!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
источник
Мы можем использовать списки как ввод / вывод
Джонатан Аллан
@JonathanAllan О, это не было очевидно отредактировано в OP
PurkkaKoodari
Мой 17 кажется еще медленнее ...
Джонатан Аллан
О, это слишком похоже - tio.run/##y0rNyan8/…
Джонатан Аллан
@JonathanAllan Иди и опубликуй его, для меня он выглядит иначе, хотя алгоритм по сути тот же.
PurkkaKoodari
2

Чисто , 397 ... 317 байт

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

Попробуйте онлайн!

Это берет [Int], определяет главные факторы результата и уменьшает факторы, чтобы найти наименьшее представление, используя самый большой фактор на любой стадии в качестве базового значения для следующего факторного члена. Он не завершит некоторые тестовые случаи на TIO, но он довольно * быстрый и может запустить их все менее чем за 3 минуты на ноутбуке среднего уровня.

* для O((prod(N)!)^sum(N))алгоритма сложности

Οurous
источник
Контрольный пример
@tsh Исправлено сейчас. Это была не сортировка по наименьшей длине, а по величине первого члена, основанная на ошибочном предположении.
Οurous
1

> <> , 66 байт

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

Попробуйте онлайн!

Неэффективно, не находит самую маленькую строку, и интерпретатор не очень хорошо справляется с чрезвычайно большими числами. Но хотя бы я пытался? Принимает ввод как список чисел через -vфлаг.

Сначала он вычисляет значение входных данных путем факториализации каждого числа и умножения их вместе. Затем он находит самый большой факториал, который делится чисто на сумму и выводит его. Повторяйте, пока он не получит простое число (которое выводит) или 1 и не выйдет из программы. Из-за этого он иногда не находит кратчайшего представления числа, например, 7!2!2!7!2!2!2!2!возвращается тестовый пример 10!224вместо того, 8!8!чтобы найти, что сумма делится на 10! первый.

Джо Кинг
источник
1

Рубин , 240 237 233 байта

Это невероятно неэффективно

Принимает массив входных данных в качестве входных данных

Возвращает строку и выбирает кратчайший вариант, скажем '720!', '6!!'и'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]}

Попробуйте онлайн!

Асоне Тухид
источник