Продукт длины крюка

27

Диаграмма Юнга является расположением ящиков в левом выравнивании строк и топ выравниванием столбцов. Для каждого ящика все места над ним и слева от него заняты.

XXXXX
XXX
XXX
X

Длина крючка для ящика - это число ящиков справа от его строки и ниже его в столбце, также считая себя один раз. Например, вторая коробка имеет длину крючка 6:

X****
X*X
X*X
X

Вот все длины крючков:

86521
532
421
1

Ваша цель - вычислить произведение длин крючков здесь 8*6*5*2*1*5*3*2*4*2*1*1 = 115200.

(Читайте о формуле длины хука, если вам интересно, почему это выражение имеет значение.)

Ввод: набор размеров строк в виде чисел, подобных [5,3,3,1]или повторяющихся одинарных символов, таких как [[1,1,1,1,1], [1,1,1], [1,1,1], [1]]или "XXXXX XXX XXX X". Вы можете ожидать, что список будет отсортирован по возрастанию или убыванию, как вы пожелаете. Список будет непустым и будет содержать только положительные целые числа.

Вывод: произведение длины крючка, которая является положительным целым числом. Не беспокойтесь о целочисленных переполнениях или времени выполнения.

Встроенные модули, специально предназначенные для диаграмм Юнга или целочисленных разбиений, не допускаются.

Тестовые случаи:

[1] 1
[2] 2
[1, 1] 2
[5] 120
[2, 1] 3
[5, 4, 3, 2, 1] 4465125
[5, 3, 3, 1] 115200
[10, 5] 798336000
XNOR
источник

Ответы:

13

CJam, 20 19 байтов

{ee::+W%}_q~%z%:+:*

Это принимает унарный список в стиле CJam в порядке возрастания. Например:

[[1] [1 1 1] [1 1 1] [1 1 1 1 1]]

дает

115200

Как это работает

Эта версия предоставлена ​​Деннисом и использует тот факт, что Block ArrayList %все еще работает в CJam: D

{       }_             e# Put this block on stack and make a copy
          q~           e# Read the input and evaluate it to put the array of arrays on stack
            %          e# Use the copy of the block and map the array using that block
 ee                    e# Here we are mapping over each unary array in the input. ee converts
                       e# the array to [index value] pair.
   ::+                 e# Add up each index value pair. Now we have the horizontal half of
                       e# hook length for each row
      W%               e# Reverse the array to make sure the count is for blocks to the right
             z%        e# Transpose and do the same mapping for columns
               :+      e# Now we have all the hook lengths. Flatten the array
                 :*    e# Get the product of all hook lengths.

Это оригинальная 20-байтовая версия

1q~:,Wf%z:ee{:+)*}f/

Для этого используется список размеров строк в CJam в порядке возрастания. Например:

[1 3 3 5]

дает

115200

Как это работает

Если мы посмотрим на это, длина хука каждого блока в блок-диаграмме Юнга представляет собой сумму индекса этого блока в его строке и столбце с обратным отсчетом. т.е. начать индекс в каждой строке с правой стороны и начать индекс в каждом столбце снизу.

Мы берем входные данные в порядке возрастания размера строки, чтобы легко начать индекс снизу в каждом столбце. Во-первых, мы получаем индекс на строку и обращаем его вспять. Затем мы переносим. Поскольку исходный порядок строк был обратным, взятие индекса на этой транспонированной диаграмме непосредственно даст индекс снизу вверх.

Расширение кода

1                       e# This serves as the initial term for product of hook lengths
 q~                     e# Read the input and eval it to put an array on stack
   :,                   e# For each row-size (N), get an array of [0..N-1]
     Wf%                e# Reverse each row so that each row becomes [N-1..0]
        z               e# Transpose for the calculation of blocks below each block
         :ee            e# Enumerate each row. Convert it into array of [index value] pairs
            {    }f/    e# Apply this mapping block to each cell of each row
             :+         e# Add the index value pair. Here, index is the blocks below the
                        e# block and value is the blocks to the right of it in the Young diag
               )        e# Increment the sum by 1 to account for the block itself
                *       e# Multiply it with the current holding product, starting with 1

Попробуйте это онлайн здесь

оптимизатор
источник
{ee::+W%}_q~%z%:+:*(19 байт) Формат ввода:[[1][1 1 1][1 1 1][1 1 1 1 1]]
Деннис
@Dennis Nice (ab) использование порядка арности для %: P
Оптимизатор
6

J, 24 байта

*/@,@(1|@-+/\."1++/\)@:>

25 байт (с объяснением):

*/@,@(+/\."1|@<:@++/\)@:>

Вводит в виде списка возрастающих списков из одинарных цифр, аналогично примеру [[1], [1,1,1], [1,1,1], [1,1,1,1,1]].

Использование:

   f=.*/@,@(+/\."1|@<:@++/\)@:>

   f 1;1 1 1;1 1 1;1 1 1 1 1
115200

метод

  • Создать двоичную матрицу из ввода
  • Вычислите рабочие различия в обоих измерениях.
  • Для каждой ячейки сложите два результата, вычтите 1, возьмите абсолютное значение (чтобы отобразить изначально нулевые ячейки в 1)
  • Распутайте матрицу и возьмите произведение чисел.

Промежуточные результаты отображаются на входе 1 1 1 1 1;1 1 1;1 1 1;1 (5,3,3,1 in unary)( это для предыдущей версии с нисходящей длиной, но с использованием того же метода ):

   ]c=.1 1 1 1 1;1 1 1;1 1 1;1
┌─────────┬─────┬─────┬─┐
│1 1 1 1 1│1 1 1│1 1 1│1│
└─────────┴─────┴─────┴─┘

   (>)  c
1 1 1 1 1
1 1 1 0 0
1 1 1 0 0
1 0 0 0 0

   (+/\.@:>)  c
4 3 3 1 1
3 2 2 0 0
2 1 1 0 0
1 0 0 0 0

   (+/\."1@:>)  c
5 4 3 2 1
3 2 1 0 0
3 2 1 0 0
1 0 0 0 0

   ((+/\."1++/\.)@:>)  c
9 7 6 3 2
6 4 3 0 0
5 3 2 0 0
2 0 0 0 0

   ((+/\."1<:@++/\.)@:>)  c
8  6  5  2  1
5  3  2 _1 _1
4  2  1 _1 _1
1 _1 _1 _1 _1

   ((+/\."1|@<:@++/\.)@:>)  c
8 6 5 2 1
5 3 2 1 1
4 2 1 1 1
1 1 1 1 1

   (,@(+/\."1|@<:@++/\.)@:>)  c
8 6 5 2 1 5 3 2 1 1 4 2 1 1 1 1 1 1 1 1

   (*/@,@(+/\."1|@<:@++/\.)@:>)  c
115200

Явная версия той же длины:

3 :'*/,|<:(+/\."1++/\)>y'

Попробуйте это онлайн здесь.

randomra
источник
4

Pyth - 21 байт

Я теряю много байтов при вертикальном расчете. Собираюсь сосредоточиться на игре в гольф.

*Fs.em+lf>Td>Qkt-bdbQ

Принимает участие как [5, 3, 3, 1].

Попробуйте здесь онлайн .

Maltysen
источник
4

Pyth, 18 байт

*Fsm.e+k-bdf>TdQeQ

Принимает ввод в порядке возрастания, как [1, 3, 3, 5].

Демонстрация.


Альтернативное решение, 19 байтов

*Fs.em+s>Rd<Qk-bdbQ
isaacg
источник
3

Python 2, 89 88 байт

p=j=-1;d={}
for n in input():j+=1;i=0;exec"a=d[i]=d.get(i,j);p*=n-i+j-a;i+=1;"*n
print-p

(Спасибо @xnor за спасение одного безумного байта путем объединения pи j)

d.getВыглядит немного подозрительно ко мне, но в остальном я относительно доволен этим. Я попробовал некоторые другие подходы, такие как рекурсия и архивирование, но это единственный способ, который мне удалось получить до 100.

Принимает ввод из STDIN в виде списка в порядке возрастания, например [1, 3, 3, 5].

Sp3000
источник
3

Haskell, 68 байт

f[]=1
f g@(h:t)=(h+length t)*f[x-1|x<-g,x>1]
p[]=1
p g@(_:t)=f g*p t

Пример использования: p [5,4,3,2,1]->4465125

fсканирует слева направо путем умножения длины самого внешнего хука на рекурсивный вызов самого себя, где каждый элемент списка ввода уменьшается 1(удаляя его при достижении 0). pсканирует сверху вниз путем умножения fвсего списка pна хвост.

Ними
источник
2

R 174 байта

Итак ... Это решение довольно длинное и может быть более подходящим для игры в гольф. Я подумаю об этом !

v=c();d=length;m=matrix(-1,l<-d(a<-scan()),M<-max(a));for(i in 1:l)m[i,(1:a[i])]=c(a[i]:1);for(j in 1:M)m[,j]=m[,j]+c((((p=d(which(m[,j]>0)))-1)):0,rep(0,(l-p)));abs(prod(m))

Ungolfed:

v=c()          #Empty vector
d=length       #Alias

m=matrix(-1,l<-d(a<-scan()),M<-max(a)) #Builds a matrix full of `-1`

for(i in 1:l)
    m[i,(1:a[i])]=c(a[i]:1) #Replaces each row of the matrix by `n` to 1, `n` being the 
                            #corresponding input : each number is the number of non-empty
                            #cells at its left + itself

for(j in 1:M)
    m[,j]=m[,j]+c((((p=d(which(m[,j]>0)))-1)):0,rep(0,(l-p)))

    #This part calculates the number of "non-empty" (i.e. without `-1` in a column), -1,
    #because the count for the cell itself is already done.
    # Then, it creates a vector of those count, appending 0's at the end if necessary 
    #(this avoids recycling)

abs(prod(m)) #Outputs the absolute value of the product (because of the `-1`'s)
Фредерик
источник
1

Python 2, 135 128 байтов

Это берет список типов Python из stdin:

r=input()
c=[-1]*r[0]
for a in r:
 for b in range(a):c[b]+=1
s=1
y=0
for a in r:
 for x in range(a):s*=a-x+c[x]-y
 y+=1
print s

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

Мы получаем количество ячеек в каждом ряду в качестве входных данных. Это решение сначала подсчитывает количество ячеек в каждом столбце, в котором хранится c(на самом деле это число минус 1, чтобы упростить его использование в последующих вычислениях). Затем он перебирает все блоки и умножает длины хуков. Сама длина крючка вычисляется тривиально, если у вас есть количество блоков в каждой строке и столбце.

Рето Коради
источник
1
Похоже, вы не используете m?
xnor
Мог бы поклясться, что я его удалил! Я помню, что заметил, что использовал только один раз, и заменил единственное использование. Но тогда я, должно быть, упустил фактическое удаление переменной. :(
Рето Коради
1

JavaScript ( ES6 ) 69

Функция, принимающая массив целых чисел в порядке возрастания .

Запустите фрагмент для проверки (только Firefox)

F=x=>x.map(r=>{for(i=-1;++i<r;p[i]=-~p[i])t*=r-i+~~p[i]},p=[],t=1)&&t

// TEST
out=x=>O.innerHTML += x + '\n';

test=[
 {y:[1], h: 1}
,{y:[2], h: 2}
,{y:[1, 1], h: 2}
,{y:[5], h: 120}
,{y:[2, 1], h: 3}
,{y:[5, 4, 3, 2, 1], h: 4465125}
,{y:[5, 3, 3, 1], h: 115200}
,{y:[10, 5], h: 798336000}
]

test.forEach(t=>{ 
  t.y.reverse(); // put in ascending order
  r=F(t.y);
  out((r==t.h? 'Ok':'Fail')+' Y: ['+t.y+'] Result:'+r+' Check:'+t.h)
})  
<pre id=O></pre>

edc65
источник
1

Питон, 95 91 байт

Это реализация Python для ответа Ними на Haskell . Предложения по игре в гольф приветствуются.

f=lambda z:z==[]or(z[0]+len(z)-1)*f([i-1for i in z if~-i])
p=lambda z:z==[]or f(z)*p(z[1:])
Sherlock9
источник
Добро пожаловать в гольф на Python! Вы можете сделать, z and _ or 1как, z==[]or _когда zэто список, используя тот факт, что True==1. Объявления функций Python являются более многословными, чем Haskell, поэтому он часто дает хорошую выгоду для определения одной рекурсивной функции, которая выполняет как внутренние, так и внешние рекурсивные циклы, хотя я не знаю, насколько это возможно.
xnor
@xnor "Добро пожаловать в гольф на Питоне"?
Sherlock9
Ой, прости, ты играешь в гольф на Python. Я ассоциирую вас с На самом деле.
xnor
@xnor Задолго до того, как я начал заниматься игрой в гольф на Python. Я немного раздражен, что ты не помнишь: P
Sherlock9
Я не могу говорить за xnor, но я узнаю пользователей в основном по их аватару.
Деннис