Wdrażaj operacje workowe

20

Worek , zwany także multiset, to nieuporządkowana kolekcja. Możesz nazwać to zestawem, który pozwala na duplikaty, lub listą (lub tablicą), która nie jest uporządkowana / indeksowana. W tym wyzwaniu zostaniesz poproszony o wdrożenie operacji worka: test dodawania, różnicy, mnożenia, dzielenia, liczenia i równości.

Operacje

Określone operacje mogą nie być konwencjonalne.

  • dodatek łączy dwie torby w jedną, zachowując całkowitą liczbę każdej wartości
    [1,2,2,3] + [1,2,4] = [1,1,2,2,2,3,4]
  • różnica usuwa z torby każdy element innej torby lub nic nie robi, jeśli nie ma takiego elementu
    [1,2,2,4] - [1,2] = [2,4] [1,2,3] - [2,4] = [1,3]
  • mnożenie zwielokrotnia każdy element w torbie.
    [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]
  • podział jest rzadki: każdy n równych elementów umieszcza się w n równych nowych torbach, elementy, które nie mogą utworzyć grupy n, pozostają w torbie. Zwróć jedną z n nowych toreb.
    [1,1,2,2,2] / 2 = [1,2] [1,2,2,3,3,3] / 3 = [3]
  • liczenie liczy, ile worków dzielnika można wyprodukować z worka dywidendy
    [1,1,2,2,2,2,3,3,3] c [1,2,3] = 2
  • test równości sprawdza, czy dwie torby mają taką samą liczbę każdego elementu
    [1,2,2,3] == [3,2,1,2] = truthy [1,2,3] == [1,2,2,3] = falsy(można =do tego również użyć )

Jeśli używasz własnych symboli dla operatorów, proszę podać.

Formaty

Torby będą wyświetlane jako listy formularza [1,1,2,3,4]. Możesz użyć dowolnego nawiasu kwadratowego, a nawet cudzysłowów lub nic. intDla celów tego pytania elementy będą liczbami całkowitymi (matematycznie, niekoniecznie ). Torby nie muszą być sortowane.

Format wejściowy będzie dwie torby lub worka, a oznacza liczbę całkowitą, z operatorem. Możesz określić własny format, o ile zawiera on te trzy.

Format powinien być pojedynczy torba z tym samym formacie.

Zasady

  • nie możesz używać wbudowanych funkcji, operacji lub bibliotek (w tym biblioteki standardowej), które już je implementują; można jednak stosować łączenie i mnożenie listy, ponieważ są one z definicji operacjami na liście, a nie operacjami workowania (które w zasadzie robią to samo)
  • obowiązują standardowe luki
  • najkrótsza odpowiedź wygrywa

Przypadki testowe

[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
źródło
2
Może złagodzić format wejściowy? Na przykład pozwól wziąć torbę, torbę / numer i operatora jako osobne argumenty lub w dowolnym formacie. W przeciwnym razie ważną częścią wyzwania jest analiza danych wejściowych, co nie jest szczególnie interesujące
Luis Mendo
@LuisMendo split-on-space jest wystarczające, aby to przeanalizować, jeśli masz język, który może w ogóle oceniać łańcuchy jako listy, nie sądzisz? Nie mam doświadczenia w publikowaniu wyzwań, więc proszę, oświeć mnie :-)
busukxuan,
Nie mogłem znaleźć odpowiedniego meta postu, ale zobaczmy na przykład sformułowanie tutaj : możesz odczytać liczbę całkowitą jako jej dziesiętną reprezentację, jednoargumentową (przy użyciu wybranego znaku), tablicę bajtów (duży lub mały endian) lub pojedynczy bajt (jeśli jest to największy typ danych w Twoim języku) . Lub tutaj : formaty wejściowe i wyjściowe są jak zwykle elastyczne (tablice, listy, lista list, ciągi znaków z rozsądnymi separatorami itp .).
Luis Mendo,
@LuisMendo jest teraz w zasadzie darmowy. Mówiąc o liczbie całkowitej, miałem na myśli, że w sensie matematycznym, a nie typ danych.
busukxuan
1
@LuisMendo nie, symbole muszą mieć sens, nawet jeśli tylko trochę. Cóż, możesz użyć jednego = do testu równości.
busukxuan

Odpowiedzi:

3

05AB1E, 92 87 83 82 77 bajtów

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

Podziel według operacji

>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

Wyjaśnienie

Dodanie

‚˜,}

Umieść jedną torebkę w drugiej i spłaszcz je do jednej torebki.

Mnożenie

и˜Qis}

Upewnij się, że liczba znajduje się na górze stosu. Nazwij to X.

GD})˜,}

Duplikuj torbę X razy i dołącz do jednej torby.

Liczyć

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

Dla każdego elementu w worku z dzielnikiem policz liczbę wystąpień w worku z dywidendą.
Minimalna liczba to liczba worków, które możemy wykonać.

Równość

 {s{Q,}

Posortuj obie torby i sprawdź, czy są równe.

Podział

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

Policz, ile razy każdy unikalny element występuje w torbie.
Jeśli występuje co najmniej tyle razy, co dzielnik. Zachowaj kopie (nr_of_copies_total // divisor) w torbie.

Różnica

svy†¬yQi¦}} 

Dla każdego elementu w subtrahend, posortuj go na przód minuend.
Jeśli bieżący poddźwięk jest równy pierwszemu elementowi w menu, usuń go z menu.

Emigna
źródło
9

APL (155)

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

To definiuje „torbę” operatora , która definiuje operacje worka dla danych funkcji. To znaczy+∆ Byłby dodatkiem. Następnie odczytuje wiersz z klawiatury i ocenia go jako wyrażenie APL.

Funkcje to:

  • +∆, dodatek
  • -∆, odejmowanie
  • ×∆, mnożenie
  • ÷∆, podział
  • ⊂∆, licząc
  • ≡∆, równoważność (choć ze względu na grę w golfa dowolna nierozpoznana funkcja wykona równoważność)

Wyjaśnienie:

  • ∆←{... }: zdefiniuj operatora :

    • O←⍺⍺: zapisz daną funkcję w O( ⎕CRnie będzie działać ⍺⍺bezpośrednio)
    • O←⎕CR'O': pobierz ciąg reprezentujący tę funkcję
    • '+'=O... :: do dodania,
      • ⍺,⍵: połącz obie listy razem
      • R[⍋R←... ]: i posortuj wynik
    • '-'=O:: do odejmowania,
      • ⍺{...}⍵ : uruchom następującą funkcję rekurencyjną:
        • ⍵≡⍬:⍺: jeśli subtrahend jest pusty, zwróć minuend
        • ⍺/⍨(⍳⍴⍺)≢⍺⍳⊃⍵∇1↓⍵: w przeciwnym razie usuń pierwszy element subtrahend z subtrahend i minuend i spróbuj ponownie
    • (⍬=⍴⍵)∧K←'×'=O: do mnożenia i jeśli właściwy argument nie jest torbą:
      • ⍵/⍺: skopiuj każdy element w lewym argumencie przez prawy argument
    • K:: ... a jeśli właściwym argumentem jest torba:
      • ⍺/⍵: replikuj każdy element w prawym argumencie przez lewy argument (jest to tak, że mnożenie jest przemienne)
    • '÷'=O:: dla podziału,
      • ⍵≤⍺∘.+⍺: zobacz, które elementy w ⍺ występują co najmniej ⍵ razy,
      • ⍺/⍨: wybierz te z ⍺,
      • : i usuń wszystkie duplikaty z tej listy
    • '⊂'=O:: do liczenia,
      • ⍵{...}⍺ : uruchom następującą funkcję rekurencyjną:
        • (∪⍺)≢∪⍵:0: jeśli jedna lista zawiera elementy, a druga nie, wynik to 0
        • 1+⍺∇⍵-∆⍺: w przeciwnym razie odejmij dywidendę od dzielnika, spróbuj ponownie i zwiększ wynik.
    • : jeśli żaden z powyższych, nie wykonaj testu równoważności:
      • ⍺[⍋⍺]≡⍵[⍋⍵]: posortuj obie listy i sprawdź, czy są równe
  • : przeczytaj wyrażenie z klawiatury, oceń je i wyślij wynik.

Przypadki testowe:

      ∆←{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
źródło
Naprawdę profesjonalne rozwiązanie i świetny opis! +1
Twój opis i wyjaśnienie jest naprawdę solidne! Jedna rzecz: w przypadku podziału uważam, że specyfikacja jest sformułowana w sposób, który [2,2,2,2,2,2]/3powinien dać [2,2], ale twój wydaje się dawać [2].
Wartość tuszu
Nie musisz kodować REPL. Jeśli tylko zdefiniujesz , użytkownik zostanie zrzucony do natywnej REPL APL, gdzie jest teraz poprawny. Myślę, że możesz zaoszczędzić kilka bajtów, przesuwając odejmowanie do końca, ponieważ jest to jedyny, który wymaga dwóch linii. Zamiast ⎕CR, użyj, *aby symbolizować liczenie, i wykonaj O←⍺⍺2, a następnie 2=O:dla plus, 1=Odla mult, 0=O:dla equiv, 7<O:dla count i 0<O:dla div (z implikacją 0>O:dla subtr).
Adám
6

JavaScript (ES6), 260 bajtów

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

Zajmuje 3 parametry. Pierwszy parametr to tablica, drugi to operator, trzeci zależy od operatora. Torby są potrzebne do przechowywania liczb całkowitych nieujemnych.

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

Nie golfowany:

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
źródło
6

Oktawa, 253 244 226 bajtów

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

Ta funkcja musi znajdować się w pliku. Aby zapisać funkcję w oknie poleceń, musisz użyć endfunctionlub end.

Podziękowania dla Luisa Mendo za zaoszczędzenie 18 bajtów.

Operacje to:

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

Przykład użycia:

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

Nie golfowany:

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
źródło
5

Matematyka, 387 347 300 284 bajty

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]

Nieznacznie zdezelowany (czyli stara wersja), nie miał pełnego wsparcia dla testów równości (zwrócił prawdziwe wartości, ale pozostawił nieocenione dla niepasujących toreb).

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)

Implementuje wymagany typ danych za pomocą head b.

Pierwsza bjest zdefiniowana jako Orderless. Każdy obiekt przekazany do jądra z head bautomatycznie posortuje swoje argumenty. Więc nawet jeśli b[3,2,1]zostanie wpisany, oceniający nigdy nie zobaczy niczego innego b[1,2,3].

Dodawanie jest trywialnie zdefiniowane jako łączenie elementów.

Określono specjalną zasadę dotyczącą różnicy między dwoma workami (wyjaśniono poniżej). Poprzednia wersja miała symbol pomocniczy dla wyrażeń formy -bag.

Następnie mnożenie (tak długo, jak długo njest liczbą całkowitą dodatnią) jest rekurencyjnie definiowane jako, n*b[...] = b[...] + (n-1)*b[...]które ostatecznie zredukuje się do prostej sumy.

Specjalna reguła dla b[...] - b[...]zlicza liczbę odrębnych elementów w sumie worków i odejmuje torbę, która ma zostać odjęta dwukrotnie od tego wyniku. Łatwiej wyjaśniono:

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

Powyżej znajduje się lista Keys->Values. KeyValueMapz Tabletworzy listy za każdym Key Valuerazem. (istnieje również Max[...,0]możliwość nie tworzenia tabel o ujemnej długości). Wydaje się to jako:

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

który jest spłaszczony, a głowa Listzastąpiona przez b.

Podział według liczb całkowitych jest nieco podobny w użytych funkcjach, jest to po prostu dzielony podział elementu zliczony przez liczbę całkowitą.

Dzielenie według zbiorów lub liczenie Zmieniłem od czasu oryginalnej implementacji. Odbywa się to teraz rekurencyjnie w następujący sposób. Powiedzmy, dzielimy torbę b1przez b2(które w kodzie golfowym są cia odpowiednio. W przypadku (b1-b2) + b2 == b1, a następnie dodanie 1 i dodać do tego w wyniku podziału (b1-b2)/b2. Jeżeli nie, to zwraca 0 i wyjście rekursji.

Jeśli torby pasują, wbudowany ==dajeTrue . Ostatnia linia wymusza „a”, Falsejeśli nie.

Przypadki testowe:

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
LLAMAMYP
źródło
2

Q - 219 znaków

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}

ado dodania, sdla różnicy (odejmowania), mdo mnożenia, ddo dzielenia,c dla liczenia, edla równości.

Algorytm dodawania jest oczywisty, wystarczy połączyć torby.

Funkcja odejmowania indeksuje w torbie wejściowej (reprezentowanej jako tablica) z całym zakresem indeksów, z wyjątkiem pierwszych nindeksów każdej klasy równoważności utworzonych przez równość z każdym elementem w y, gdzie njest liczba kopii tego reprezentanta w y. Obsługa możliwych duplikatów ysprawia, że ​​jest to prawdziwy potwór funkcji.

Funkcja mnożenia pobiera xwartości z każdego z nich y, w przypadku, gdy yjest to pojedyncza wartość, zamiast tablicy, po prostu je replikuje.

Funkcja podziału generuje wartości, których liczba w tablicy jest większa niż y, a następnie usuwa duplikaty.

Funkcja zliczania oblicza liczbę każdego elementu y, a następnie zwraca minimum.

Dwie torby są równe, jeśli ich reprezentacje w sortowanej tablicy są równe.

C. Quilley
źródło
2

Ruby, odpowiedź na definicję klasy, 323 291 bajtów

Przede wszystkim chciałem stworzyć Bagprawdziwą klasę ze względu na elastyczność Ruby w stosunku do klas. W tym przypadku dziedziczy po, Arrayponieważ jest krótszy niż konieczność inicjowania wewnętrznej tablicy i radzenia sobie z innymi rzeczami.

Prawdopodobnie zrobię poważniejszą odpowiedź na golfa, która wykorzystuje funkcję do radzenia sobie z operacjami jutro. Jestem bardzo zmęczony i bawiłem się z tym zbyt dobrze, mimo że musiałem wdawać się w definicję klasyNumber * Bag numerycznej, aby działać poprawnie WYRAŻAJ FUNKCJĘ WYSOKOŚCI, ABY ZROBIĆ TO, ABY NIE POTRZEBOWAŁO POMYŚLENIA DEFINICJI KLASY NUMERYCZNEJ

Wypróbuj online! (Białe znaki nie mają znaczenia w Ruby, więc kod jest tam nieco nieoznaczony.)

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
Wartość tuszu
źródło
1

Ruby, 201 bajtów

Jak obiecałem w mojej drugiej odpowiedzi, oto jedna, która używa funkcji zamiast budowania nowej klasy. Jestem tak blisko przekroczenia znaku 200 bajtów ... Wypróbuj online

Wykorzystuje to te same kody jak @Neil w odpowiedzi na JavaScript i tę samą kolejność argumentów (lhs, opcode, rhs)

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

Kod:

->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][]}
Wartość tuszu
źródło
1

C ++, 555 551 bajtów

(dodano podział wierszy dla czytelności - wymagany i liczony jest tylko pierwszy znak nowej linii)

#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;}

Wyjaśnienie

Wdrażamy naszą torbę jako mapę (wartości, liczby). Podstawowe operacje można wdrożyć, manipulując licznikami; odejmowanie i dzielenie liczb całkowitych również muszą usuwać wszystkie elementy, których liczba osiąga zero, aby std::map::operator==działało to jako test równości.

Poniższy rozszerzony kod jest ogólną wersją powyższego, o wiele mniej golfa: używamy osobnego s()do wyciskania wartości zerowych i implementujemy constoperacje w zakresie operatorów przypisania w idiomatyczny sposób C ++. Używamy również s()do pomnożenia przez 0zwrócenie naprawdę pustej torby (testowane przez dodanie (B{1}*0 != B{})domain() ); oryginał nie przejdzie tego testu i nie jest jasne, czy jest to wymóg.

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

Testy

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
źródło
Niezła odpowiedź! +1. Twój kod wymaga odpowiedniego formatowania w poście.
Yytsi
Celowo chciałem, żeby kod się zawinął, żebyś mógł zobaczyć wszystko. Alternatywą było dodanie podziałów linii.
Toby Speight
1
Dodano podział linii - myślę, że tak jest lepiej, ponieważ teraz działa filtrowanie wstępne.
Toby Speight,
1

Python 2.7 - 447B (rozmiar pliku)

To moja pierwsza próba w Codegolf, mam nadzieję, że się spełni. Potrzebowałem 2h. (Ale wciąż jestem początkującym w Pythonie)

Edycja: Podziękowania dla „Kevina Lau - nie Kenny'ego” za wskazanie:

  • argument własny pytonów w klasie można zastąpić dowolnym
  • wcięcie musi być tylko pojedynczą spacją
  • wbudowane sortowane - funkcja ( wiedziałem , że ją widziałem, ale myślałem, że jest to metoda na listach)
  • __ radd __ nie jest potrzebne (w każdym razie obsługuję tylko dodawanie obiektów B (typu Bag))

Edycja: Dodatkowo zaoszczędziłem miejsce, zastępując funkcje lambdami, nowe linie i wcięcia większą liczbą średników.

Kod:

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

czeki:

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

Wynik:

True
True
True
True
True
True
True
True
True
False

Mógłbym kiedyś spróbować z ustawioną podstawą. Edycja: Może nawet spróbuję tylko z funkcjami.

Dziwak
źródło
Witamy w PPCG! W Pythonie należy zwrócić uwagę na fakt, że tak naprawdę nie trzeba wywoływać pierwszych parametrów w funkcjach klas self- coś podobnego też Sby działało . Inną sztuczką jest to, że wbudowana sortedfunkcja robi dokładnie to, co chcesz z nowej funkcji s, więc możesz zrezygnować z definicji funkcji (ponieważ używasz jej tylko raz). Nigdy nie potrzebujesz, __radd__ponieważ nigdy nie dodajesz torebek innych niż torby, chociaż nadal potrzebujesz __rmul__. Na koniec potrzebujesz tylko jednego miejsca wcięcia zamiast czterech, co znacznie zmniejsza liczbę bajtów
Value Ink