Dilema Kurator

9

pengantar

Anda adalah seorang teman kurator untuk sebuah museum seni, yang baru-baru ini senang mendapatkan seni modern dari empat seniman ( beberapa di antaranya mungkin memberi kurator nol karya seni, bajingan muda ). Karena ini adalah seni modern, semua karya seniman yang ada terlihat persis sama. Teman Anda ingin menggunakan komputer untuk membantu memutuskan urutan penempatan potongan-potongan ini.

Persyaratan Program

Program Anda harus mengambil lima bilangan bulat (diteruskan ke fungsi atau diinput melalui stdin (atau yang lainnya)). Empat yang pertama adalah jumlah lukisan yang disediakan oleh masing-masing dari empat seniman. Nilai terakhir adalah indeks permutasi i(dihitung dari 1, bukan 0). Kurator ingin melihat ipermutasi ke-3 dengan urutan leksikografis dari lukisan-lukisan tersebut.

Program Anda harus menampilkan permutasi ini dalam format apa pun yang masuk akal: misalnya abbccdatau [0 1 1 2 2 3]. Waktu kerja untuk input yang berjumlah kurang dari sepuluh lukisan harus memakan waktu kurang dari satu jam (semoga ini tidak menjadi masalah).

Anda tidak diizinkan untuk menggunakan fungsi bawaan untuk mengerjakan permutasi

Contohnya

Input: 0 1 2 0 2

Mengingat bahwa kita memiliki satu lukisan oleh seniman B dan dua oleh seniman C (dan mereka semua terlihat sama), permutasi dalam urutan leksikografis adalah:

['bcc', ' cbc ', 'ccb']

Permutasi yang disorot akan menjadi output yang benar, karena ini adalah yang kedua dalam urutan leksikografis.

Input: 1 2 0 1 5

['abbd', 'abdb', 'adbb', 'babd', ' badb ', 'bbad', 'bbda', 'bdab', 'bdba', 'dabb', 'dbab', 'dbab', 'dbba']

Pengujian

Berikut ini beberapa tes yang harus benar.

1 2 4 1 5    - ABBDCCCC
2 2 3 1 86   - ABBCACDC
4 1 2 0 24   - AACACBA
1 4 3 2 65   - ABBCBBDCDC

Sepotong kode pendek dalam Python3 yang seharusnya secara acak menghasilkan input dan output tersedia di sini (tidak berlaku untuk entri, ini menggunakan impor permutasi Python):

from itertools import permutations
from random import randint
a,b,c,d,n = randint(1,2),randint(1,2),randint(1,3),randint(1,3),randint(1,15)
print(str(a) + " " + str(b) + " " + str(c) + " " + str(d) + " " + str(n) + " - " + str(sorted(set([''.join(p) for p in permutations(a * "a" + b * "b" + c * "c" + d * "d")]))[n-1]))

Papan angka

Optimizer - CJam       - 39  - Confirmed - Bruteforce
EDC65     - JavaScript - 120 - Confirmed - Bruteforce
Jakube    - Python2    - 175 - Confirmed - Algorithmic
Alexander Craggs
sumber
1
Anda berkata, "semua bagian terlihat persis sama". Apakah yang Anda maksudkan "semua potongan dari artis tertentu terlihat persis sama, tetapi potongan-potongan dari artis yang berbeda terlihat berbeda"?
DavidC
Ini bukan entri yang valid, tapi saya pikir itu mungkin masih berguna untuk seseorang: {:A.a.{~97+[:I.}:valid J dan berfungsi, tetapi digunakan A.untuk sebagian besar pekerjaan, jadi itu tidak valid. Jika Anda bisa menulis fungsi yang menggantikan A.dan menggantikannya dalam fungsi ini, Anda akan memiliki jawaban yang valid.
Janıʇǝɥʇu
@ ɐɔıʇǝɥʇuʎs - Anda tidak harus menggunakan "ABCD", Anda dapat menggunakan sistem karakter / numerik / simbolik sama sekali. Saya khawatir saya tidak tahu J, dan jadi tidak bisa mengatakan masalah yang sebenarnya, tetapi harap ini membantu =)
Alexander Craggs
@PopeyGilbert Yah, versi yang hanya mengeluarkan angka akan menjadi {:A.[:I.}:... Masalahnya adalah itu, tapi saya masih berpikir A.itu tidak valid: jsoftware.com/help/dictionary/dacapdot.htm
ɐɔıʇǝɥʇuʎs
Bagaimana jika permutasi yang diperlukan tidak ada? 1 0 0 0 100?
edc65

Jawaban:

5

Python 2: 175 163 karakter

Ini bukan jawaban golf yang serius. Dengan algoritma yang berbeda saya mencapai 138 byte. Hanya ingin memposting ini di sini, karena tidak menggunakan kekerasan. Kompleksitas adalah Theta (gambar #).

f=lambda x:0**x or x*f(x-1)
def g(Q,n):
 while sum(Q):
  for j in 0,1,2,3:
   p=f(sum(Q)-1)*Q[j]
   for k in Q:p/=f(k)
   if p<n:n-=p
   else:print j;Q[j]-=1;break

Pemakaian:

g([1, 4, 3, 2], 65)

edit:

Algoritma yang sama, hanya beberapa bermain golf: jangan mengimpor metode faktorial dan sedikit perubahan dalam urutan perhitungan.

Terjemahan Pyth: 61 karakter

Lu*GhHUb1WsPQV4J*@QNytsPQFZPQ=J/JyZ)I<JeQ XQ4-eQJ)EN XQNt@QNB

Tidak ada yang istimewa di sini, terjemahan tepat dari kode python saya. Terlalu lama. Saya terlalu banyak menggunakan hal-hal yang jelek (panjang). 9 huruf pertama saja adalah definisi faktorial.

Lu*GhHUb1    def y(b): G=1; for H in range(b): G*= H+1; return G

Juga hal-hal seperti Q[j]-=1terlalu lama: XQNt@QN(1 karakter lebih dari Python !!!)

Pemakaian:

Cobalah di sini: Pyth Compiler / Executor . Nonaktifkan mode debug dan gunakan [2, 2, 3, 1, 86]sebagai input.

Jakube
sumber
Berhasil! Selamat atas solusi Python pertama! Namun, saya menemukan bahwa di lingkungan saya harus pindah ke from math import*luar fungsi. Menambahkan Anda ke leaderboard!
Alexander Craggs
Wow ... Solusi Anda sangat efisien - Untuk 32 lukisan hanya dibutuhkan 0,034 detik o.0.
Alexander Craggs
3

CJam, 50 43 39 byte

q~(])\{W):Wa*}%s:X{Xm*:s_&}X,(*{$X=},$=

Ini bisa bermain golf banyak.

Mengambil input dari STDIN dalam format berikut:

4 1 2 0 24

Keluaran lukisan. Misalnya untuk input di atas:

0020210

Cobalah online di sini

Perhatikan bahwa kompiler online menyerah untuk ukuran lukisan yang lebih besar. Anda harus mencoba input yang lebih besar pada versi Java

Pengoptimal
sumber
Selamat telah menjadi pemecah masalah pertama! 50 byte tentu merupakan nilai yang sulit dikalahkan. Saya akan menambahkan Anda sebagai bagian atas papan peringkat!
Alexander Craggs
@PopeyGilbert, Anda setidaknya harus menunggu selama 1 minggu atau lebih sebelum menerima jawaban
Pengoptimal
Ah, baiklah, saya sangat menyesal! Dalam tantangan saya sebelumnya, saya baru saja mengubah jawaban yang diterima ketika seseorang dipukuli. Salahku.
Alexander Craggs
1
@PopeyGilbert Itu sangat mulia dari Anda (dan saya berharap semua penulis penantang melakukannya), dan pada prinsipnya tidak ada yang salah dengan menerima lebih awal jika Anda melakukannya, tetapi beberapa orang tampaknya tersinggung jika tantangan di sini menerima jawaban lebih awal (karena, saya tebak, tidak ada yang mengharapkan penulis untuk mengubah jawaban yang diterima).
Martin Ender
Saya pribadi berpikir bahwa harus ada setidaknya 2 jawaban untuk dipilih antara sebelum menerima, bahkan jika itu dilakukan lebih awal. Tentu saja jika hanya ada 1 jawaban hingga satu minggu atau lebih, terima saja.
Pengoptimal
3

JavaScript (ES6) 120 138 147

Sebagai fungsi dengan lima parameter yang diperlukan, output melalui konsol.
Menggunakan simbol 0,1,2,3. Saya menghitung total simbol, lalu membangun dan memeriksa setiap nomor basis 4 yang memiliki jumlah digit yang diperlukan. Angka dengan angka yang salah dari digit apa pun akan dibuang.
Catatan: dengan JavaScript 32 bit integer ini berfungsi hingga 15 lukisan.

Sunting Lebih Pendek (hindari .toString) dan lebih cepat (kondisi keluar yang dimodifikasi). Waktu untuk setiap tes di bawah 1 detik.

Edit2 tidak ada perubahan algoritma, pegolf lagi (lekukan ditambahkan agar mudah dibaca)

F=(w,x,y,z,n)=>{
  for(a=0;n;n-=l=='0,0,0,0')
    for(l=[w,x,y,z],t=w+x+y+z,v='',b=a++;t--;b/=4)--l[d=b&3],v=d+v;
  console.log(v)
}

Tidak Disatukan dan tidak perlu FireFox

F=function(w,x,y,z,n) {
  for(a=0; n; a++) // exit when solution found (if wrong parameters, run forever)
  {
    l=[w,x,y,z]; // required number of each symbol
    t=w+x+y+z; // total of digits
    v=''; // init output string
    for(b=a;
      t--; // digit count down
      b >>= 2) // shift for next digit
    {
        d = b & 3; //get digit
        --l[d]; // decrement for the current digit
        v = d + v; // add to output string         
    }
    l[0]|l[1]|l[2]|l[3] // if digits ok
    ||--n // decrement counter
  }
  console.log(v) // when found, exit for and print the answer
}

Uji di konsol FireBug / FireFox

F(1, 2, 4, 1, 5) 
F(2, 2, 3, 1, 86)
F(4, 1, 2, 0, 24)
F(1, 4, 3, 2, 65)

Keluaran

01132222
01120232
0020210
0112113232
edc65
sumber
Halo! Memiliki sedikit kesulitan menjalankannya. Saya mengunduh FireFox untuk melihat apakah itu akan membantu. Saya akan menambahkan Anda ke leaderboard!
Alexander Craggs
Saya menemukan tabel yang bagus di sini - Saya akan menganggap Firefox diperlukan. Diuji dan berhasil! Papan peringkat diubah menjadi dikonfirmasi.
Alexander Craggs
Papan kepemimpinan tetapi tidak ada suara positif ... Anda benar-benar tidak menyukainya! :(
edc65
Agh! Saya sangat menyesal = (Sudah tergantikan sekarang =)
Alexander Craggs
Saya bertanya-tanya berapa lama algoritma ini akan berada di CJam. Tetapi sampai sekarang, saya tidak tahu bagaimana ini bekerja: P
Optimizer
2

Pyth , 20

@fqPQm/TdU4^U4sPQteQ

Coba di sini.

Input dalam bentuk daftar Python, mis [1, 2, 4, 1, 5]

Output juga dalam bentuk daftar Python, misalnya [0, 1, 1, 3, 2, 2, 2, 2]untuk input di atas.

Solusinya adalah kekerasan, dan membutuhkan waktu sekitar 10 detik, kasus terburuk, pada mesin saya.

Bagaimana itu bekerja:

@fqPQm/TdU4^U4sPQteQ
           ^U4sPQ         All permutations of [0, 1, 2, 3] with length equal to the number
                          of paintings.
     m/TdU4               Find the count (/) of paintings by painter in the input list.
 fqPQ                     Filter the permutations on the counts being the desired counts
                          in the input.
                          This gives all possible orderings of the paintings.
@                teQ      Index into this list at the given location - 1. (0-indexing)
isaacg
sumber