Produk panjang kait

27

Sebuah diagram Muda adalah susunan kotak di baris kiri-dibenarkan dan top-dibenarkan kolom. Untuk setiap kotak, semua ruang di atasnya dan di sebelah kirinya ditempati.

XXXXX
XXX
XXX
X

The Panjang kail dari kotak adalah jumlah kotak ke kanan berturut-turut, serta di bawahnya dalam kolomnya, juga menghitung sendiri sekali. Misalnya, kotak kedua memiliki panjang kait 6:

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

Berikut ini semua panjang kaitnya:

86521
532
421
1

Tujuan Anda adalah menghitung produk dari panjang kait, di sini 8*6*5*2*1*5*3*2*4*2*1*1 = 115200.

(Baca tentang rumus panjang kait jika Anda tertarik mengapa ungkapan ini penting.)

Input: Kumpulan ukuran baris sebagai angka seperti [5,3,3,1]atau sebagai simbol unary berulang seperti [[1,1,1,1,1], [1,1,1], [1,1,1], [1]]atau "XXXXX XXX XXX X". Anda dapat mengharapkan daftar diurutkan naik atau turun, seperti yang Anda inginkan. Daftar ini akan kosong dan hanya berisi bilangan bulat positif.

Output: Produk dari panjang kait, yang merupakan bilangan bulat positif. Jangan khawatir tentang integer overflow atau runtime.

Built-in yang khusus menangani diagram Young atau partisi integer tidak diperbolehkan.

Kasus uji:

[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
Tidak
sumber

Jawaban:

13

CJam, 20 19 byte

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

Ini mengambil dalam daftar unary gaya CJam dalam urutan menaik. Sebagai contoh:

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

memberi

115200

Bagaimana itu bekerja

Versi ini disediakan oleh Dennis dan menggunakan fakta bahwa Block ArrayList %masih berfungsi di 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.

Ini adalah versi asli 20 byte

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

Ini mengambil daftar gaya CJam dari ukuran baris dalam urutan menaik. Sebagai contoh:

[1 3 3 5]

memberi

115200

Bagaimana itu bekerja

Jika kita melihatnya, kait panjang setiap blok dalam diagram blok Young adalah jumlah dari indeks blok itu di baris dan kolomnya, menghitung mundur. yaitu Mulai indeks di setiap baris dari sisi kanan dan mulai indeks di setiap kolom dari bawah.

Kami mengambil input dalam urutan ukuran baris agar dapat dengan mudah memulai indeks dari bawah di setiap kolom. Pertama, kami mendapatkan indeks per baris dan membalikkannya. Lalu kami pindah. Karena urutan baris asli dibalik, mengambil indeks dalam diagram yang ditransformasikan ini akan langsung memberikan indeks bawah ke atas.

Perluasan kode

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

Cobalah online di sini

Pengoptimal
sumber
{ee::+W%}_q~%z%:+:*(19 byte) Format input:[[1][1 1 1][1 1 1][1 1 1 1 1]]
Dennis
@ Dennis Nice (ab) penggunaan urutan arity untuk %: P
Pengoptimal
6

J, 24 byte

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

25 byte (dengan penjelasan):

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

Mengambil input sebagai daftar daftar naik dari angka-angka unary mirip dengan contoh [[1], [1,1,1], [1,1,1], [1,1,1,1,1]].

Pemakaian:

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

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

metode

  • Buat matriks biner dari input
  • Hitung perbedaan running di kedua dimensi.
  • Untuk setiap sel, tambahkan dua hasil, kurangi 1, ambil nilai absolut (untuk memetakan sel nol awalnya menjadi 1)
  • Angkat matriks dan ambil produk angka-angkanya.

Hasil antara ditunjukkan pada input 1 1 1 1 1;1 1 1;1 1 1;1 (5,3,3,1 in unary)( ini untuk versi sebelumnya dengan panjang menurun tetapi menggunakan metode yang sama ):

   ]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

Versi eksplisit dengan panjang yang sama:

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

Cobalah online di sini.

randomra
sumber
4

Pyth - 21 byte

Saya kehilangan banyak byte dalam perhitungan vertikal. Akan fokus pada bermain golf itu.

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

Mengambil input seperti [5, 3, 3, 1].

Coba di sini online .

Maltysen
sumber
4

Pyth, 18 byte

*Fsm.e+k-bdf>TdQeQ

Mengambil input dalam urutan menaik, seperti [1, 3, 3, 5].

Demonstrasi.


Solusi alternatif, 19 byte

*Fs.em+s>Rd<Qk-bdbQ
isaacg
sumber
3

Python 2, 89 88 byte

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

(Terima kasih kepada @xnor untuk satu byte penyimpanan yang gila dengan menggabungkan pdan j)

The d.getterlihat sedikit mencurigakan kepada saya, tetapi sebaliknya aku relatif senang dengan hal ini. Saya mencoba beberapa pendekatan lain, seperti rekursi dan zipping, tetapi ini adalah satu-satunya yang berhasil saya dapatkan di bawah 100.

Mengambil input dari STDIN sebagai daftar dalam urutan menaik, mis [1, 3, 3, 5].

Sp3000
sumber
3

Haskell, 68 byte

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

Contoh penggunaan: p [5,4,3,2,1]->4465125

fmemindai dari kiri ke kanan dengan mengalikan panjang kait terluar dengan panggilan rekursif ke dirinya sendiri di mana setiap elemen dari daftar input dikurangi dengan 1(menjatuhkannya saat mencapai 0). pmemindai dari atas ke bawah dengan mengalikan fseluruh daftar dengan pekor.

nimi
sumber
2

R, 174 byte

Jadi ... Solusi ini cukup panjang dan mungkin bisa lebih golf. Saya akan berpikir tentang hal ini !

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

Tidak Terkumpul:

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)
Frédéric
sumber
1

Python 2, 135 128 byte

Ini mengambil daftar jenis Python dari 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

Ini adalah implementasi yang sangat kanonik, tetapi saya belum menemukan sesuatu yang jauh lebih pintar sejauh ini. Saya merasa bahwa akan ada solusi yang jauh lebih pendek bahkan dengan bahasa pemrograman "nyata".

Kami mendapatkan jumlah kotak di setiap baris sebagai input. Solusi ini pertama-tama menghitung jumlah kotak di setiap kolom, yang disimpan dalam c(sebenarnya jumlah minus 1 untuk menyederhanakan penggunaannya dalam perhitungan nanti). Kemudian ia beralih ke semua kotak, dan mengalikan panjang kait. Panjang kait itu sendiri sepele untuk dihitung setelah Anda memiliki jumlah kotak di setiap baris dan kolom.

Reto Koradi
sumber
1
Sepertinya Anda tidak menggunakan m?
xnor
Bisa bersumpah bahwa saya menghapusnya! Saya ingat memperhatikan bahwa saya hanya menggunakannya sekali, dan mengganti satu-satunya penggunaan. Tapi kemudian saya pasti ketinggalan untuk benar-benar menghapus variabel. :(
Reto Koradi
1

JavaScript ( ES6 ) 69

Suatu fungsi mengambil array bilangan bulat dalam urutan menaik .

Jalankan cuplikan untuk menguji (khusus 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
sumber
1

Python, 95 91 byte

Ini adalah implementasi Python dari jawaban Hasimi nimi . Saran bermain golf diterima.

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
sumber
Selamat datang di golf Python! Anda dapat melakukan z and _ or 1seperti z==[]or _saat zini daftar, menggunakan fakta bahwa True==1. Deklarasi fungsi Python lebih banyak daripada Haskell, sehingga sering memberikan hasil yang baik untuk mendefinisikan fungsi rekursif tunggal yang melakukan loop rekursif dalam dan luar, meskipun saya tidak tahu seberapa layak yang ada di sini.
xnor
@ xnor "Selamat datang di golf Python"?
Sherlock9
Oh, maaf, kamu bermain golf dengan Python. Saya mengasosiasikan Anda dengan Sebenarnya.
xnor
@ xnor Panjang, jauh sebelum saya mulai di Sebenarnya, saya bermain golf dengan Python. Saya agak jengkel bahwa Anda tidak ingat: P
Sherlock9
Saya tidak dapat berbicara untuk xnor, tetapi saya mengenali pengguna terutama dari avatar mereka.
Dennis