Implementasikan operasi tas

20

Sebuah tas , juga disebut multiset, adalah koleksi unordered. Anda bisa menyebutnya set yang memungkinkan duplikat, atau daftar (atau array) yang tidak dipesan / diindeks. Dalam tantangan ini, Anda diminta untuk mengimplementasikan operasi tas: penambahan, perbedaan, perkalian, pembagian, penghitungan dan uji kesetaraan.

Operasi

Operasi yang ditentukan mungkin tidak konvensional.

  • Selain itu menggabungkan dua tas menjadi satu, menghemat jumlah total setiap nilai
    [1,2,2,3] + [1,2,4] = [1,1,2,2,2,3,4]
  • perbedaan menghapus dari tas setiap elemen dari tas lain, atau tidak melakukan apa pun jika tidak ada elemen tersebut
    [1,2,2,4] - [1,2] = [2,4] [1,2,3] - [2,4] = [1,3]
  • multiplikasi mengalikan setiap elemen dalam tas.
    [1,2,3,3,4] * 3 = [1,1,1,2,2,2,3,3,3,3,3,3,4,4,4] 2 * [1,3] = [1,1,3,3]
  • pembagian adalah hal yang tidak biasa: setiap n elemen yang sama dimasukkan ke dalam n tas yang sama, elemen yang tidak dapat membentuk n-grup tetap berada di dalam tas. Kembalikan salah satu dari n tas baru.
    [1,1,2,2,2] / 2 = [1,2] [1,2,2,3,3,3] / 3 = [3]
  • menghitung menghitung berapa banyak tas pembagi dapat diproduksi dari tas dividen
    [1,1,2,2,2,2,3,3,3] c [1,2,3] = 2
  • pemeriksaan kesetaraan memeriksa apakah dua kantung memiliki angka yang sama dari setiap elemen
    [1,2,2,3] == [3,2,1,2] = truthy [1,2,3] == [1,2,2,3] = falsy(dapat juga digunakan =untuk ini)

Jika Anda menggunakan simbol Anda sendiri untuk operator, silakan tentukan.

Format

Tas akan ditampilkan sebagai daftar formulir [1,1,2,3,4]. Anda dapat menggunakan braket lain selain yang persegi, atau bahkan menggunakan tanda kutip, atau tidak sama sekali. Elemen-elemen akan menjadi bilangan bulat (secara matematis, tidak harus int) untuk tujuan pertanyaan ini. Tas tidak harus disortir.

The format masukan akan dua tas atau tas dan integer, dengan operator. Anda dapat menentukan format Anda sendiri asalkan memuat tiga format ini.

The format output harus menjadi tas tunggal format yang sama.

Aturan

  • Anda tidak boleh menggunakan fungsi, operasi, atau perpustakaan bawaan (termasuk perpustakaan standar) yang sudah menerapkan ini; tidak apa-apa untuk menggunakan daftar concatenation dan multiplikasi karena mereka adalah operasi daftar definisi, bukan operasi tas (yang pada dasarnya melakukan hal yang sama)
  • celah standar berlaku
  • jawaban terpendek menang

Uji kasus

[1,2,2,3] + [1,2,4]
[1,1,2,2,2,3,4]

[1,2,2,4] - [1,2]
[2,4]

[1,2,3] - [2,4]
[1,3]

[1,2,3,3,4] * 3
[1,1,1,2,2,2,3,3,3,3,3,3,4,4,4]

2 * [1,3]
[1,1,3,3]

[1,1,2,2,2] / 2
[1,2]

[1,2,2,3,3,3] / 3
[3]

[1,1,2,2,2,2,3,3,3] c [1,2,3]
2

[3,2,1,2] == [1,2,2,3]
truthy

[1,2,3] == [1,2,2,3]
falsy
busukxuan
sumber
2
Mungkin bersantai format input? Misalnya memungkinkan untuk mengambil tas, tas / nomor, dan operator sebagai argumen terpisah, atau dalam format gratis. Kalau tidak, bagian penting dari tantangan adalah mengurai input, yang tidak terlalu menarik
Luis Mendo
@LuisMendo split-on-space sudah cukup untuk menguraikan ini, jika Anda memiliki bahasa yang dapat mengevaluasi string sebagai daftar sama sekali, bukan begitu? Saya tidak berpengalaman dalam memposting tantangan, jadi tolong beri tahu saya :-)
busukxuan
Saya tidak dapat menemukan posting meta yang relevan, tetapi lihat misalnya kata-katanya di sini : Anda dapat membaca integer sebagai representasi desimal, representasi unary (menggunakan karakter pilihan Anda), array byte (endian besar atau kecil) atau byte tunggal (jika ini adalah tipe data terbesar bahasa Anda) . Atau di sini : Format input dan output fleksibel seperti biasa (array, daftar, daftar daftar, string dengan pemisah yang masuk akal, dll ).
Luis Mendo
@LuisMendo pada dasarnya gratis sekarang. Dan tentang bilangan bulat, saya hanya bermaksud bahwa dalam pengertian matematika, bukan tipe data.
busukxuan
1
@LuisMendo tidak, simbol harus masuk akal, walaupun hanya sedikit. Nah, Anda bisa menggunakan satu = untuk uji kesetaraan.
busukxuan

Jawaban:

3

05AB1E, 92 87 83 82 77 byte

>i‚˜,}¹iи˜Qis}GD})˜,}¹<i³v²y¢O}){0è,}¹Íi{s{Q,}¹Í<iÙv²y¢O³‹_iy}}),}svy†¬yQi¦}}

Berpisah dengan operasi

>i                      # if 0
  ‚˜,}                  # addition
¹i                      # if 1
  и˜Qis}GD})˜,}        # multiplication
¹<i                     # if 2
   ³v²y¢O}){0è,}        # count
¹Íi                     # if 3
   {s{Q,}               # equality
¹Í<i                    # if 4
   Ùv²y¢O³÷Fy}}),}      # division
                        # else
   svy†¬yQi¦}}          # difference

Penjelasan

Tambahan

‚˜,}

Masukkan satu tas ke tas lain dan ratakan ke satu tas.

Perkalian

и˜Qis}

Pastikan angkanya ada di bagian atas tumpukan. Panggil ini X.

GD})˜,}

Gandakan tas X kali dan gabung ke satu tas.

Menghitung

³v²y¢O}){0è,}

Untuk setiap elemen dalam tas pembagi, hitung jumlah kejadian dalam tas dividen.
Hitungan minimum adalah jumlah tas yang bisa kita buat.

Persamaan

 {s{Q,}

Sortir kedua tas dan periksa apakah keduanya sama.

Divisi

Ùv²y¢O³÷Fy}}),}

Hitung berapa kali setiap elemen unik terjadi di tas.
Jika itu terjadi setidaknya sebanyak pembagi. Simpan salinan (nr_of_copies_total // divisor) di dalam tas.

Perbedaan

svy†¬yQi¦}} 

Untuk setiap elemen dalam subtrahend, urutkan ke bagian depan minuend.
Jika subtrahend saat ini jika sama dengan elemen pertama dalam minuend, hapus dari minuend.

Emigna
sumber
9

APL (155)

∆←{O←⍺⍺⋄'+'=O←⎕CR'O':R[⍋R←⍺,⍵]⋄'-'=O:⍺{⍵≡⍬:⍺⋄(⍺/⍨(⍳⍴⍺)≠⍺⍳⊃⍵)∇1↓⍵}⍵⋄(⍬≡⍴⍵)∧K←'×'=O:⍵/⍺⋄K:⍺/⍵⋄'÷'=O:∪⍺⌿⍨⍵≤+/⍺∘.=⍺⋄'⊂'=O:⍵{(∪⍺)≢∪⍵:0⋄1+⍺∇⍵-∆⍺}⍺⋄⍺[⍋⍺]≡⍵[⍋⍵]}⋄⎕

Ini mendefinisikan 'tas' operator , yang mendefinisikan operasi tas untuk fungsi yang diberikan. Yaitu +∆akan menjadi tambahan. Kemudian membaca baris dari keyboard dan mengevaluasinya sebagai ekspresi APL.

Fungsinya adalah:

  • +∆, tambahan
  • -∆, pengurangan
  • ×∆, penggandaan
  • ÷∆, pembagian
  • ⊂∆, menghitung
  • ≡∆, ekuivalensi (meskipun karena bermain golf fungsi apa pun yang tidak dikenali akan melakukan ekivalensi)

Penjelasan:

  • ∆←{... }: tentukan operator :

    • O←⍺⍺: menyimpan fungsi yang diberikan dalam O( ⎕CRtidak akan bekerja ⍺⍺secara langsung)
    • O←⎕CR'O': dapatkan representasi string dari fungsi itu
    • '+'=O... :: sebagai tambahan,
      • ⍺,⍵: gabungkan kedua daftar bersama
      • R[⍋R←... ]: dan urutkan hasilnya
    • '-'=O:: untuk pengurangan,
      • ⍺{... }⍵: jalankan fungsi rekursif berikut:
        • ⍵≡⍬:⍺: jika subtrahend kosong, kembalikan minuend
        • ⍺/⍨(⍳⍴⍺)≢⍺⍳⊃⍵∇1↓⍵: jika tidak, hapus elemen pertama dari subtrahend dari kedua subtrahend dan minuend dan coba lagi
    • (⍬=⍴⍵)∧K←'×'=O: untuk perkalian, dan jika argumen yang tepat bukan tas:
      • ⍵/⍺: mereplikasi setiap elemen dalam argumen kiri dengan argumen kanan
    • K:: ... dan jika argumen yang benar adalah tas:
      • ⍺/⍵: mereplikasi setiap elemen dalam argumen kanan dengan argumen kiri (ini adalah agar multiplikasi komutatif)
    • '÷'=O:: untuk divisi,
      • ⍵≤⍺∘.+⍺: lihat elemen mana di ⍺ yang muncul setidaknya ⍵ kali,
      • ⍺/⍨: pilih yang dari ⍺,
      • : dan hapus semua duplikat dari daftar itu
    • '⊂'=O:: untuk menghitung,
      • ⍵{... }⍺: jalankan fungsi rekursif berikut:
        • (∪⍺)≢∪⍵:0: jika satu daftar berisi elemen yang lain tidak, hasilnya adalah 0
        • 1+⍺∇⍵-∆⍺: jika tidak, kurangi dividen dari pembagi, coba lagi, dan tambahkan hasilnya.
    • : jika tidak ada yang di atas, lakukan tes kesetaraan:
      • ⍺[⍋⍺]≡⍵[⍋⍵]: urutkan kedua daftar dan lihat apakah keduanya sama
  • : membaca ekspresi dari keyboard, mengevaluasinya, dan mengeluarkan hasilnya.

Kasus uji:

      ∆←{O←⍺⍺⋄'+'=O←⎕CR'O':R[⍋R←⍺,⍵]⋄'-'=O:⍺{⍵≡⍬:⍺⋄(⍺/⍨(⍳⍴⍺)≠⍺⍳⊃⍵)∇1↓⍵}⍵⋄(⍬≡⍴⍵)∧K←'×'=O:⍵/⍺⋄K:⍺/⍵⋄'÷'=O:∪⍺⌿⍨⍵≤+/⍺∘.=⍺⋄'⊂'=O:⍵{(∪⍺)≢∪⍵:0⋄1+⍺∇⍵-∆⍺}⍺⋄⍺[⍋⍺]≡⍵[⍋⍵]}⋄⎕
⎕:
      1 2 2 3 +∆ 1 2 4
1 1 2 2 2 3 4
      ∆←{O←⍺⍺⋄'+'=O←⎕CR'O':R[⍋R←⍺,⍵]⋄'-'=O:⍺{⍵≡⍬:⍺⋄(⍺/⍨(⍳⍴⍺)≠⍺⍳⊃⍵)∇1↓⍵}⍵⋄(⍬≡⍴⍵)∧K←'×'=O:⍵/⍺⋄K:⍺/⍵⋄'÷'=O:∪⍺⌿⍨⍵≤+/⍺∘.=⍺⋄'⊂'=O:⍵{(∪⍺)≢∪⍵:0⋄1+⍺∇⍵-∆⍺}⍺⋄⍺[⍋⍺]≡⍵[⍋⍵]}⋄⎕
⎕:
      1 2 2 4 -∆ 1 2
2 4
      ∆←{O←⍺⍺⋄'+'=O←⎕CR'O':R[⍋R←⍺,⍵]⋄'-'=O:⍺{⍵≡⍬:⍺⋄(⍺/⍨(⍳⍴⍺)≠⍺⍳⊃⍵)∇1↓⍵}⍵⋄(⍬≡⍴⍵)∧K←'×'=O:⍵/⍺⋄K:⍺/⍵⋄'÷'=O:∪⍺⌿⍨⍵≤+/⍺∘.=⍺⋄'⊂'=O:⍵{(∪⍺)≢∪⍵:0⋄1+⍺∇⍵-∆⍺}⍺⋄⍺[⍋⍺]≡⍵[⍋⍵]}⋄⎕
⎕:
      1 2 3 -∆ 2 4
1 3
      ∆←{O←⍺⍺⋄'+'=O←⎕CR'O':R[⍋R←⍺,⍵]⋄'-'=O:⍺{⍵≡⍬:⍺⋄(⍺/⍨(⍳⍴⍺)≠⍺⍳⊃⍵)∇1↓⍵}⍵⋄(⍬≡⍴⍵)∧K←'×'=O:⍵/⍺⋄K:⍺/⍵⋄'÷'=O:∪⍺⌿⍨⍵≤+/⍺∘.=⍺⋄'⊂'=O:⍵{(∪⍺)≢∪⍵:0⋄1+⍺∇⍵-∆⍺}⍺⋄⍺[⍋⍺]≡⍵[⍋⍵]}⋄⎕
⎕:
      1 2 3 3 4 ×∆ 3
1 1 1 2 2 2 3 3 3 3 3 3 4 4 4
      ∆←{O←⍺⍺⋄'+'=O←⎕CR'O':R[⍋R←⍺,⍵]⋄'-'=O:⍺{⍵≡⍬:⍺⋄(⍺/⍨(⍳⍴⍺)≠⍺⍳⊃⍵)∇1↓⍵}⍵⋄(⍬≡⍴⍵)∧K←'×'=O:⍵/⍺⋄K:⍺/⍵⋄'÷'=O:∪⍺⌿⍨⍵≤+/⍺∘.=⍺⋄'⊂'=O:⍵{(∪⍺)≢∪⍵:0⋄1+⍺∇⍵-∆⍺}⍺⋄⍺[⍋⍺]≡⍵[⍋⍵]}⋄⎕
⎕:
      2 ×∆ 1 3
1 1 3 3
      ∆←{O←⍺⍺⋄'+'=O←⎕CR'O':R[⍋R←⍺,⍵]⋄'-'=O:⍺{⍵≡⍬:⍺⋄(⍺/⍨(⍳⍴⍺)≠⍺⍳⊃⍵)∇1↓⍵}⍵⋄(⍬≡⍴⍵)∧K←'×'=O:⍵/⍺⋄K:⍺/⍵⋄'÷'=O:∪⍺⌿⍨⍵≤+/⍺∘.=⍺⋄'⊂'=O:⍵{(∪⍺)≢∪⍵:0⋄1+⍺∇⍵-∆⍺}⍺⋄⍺[⍋⍺]≡⍵[⍋⍵]}⋄⎕
⎕:
      1 1 2 2 2 ÷∆ 2
1 2
      ∆←{O←⍺⍺⋄'+'=O←⎕CR'O':R[⍋R←⍺,⍵]⋄'-'=O:⍺{⍵≡⍬:⍺⋄(⍺/⍨(⍳⍴⍺)≠⍺⍳⊃⍵)∇1↓⍵}⍵⋄(⍬≡⍴⍵)∧K←'×'=O:⍵/⍺⋄K:⍺/⍵⋄'÷'=O:∪⍺⌿⍨⍵≤+/⍺∘.=⍺⋄'⊂'=O:⍵{(∪⍺)≢∪⍵:0⋄1+⍺∇⍵-∆⍺}⍺⋄⍺[⍋⍺]≡⍵[⍋⍵]}⋄⎕
⎕:
      1 2 2 3 3 3 ÷∆ 3
3
      ∆←{O←⍺⍺⋄'+'=O←⎕CR'O':R[⍋R←⍺,⍵]⋄'-'=O:⍺{⍵≡⍬:⍺⋄(⍺/⍨(⍳⍴⍺)≠⍺⍳⊃⍵)∇1↓⍵}⍵⋄(⍬≡⍴⍵)∧K←'×'=O:⍵/⍺⋄K:⍺/⍵⋄'÷'=O:∪⍺⌿⍨⍵≤+/⍺∘.=⍺⋄'⊂'=O:⍵{(∪⍺)≢∪⍵:0⋄1+⍺∇⍵-∆⍺}⍺⋄⍺[⍋⍺]≡⍵[⍋⍵]}⋄⎕
⎕:
      1 1 2 2 2 2 3 3 3 ⊂∆ 1 2 3
2
      ∆←{O←⍺⍺⋄'+'=O←⎕CR'O':R[⍋R←⍺,⍵]⋄'-'=O:⍺{⍵≡⍬:⍺⋄(⍺/⍨(⍳⍴⍺)≠⍺⍳⊃⍵)∇1↓⍵}⍵⋄(⍬≡⍴⍵)∧K←'×'=O:⍵/⍺⋄K:⍺/⍵⋄'÷'=O:∪⍺⌿⍨⍵≤+/⍺∘.=⍺⋄'⊂'=O:⍵{(∪⍺)≢∪⍵:0⋄1+⍺∇⍵-∆⍺}⍺⋄⍺[⍋⍺]≡⍵[⍋⍵]}⋄⎕
⎕:
      3 2 1 2 ≡∆ 1 2 2 3
1
      ∆←{O←⍺⍺⋄'+'=O←⎕CR'O':R[⍋R←⍺,⍵]⋄'-'=O:⍺{⍵≡⍬:⍺⋄(⍺/⍨(⍳⍴⍺)≠⍺⍳⊃⍵)∇1↓⍵}⍵⋄(⍬≡⍴⍵)∧K←'×'=O:⍵/⍺⋄K:⍺/⍵⋄'÷'=O:∪⍺⌿⍨⍵≤+/⍺∘.=⍺⋄'⊂'=O:⍵{(∪⍺)≢∪⍵:0⋄1+⍺∇⍵-∆⍺}⍺⋄⍺[⍋⍺]≡⍵[⍋⍵]}⋄⎕
⎕:
      1 2 3 ≡∆ 1 2 2 3
0
marinus
sumber
Solusi yang benar-benar profesional dan penulisan yang bagus! +1
Langgan dan penjelasan Anda benar-benar solid! Namun, satu hal: untuk pembagian, saya yakin spek itu ditulis dengan cara yang [2,2,2,2,2,2]/3seharusnya memberi [2,2], tetapi milik Anda tampaknya memberi [2].
Nilai Tinta
Anda tidak perlu kode REPL. Jika Anda baru saja mendefinisikan , pengguna akan dibuang ke REPL asli APL, di mana sekarang valid. Saya pikir Anda dapat menyimpan beberapa byte dengan memindahkan pengurangan sampai akhir karena itu adalah satu-satunya yang membutuhkan dua baris. Alih-alih ⎕CR, gunakan *untuk melambangkan hitungan, dan lakukan O←⍺⍺2, lalu 2=O:untuk plus, 1=Ountuk mult, 0=O:untuk equiv, 7<O:untuk menghitung, dan 0<O:untuk div (dengan tersirat 0>O:untuk subtr).
Adám
6

JavaScript (ES6), 260 byte

(x,o,y,a=a=>a.reduce((r,e,i)=>[...r,...Array(e).fill(i)],[]),b=(a,r=[])=>a.map(e=>r[e]=-~r[e])&&r)=>[z=>a(b(y,z)),z=>y.map(e=>z[e]&&z[e]--)&&a(z),z=>a(z.map(e=>e*y)),z=>a(z.map(i=>i/y|0)),z=>b(y).map((e,i)=>r=Math.min(r,z[i]/e),r=1/0)|r,z=>``+z==b(y)][o](b(x))

Membawa 3 parameter. Parameter pertama adalah array, yang kedua adalah operator, yang ketiga tergantung pada operator. Tas diminta untuk menyimpan bilangan bulat non-negatif.

[...] 0 [...] -> addition
[...] 1 [...] -> difference
[...] 2 <n> -> multiplication
[...] 3 <n> -> division
[...] 4 [...] -> counting
[...] 5 [...] -> equality

Tidak Terkumpul:

function do_bag_op(lhs, op, rhs) {
    function bag2array(bag) {
        return bag.reduce(function (result, entry, index) {
            return result.concat(Array(entry).fill(index));
        }, []);
    }
    function array2bag(array, bag) {
        if (!bag) bag = [];
        array.forEach(function (entry) {
            if (bag[entry]) bag[entry]++;
            else bag[entry] = 1;
        }
        return bag;
    }
    var bag = array2bag(lhs);
    switch (o) {
    case 0: // addition
        return bag2array(array2bag(rhs, bag));
    case 1: // difference
        rhs.forEach(function(entry) {
            if (bag[entry]) bag[entry]--;
        });
        return bag2array(bag);
    case 2: // multiplication
        return bag2array(bag.map(function (entry) {
            return entry * rhs;
        }));
    case 3: // division
        return bag2array(bag.map(function (entry) {
            return Math.floor(entry / rhs);
        }));
    case 4: // counting
        return Math.floor(array2bag(rhs).reduce(function (count, entry, index) {
            return Math.min(count, bag[index] / entry);
        }, Infinity));
    case 5: // equality
        return String(bag) == String(array2bag(rhs));
    }
}
Neil
sumber
6

Oktaf, 253 244 226 byte

function r=f(a,b,o)
u=union(a,b);p=hist(a,u);q=hist(b,u);m=d=0;if(numel(b)==1)m=p.*b;d=p/b;elseif(numel(a)==1)m=a.*q;end
r={p+q,p-q,m,d,min(fix(p./q)),isequal(p,q)}{o};if(o<5)r=[arrayfun(@(x,y)repmat(y,1,x),r,u,'un',0){:}];end

Fungsi ini harus ada dalam file. Untuk menulis fungsi di jendela perintah, Anda harus menggunakan endfunctionatau end.

Terima kasih kepada Luis Mendo karena telah menghemat 18 byte.

Operasi adalah:

1 = addition
2 = difference
3 = multiplication
4 = division
5 = counting
6 = equality test

Contoh penggunaan:

>> f([1,2,2,3], [1,2,4], 1)
ans = 1   1   2   2   2   3   4

>> f([1,2,2,4], [1,2], 2)
ans = 2   4

>> f([1,2,3], [2,4], 2)
ans = 1   3

>> f([1,2,3,3,4], 3, 3)
ans = 1   1   1   2   2   2   3   3   3   3   3   3   4   4   4

>> f(2, [1,3], 3)
ans = 1   1   3   3

>> f([1,1,2,2,2], 2, 4)
ans = 1   2

>> f([1,2,2,3,3,3], 3, 4)
ans =  3

>> f([1,1,2,2,2,2,3,3,3], [1,2,3], 5)
ans =  2

>> f([3,2,1,2], [1,2,2,3], 6)
ans =  1

>> f([1,2,3], [1,2,2,3], 6)
ans = 0

Tidak Terkumpul:

function r = f(a,b,o)
    u = union(a,b);
    p = hist(a,u);
    q = hist(b,u);
    m = d = 0;
    if (numel(b)==1)
        m = p.*b;
        d = p/b;
    elseif (numel(a)==1) 
        m = a.*q;
    end
    r = {p+q, p-q, m, d, min(fix(p./q)), isequal(p,q)}{o};
    if (o<5)
        r = [arrayfun(@(x,y) repmat(y, 1, x), r, u, 'un', 0){:}];
    end
end
Marco
sumber
5

Mathematica, 387 347 300 284 byte

k=KeyValueMap[Table,#]&;j=b@@Join@@#&;l=List;q=Counts
b~SetAttributes~Orderless
a_b+c_b^:=j@{a,c}
c_b-a_b^:=j@k@Merge[q/@(l@@@{a+c,2a}),-Min[0,+##2-#]&@@#&]
a_b*n_Integer/;n>0^:=a+a*(n-1)
a_Rational c_b^:=j@k[⌊a#⌋&/@q@*l@@c]
a_b==d_b^:=l@@a==l@@d
c_b/a_b^:=If[(c-a)+a==c,1+(c-a)/a,0]

Degolfed sedikit (alias versi lama), tidak memiliki dukungan penuh untuk tes kesetaraan (mengembalikan nilai-nilai kebenaran, tetapi dibiarkan tidak dievaluasi untuk tas yang tidak cocok).

SetAttributes[b,Orderless]
b/:-a_b:=d@@a
b/:a_b+c_b:=Join[a,c]
d/:a_b+c_d:=b@@Join@@KeyValueMap[Table,Merge[Counts/@(List@@@{a+b@@c,b@@c+b@@c}),Max[0,#-(+##2)]&@@#&]]
b/:Rational[1,a_]c_b:=b@@Join@@KeyValueMap[Table,Floor[#/a]&/@Counts@*List@@c]
b/:(a_b)^-1:=c@@a
c/:a_b d_c:=Min@Merge[Counts/@(List@@@{a,d}),If[+##2==0,\[Infinity],#/+##2]&@@#&]
b/:a_b*n_Integer:=a+a*(n-1)

Menerapkan tipe data yang diperlukan dengan kepala b.

Pertama bdidefinisikan sebagai Orderless. Setiap objek yang diteruskan ke kernel dengan head bakan melakukan autosort argumennya. Jadi, bahkan jika b[3,2,1]diketik, evaluator tidak akan pernah melihat selain b[1,2,3].

Penambahan sepele didefinisikan sebagai bergabung dengan elemen.

Aturan khusus untuk perbedaan dua kantong didefinisikan (dijelaskan di bawah). Versi sebelumnya memiliki simbol bantu untuk ekspresi bentuk -bag.

Kemudian perkalian (selama nbilangan bulat positif) secara rekursif didefinisikan sebagai n*b[...] = b[...] + (n-1)*b[...]yang pada akhirnya akan berkurang menjadi jumlah sederhana.

Aturan khusus untuk b[...] - b[...]menghitung jumlah elemen berbeda dalam jumlah kantung dan mengurangi kantung yang akan dikurangkan dua kali dari hasil itu. Lebih mudah dijelaskan:

b[1,2,3,4,5] - b[2,3,6]
Element counts in sum of bags: <|1->1, 2->2, 3->2, 4->1, 5->1, 6->1|>
Element counts in 2x second bag:     <|2->2, 3->2, 6->2|>
Subtracting the corresponding values:
                               <|1->1, 2->0, 3->0, 4->1, 5->1, 6->-1|>

Di atas adalah daftar Keys->Values. KeyValueMapdengan Tablemembuat daftar setiap Key Valuekali. (Ada juga di Max[...,0]sana untuk tidak mencoba membuat tabel panjang negatif). Ini muncul sebagai:

{{1},{},{},{4},{5},{}}

yang diratakan dan kepala Listdiganti dengan b.

Pembagian dengan bilangan bulat agak mirip dalam fungsi yang digunakan, itu hanya pembagian lantai elemen dihitung oleh bilangan bulat.

Pembagian dengan menetapkan atau menghitung Saya telah berubah sejak implementasi awal. Sekarang secara rekursif dilakukan sebagai berikut. Katakanlah, kita membagi tas b1dengan b2(yang dalam kode golf adalah cdan amasing - masing. Jika (b1-b2) + b2 == b1, kemudian tambahkan 1 dan tambahkan ke hasil pembagian (b1-b2)/b2. Jika tidak, kembalikan 0 dan keluar dari rekursi.

Jika tas cocok, built-in ==memberi True. Baris terakhir memaksa a Falsejika tidak.

Kasus uji:

Input:
b[1, 2, 2, 3] + b[1, 2, 4]
b[1, 2, 2, 4] - b[1, 2]
b[1, 2, 3] - b[2, 4]
b[1, 2, 3, 3, 4]*3
2*b[1, 3]
b[1, 1, 2, 2, 2]/2
b[1, 2, 2, 3, 3, 3]/3
b[1, 1, 2, 2, 2, 2, 3, 3, 3] /b[1, 2, 3]
b[3, 2, 1, 2] == b[1, 2, 2, 3]
b[1, 2, 3] == b[1, 2, 2, 3]

Output:
b[1, 1, 2, 2, 2, 3, 4]
b[2, 4]
b[1, 3]
b[1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 4, 4]
b[1, 1, 3, 3]
b[1, 2]
b[3]
2
True
False
LLlAMnYP
sumber
2

Q - 219 karakter

a:(,)
s:{[x;y]x((!:)(#:)x)except(,/)({.[(#);x]}')flip(7h$(({(+/)x=y}[y]')(?:)y);(({where x=y}[x]')y))}
m:{(,/)$[0>(@:)x;(#[x]')y;(#[y]')x]}
d:{(?:)x(&:)({y<=(+/)x=z}[x;y]')x}
c:{min({(+/)x=y}[x]')y}
e:{(asc x)~asc y}

auntuk tambahan, suntuk perbedaan (pengurangan), muntuk perkalian, duntuk pembagian, cuntuk penghitungan, euntuk kesetaraan.

Algoritma penjumlahan adalah yang jelas, hanya bergabung dengan tas.

Indeks fungsi pengurangan dalam kantong input (direpresentasikan sebagai sebuah array) dengan seluruh rentang indeks, kecuali untuk nindeks pertama dari setiap kelas ekivalensi yang dibentuk oleh kesetaraan untuk setiap elemen di y, di mana njumlah salinan perwakilan itu di y. Menangani kemungkinan duplikat ymenjadikannya monster fungsi yang nyata.

Fungsi multiplikasi mengambil xnilai dari masing-masing y, dalam hal ini yadalah nilai tunggal, bukan array, itu hanya mereplikasi mereka.

Fungsi pembagian menghasilkan nilai yang jumlah dalam array lebih besar dari y, dan kemudian menghapus duplikat.

Fungsi penghitungan menghitung jumlah setiap elemen di y, dan kemudian mengembalikan minimum.

Dua tas sama jika representasi array yang diurutkan sama.

C. Quilley
sumber
2

Ruby, jawaban definisi kelas, 323 291 byte

Sebagian besar hanya ingin membuat Bagkelas yang sebenarnya karena fleksibilitas Ruby dengan kelas. Dalam hal ini, ia diturunkan dari Arraykarena lebih pendek daripada harus menginisialisasi array internal dan berurusan dengan hal-hal lain.

Saya mungkin akan melakukan jawaban golf yang lebih serius yang menggunakan fungsi untuk menangani operasi besok. Saya sangat lelah dan saya terlalu bersenang-senang dengan ini walaupun saya harus bertengkar dengan definisi kelas numerik untuk dapat Number * Bagbekerja dengan baik. MEMUJI FUNGSI KERJA UNTUK MEMBUATNYA, SAYA TIDAK PERLU MESS UP NUMERICS DEFINISI KELAS

Cobalah online! (Whitespace tidak masalah di Ruby, jadi kodenya sedikit tidak diubah di sana.)

class B<Array
def == o
sort==o.sort
end
def + o
B.new super
end
def - o
r=to_a
o.map{|i|r[r.index(i)||size]=p}
B.new r-[p]
end
def * i
B.new super
end
def / i
B.new uniq.map{|o|[o]*(count(o)/i)}.flatten
end
def c o
o.map{|i|count i}.min
end
def inspect
sort
end
def coerce o
[self,o]
end
end
Nilai Tinta
sumber
1

Ruby, 201 byte

Seperti yang dijanjikan dalam jawaban saya yang lain, inilah yang menggunakan fungsi alih-alih membangun kelas baru. Saya sangat dekat dengan melanggar tanda 200 byte ... Cobalah online

Ini menggunakan opcode yang sama dengan @Neil dalam jawaban JavaScript-nya, dan urutan argumen yang sama (lhs, opcode, rhs)

0: Addition
1: Difference
2: Multiplication
3: Division
4: Counting
5: Equality

Kode:

->x,o,y{[->{(x+y).sort},->r=[*x]{y.map{|i|r[r.index(i)||x.size]=p};r-[p]},->{(x==[*x]?x*y :y*x).sort},->{x.uniq.map{|i|[i]*(x.count(i)/y)}.flatten},->{y.map{|i|x.count i}.min},->{x.sort==y.sort}][o][]}
Nilai Tinta
sumber
1

C ++, 555 551 byte

(jeda baris ditambahkan untuk dibaca - hanya baris baru pertama yang diperlukan dan dihitung)

#include<map>
struct B:std::map<int,int>{
B(std::initializer_list<int>l){for(auto i:l)++(*this)[i];}};
B operator+(B a,B b){for(auto m:b)a[m.first]+=m.second;return a;}
B operator-(B a,B b){for(auto m:b){int&x=a[m.first];x-=x>m.second?m.second:x;if(!x)a.erase(m.first);};return a;}
B operator*(B b,int n){for(auto m:b)b[m.first]*=n;return b;}
B operator*(int n,B b){return b*n;}
B operator/(B b,int n){for(auto m:b)if(!(b[m.first]/=n))b.erase(m.first);return b;}
int operator/(B a,B b){auto r=~0u;for(auto m:b){int x=a[m.first]/m.second;r=r>x?x:r;}return r;}

Penjelasan

Kami menerapkan tas kami sebagai peta (nilai, jumlah). Operasi dasar dapat diimplementasikan dengan memanipulasi penghitungan; divisi pengurangan dan bilangan bulat juga harus menghapus elemen apa pun yang hitungannya mencapai nol, sehingga std::map::operator==akan berfungsi sebagai tes kesetaraan.

Kode yang diperluas berikut adalah versi generik dari yang di atas, apalagi golf: kami menggunakan terpisah s()untuk memeras nilai hitungan nol, dan kami menerapkan constoperasi dalam hal penugasan operator dengan cara C ++ idiomatik. Kami juga menggunakan s()untuk membuat perkalian dengan 0kembali tas yang benar-benar kosong (diuji dengan menambahkan (B{1}*0 != B{})ke main()); aslinya gagal dalam tes ini, dan tidak jelas apakah ini merupakan persyaratan.

template<class T>
struct Bag{
    std::map<T,int>b;
    Bag(const std::initializer_list<T>& l){for(auto i:l)++b[i];}
    Bag&s(){for(auto i=b.begin();i!=b.end();i=i->second?++i:b.erase(i));return*this;}
    Bag&operator+=(const Bag& o){for(auto m:o.b)b[m.first]+=m.second;return*this;}
    Bag&operator-=(const Bag& o){for(auto m:o.b){auto&x=b[m.first];x-=x>m.second?m.second:x;}return s();}
    Bag&operator*=(int n){for(auto m:b)b[m.first]*=n;return s();}
    Bag&operator/=(int n){for(auto m:b)b[m.first]/=n;return s();}
    auto operator/=(const Bag& o){auto r=~0u;for(auto m:o.b){int x=b[m.first]/m.second;r=r>x?x:r;}return r;}
    bool operator==(const Bag& o)const{return b==o.b;}

    Bag operator+(Bag o)const{return o+=*this;}
    Bag operator-(const Bag& o)const{Bag t=*this;return t-=o;}
    Bag operator*(int n)const{Bag t=*this;return t*=n;}
    friend Bag operator*(int n,const Bag& b){return b*n;}
    auto operator/(auto n)const{Bag t=*this;return t/=n;}
    bool operator!=(const Bag& o)const{return b!=o.b;}
};

using B = Bag<int>;

Tes

bool operator!=(B a,B b){return!(a==b);}
int main()
{
    return 0
        + (B{1,2,2,3}+B{1,2,4}  !=  B{1,1,2,2,2,3,4})
        + (B{1,2,2,4}-B{1,2}  !=  B{2,4})
        + (B{1,2,3}-B{2,4}  !=  B{1,3})
        + (B{1,2,3,3,4}*3  !=  B{1,1,1,2,2,2,3,3,3,3,3,3,4,4,4})
        + (2*B{1,3}  !=  B{1,1,3,3})
        + (B{1,1,2,2,2}/2  !=  B{1,2})
        + (B{1,2,2,3,3,3}/3  !=  B{3})
        + (B{1,1,2,2,2,2,3,3,3}/B{1,2,3} != 2)
        + (B{3,2,1,2}  !=  B{1,2,2,3})
        + (B{1,2,3}  ==  B{1,2,2,3})
        ;
}
Toby Speight
sumber
Jawaban bagus! +1. Kode Anda membutuhkan pemformatan yang tepat dalam posting.
Yytsi
Saya sengaja ingin membungkus kode, sehingga Anda dapat melihat semuanya. Alternatifnya adalah menambahkan jeda baris.
Toby Speight
1
Jeda baris ditambahkan - Saya pikir ini lebih baik, karena prettify sekarang berfungsi.
Toby Speight
1

Python 2.7 - 447B (filesize)

Ini adalah percobaan pertama saya di Codegolf, saya harap ini memuaskan. Saya membutuhkan 2 jam. (Tapi saya masih pemula di Python)

Sunting: Terima kasih kepada "Kevin Lau - not Kenny" karena menunjukkan ini:

  • Argumen diri ular sanca dalam suatu kelas dapat digantikan oleh apa saja
  • lekukan hanya harus berupa ruang tunggal
  • builtin diurutkan - funktion (saya tahu saya telah melihatnya, tapi saya pikir itu adalah metode dalam daftar)
  • __ radd __ tidak diperlukan (saya hanya mendukung penambahan objek-B (tipe-Tas))

Sunting: Selain itu saya menghemat ruang dengan mengganti fungsi dengan lambdas dan baris baru dan lekukan dengan lebih banyak titik koma.

Kode:

class B:
 def __init__(S,L=[]):S.L=sorted(list(L));S.p=lambda:[[i]*S.L.count(i)for k,i in enumerate(S.L)if i!=S.L[k-1]];S.__eq__=lambda o:S.L==o.L;S.__rmul__=S.__mul__=lambda o:B(S.L*o);S.__add__=lambda o:B(S.L+o.L);S.__sub__=lambda o:B([i for k in S.p()for i in k[:max(0,S.L.count(k[0])-o.L.count(k[0]))]]);S.__div__=lambda o:B([i for k in S.p()for i in k[::o][:[-1,None][len(k)%o==0]]]);S.c=lambda o:min([S.L.count(i)//o.L.count(i)for i in o.L])

memeriksa:

print B([1,2,2,3]) + B([1,2,4]) == B([1,1,2,2,2,3,4]) # Add

print B([1,2,2,4]) - B([1,2]) == B([2,4]) #Substract
print B([1,2,3])   - B([2,4]) == B([1,3]) #Substract

print B([1,2,3,3,4]) * 3 == B([1,1,1,2,2,2,3,3,3,3,3,3,4,4,4])#Multiply
print 2 * B([1,3]) == B([1,1,3,3])                            #

print B([1,1,2,2,2])   /2 == B([1,2]) #Divide
print B([1,2,2,3,3,3]) /3 == B([3])   #

print B([1,1,2,2,2,2,3,3,3]).c(B([1,2,3]))==2 #Contained n times

print B([3,2,1,2]) == B([1,2,2,3]) # Equal
print B([1,2,3])   == B([1,2,2,3]) # Unequal

Keluaran:

True
True
True
True
True
True
True
True
True
False

Saya mungkin mencobanya lain kali dengan menetapkan sebagai dasar waktu. Sunting: Mungkin saya akan mencoba dengan fungsi saja.

Teck-freak
sumber
Selamat datang di PPCG! Satu hal yang perlu diperhatikan tentang Python adalah Anda sebenarnya tidak perlu memanggil parameter pertama dalam fungsi kelas self- sesuatu seperti Sakan dilakukan juga. Trik lain adalah bahwa sortedfungsi bawaan melakukan apa yang Anda inginkan dari fungsi baru Anda s, sehingga Anda dapat melupakan definisi fungsi (mengingat Anda hanya menggunakannya sekali). Anda tidak pernah perlu __radd__karena Anda tidak pernah menambahkan tas dengan tas, meskipun Anda masih membutuhkannya __rmul__. Akhirnya, Anda hanya perlu satu spasi indentasi alih-alih empat, yang memangkas jumlah byte Anda sedikit
Value Ink