Taschenoperationen implementieren

20

Eine Tasche , auch Multiset genannt, ist eine ungeordnete Sammlung. Sie können es einen Satz nennen, der Duplikate zulässt, oder eine Liste (oder ein Array), die nicht sortiert / indiziert sind. In dieser Herausforderung werden Sie gebeten, Taschenoperationen durchzuführen: Addition, Differenz, Multiplikation, Division, Zählung und Gleichheitstest.

Operationen

Die angegebenen Vorgänge sind möglicherweise nicht konventionell.

  • Außerdem werden zwei Beutel zu einem zusammengefasst, wodurch die Gesamtzahl der einzelnen Werte erhalten bleibt
    [1,2,2,3] + [1,2,4] = [1,1,2,2,2,3,4]
  • Die Differenz entfernt aus einem Beutel jedes Element eines anderen Beutels oder bewirkt nichts, wenn kein solches Element vorhanden ist
    [1,2,2,4] - [1,2] = [2,4] [1,2,3] - [2,4] = [1,3]
  • Multiplikation multipliziert jedes Element in der Tasche.
    [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]
  • Eine Teilung ist ungewöhnlich: Jeweils n gleiche Elemente werden in n gleiche neue Beutel gegeben, Elemente, die keine n-Gruppe bilden können, verbleiben im Beutel. Geben Sie eine der n neuen Taschen zurück.
    [1,1,2,2,2] / 2 = [1,2] [1,2,2,3,3,3] / 3 = [3]
  • Beim Zählen wird gezählt, wie viele Teilerbeutel aus dem Dividendenbeutel hergestellt werden können
    [1,1,2,2,2,2,3,3,3] c [1,2,3] = 2
  • gleichheitstest prüft ob zwei beutel die gleiche nummer von jedem element haben
    [1,2,2,3] == [3,2,1,2] = truthy [1,2,3] == [1,2,2,3] = falsy(kann auch dafür verwendet werden =)

Wenn Sie für die Operatoren eigene Symbole verwenden, geben Sie diese bitte an.

Formate

Taschen werden als Listen des Formulars angezeigt [1,1,2,3,4]. Sie können jede andere als quadratische Klammer verwenden oder sogar Anführungszeichen oder gar nichts. Die Elemente werden intfür die Zwecke dieser Frage (mathematisch, nicht notwendigerweise ) ganze Zahlen sein . Taschen müssen nicht sortiert werden.

Das Eingabeformat ist zwei Beutel oder ein Beutel und eine Ganzzahl mit einem Operator. Sie können Ihr eigenes Format angeben, solange es diese drei enthält.

Das Ausgabeformat sollte ein einzelner Beutel desselben Formats sein.

Regeln

  • Sie dürfen keine integrierten Funktionen, Operationen oder Bibliotheken (einschließlich der Standardbibliothek) verwenden, die diese bereits implementieren. Es ist jedoch in Ordnung, die Listenverkettung und -vervielfachung zu verwenden, da sie per Definition Listenoperationen sind und keine Bag-Operationen (die im Grunde das Gleiche tun).
  • Es gelten Standardlücken
  • kürzeste Antwort gewinnt

Testfälle

[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
quelle
2
Vielleicht das Eingabeformat lockern? Erlauben Sie beispielsweise, Beutel, Beutel / Nummer und Operator als separate Argumente oder in einem freien Format zu verwenden. Ansonsten ist ein wichtiger Teil der Herausforderung das Parsen der Eingabe, was nicht besonders interessant ist
Luis Mendo
@LuisMendo split-on-space ist ausreichend, um dies zu analysieren, wenn Sie eine Sprache haben, die Strings überhaupt als Listen auswerten kann, finden Sie nicht? Ich bin unerfahren beim Posten von Herausforderungen, bitte
klären
Ich konnte keinen relevanten Meta-Post finden, sehe aber zum Beispiel die Formulierung hier : Sie können die Ganzzahl als Dezimalrepräsentation, unäre Repräsentation (mit einem Zeichen Ihrer Wahl), Byte-Array (Big- oder Little-Endian) oder Einzelbyte lesen (Wenn dies der größte Datentyp Ihrer Sprache ist) . Oder hier : Eingabe- und Ausgabeformate sind wie gewohnt flexibel (Arrays, Listen, Listen, Strings mit sinnvollen Trennzeichen usw. ).
Luis Mendo
@ LuisMendo ist jetzt im Grunde kostenlos. Und über die ganze Zahl habe ich nur das im mathematischen Sinne gemeint, nicht den Datentyp.
Busukxuan
1
@ LuisMendo Nö, die Symbole müssen Sinn ergeben, wenn auch nur ein wenig. Nun, Sie können one = für den Gleichheitstest verwenden.
Busukxuan

Antworten:

3

05AB1E, 92 87 83 82 77 Bytes

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

Nach Operation aufteilen

>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

Erläuterung

Zusatz

‚˜,}

Legen Sie eine Tüte in eine andere und drücken Sie sie zu einer Tüte flach.

Multiplikation

и˜Qis}

Stellen Sie sicher, dass sich die Nummer oben auf dem Stapel befindet. Nenne das X.

GD})˜,}

Dupliziere den Beutel X-mal und verbinde ihn zu einem Beutel.

Anzahl

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

Zählen Sie für jedes Element im Divisionsbeutel die Anzahl der Vorkommen im Dividendenbeutel.
Die Mindestanzahl ist die Anzahl der Taschen, die wir herstellen können.

Gleichberechtigung

 {s{Q,}

Sortieren Sie beide Beutel und prüfen Sie, ob sie gleich sind.

Teilung

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

Zählen Sie, wie oft jedes einzelne Element im Beutel vorkommt.
Kommt es mindestens so oft vor wie der Divisor. Bewahren Sie (nr_of_copies_total // divisor) Kopien in der Tasche auf.

Unterschied

svy†¬yQi¦}} 

Sortieren Sie jedes Element im Subtrahend vor dem Minuend.
Wenn der aktuelle Subtrahend gleich dem ersten Element im Minuend ist, entfernen Sie ihn aus dem Minuend.

Emigna
quelle
9

APL (155)

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

Dies definiert einen Operator 'bag', der Bag-Operationen für gegebene Funktionen definiert. Dh +∆wäre zusätzlich. Dann liest es eine Zeile von der Tastatur und wertet sie als APL-Ausdruck aus.

Die Funktionen sind:

  • +∆zusätzlich
  • -∆Subtraktion
  • ×∆Multiplikation
  • ÷∆, Teilung
  • ⊂∆, Zählen
  • ≡∆, Äquivalenz (obwohl aufgrund des Golfspiels jede nicht erkannte Funktion die Äquivalenz bewirkt)

Erläuterung:

  • ∆←{... }: einen Operator definieren :

    • O←⍺⍺: Speichern Sie die angegebene Funktion in O( funktioniert ⎕CRnicht ⍺⍺direkt mit)
    • O←⎕CR'O': Ermittelt die String-Darstellung dieser Funktion
    • '+'=O... :: zusätzlich
      • ⍺,⍵: Verbinden Sie die beiden Listen miteinander
      • R[⍋R←... ]: und sortiere das Ergebnis
    • '-'=O:: für die Subtraktion,
      • ⍺{... }⍵: führe die folgende rekursive Funktion aus:
        • ⍵≡⍬:⍺: Wenn der Subtrahend leer ist, gib das Minuend zurück
        • ⍺/⍨(⍳⍴⍺)≢⍺⍳⊃⍵∇1↓⍵: andernfalls entferne das erste Element des Subtrahends sowohl vom Subtrahend als auch vom Minuend und versuche es erneut
    • (⍬=⍴⍵)∧K←'×'=O: für die Multiplikation, und wenn das richtige Argument kein Sack ist:
      • ⍵/⍺: repliziere jedes Element im linken Argument mit dem rechten Argument
    • K:: ... und wenn das richtige Argument ist eine Tasche:
      • ⍺/⍵: repliziere jedes Element im rechten Argument mit dem linken Argument (dies ist so, dass die Multiplikation kommutativ ist)
    • '÷'=O:: für die Teilung,
      • ⍵≤⍺∘.+⍺: sehen, welche Elemente in ⍺ mindestens ⍵ Mal vorkommen,
      • ⍺/⍨: Wählen Sie diese aus ⍺,
      • : und entferne alle Duplikate aus dieser Liste
    • '⊂'=O:: zum Zählen,
      • ⍵{... }⍺: führe die folgende rekursive Funktion aus:
        • (∪⍺)≢∪⍵:0: Wenn eine Liste Elemente enthält, die die andere nicht enthält, ist das Ergebnis 0
        • 1+⍺∇⍵-∆⍺: Andernfalls subtrahieren Sie die Dividende vom Divisor, versuchen Sie es erneut und erhöhen Sie das Ergebnis.
    • : Wenn keine der oben genannten Bedingungen erfüllt ist, führen Sie den Äquivalenztest durch:
      • ⍺[⍋⍺]≡⍵[⍋⍵]: Beide Listen sortieren und prüfen, ob sie gleich sind
  • : Liest einen Ausdruck von der Tastatur, wertet ihn aus und gibt das Ergebnis aus.

Testfälle:

      ∆←{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
quelle
Wirklich professionelle Lösung und tolles Schreiben! +1
Ihre Beschreibung und Erklärung ist wirklich solide! Eines jedoch: Für die Unterteilung glaube ich, dass die Spezifikation in einer Weise formuliert ist, [2,2,2,2,2,2]/3die etwas geben sollte [2,2], aber Ihre scheint etwas zu geben [2].
Wert Tinte
Sie müssen die REPL nicht codieren. Wenn Sie nur definieren , wird der Benutzer in die native REPL von APL verschoben, die jetzt gültig ist. Ich denke, Sie können einige Bytes sparen, indem Sie die Subtraktion bis zum Ende verschieben, da dies die einzige ist, für die zwei Zeilen erforderlich sind. ⎕CRVerwenden Sie stattdessen , um *count zu symbolisieren, und tun Sie O←⍺⍺2dann 2=O:für plus, 1=Ofür mult, 0=O:für equiv, 7<O:für count und 0<O:für div (mit impliziertem 0>O:Wert für 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))

Nimmt 3 Parameter auf. Der erste Parameter ist ein Array, der zweite ein Operator, der dritte ist vom Operator abhängig. Taschen müssen nicht negative ganze Zahlen enthalten.

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

Ungolfed:

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

Oktave, 253 244 226 Bytes

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

Diese Funktion muss sich in einer Datei befinden. Um die Funktion in das Befehlsfenster zu schreiben, müssen Sie endfunctionoder verwenden end.

Danke an Luis Mendo für das Speichern von 18 Bytes.

Die Operationen sind:

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

Anwendungsbeispiel:

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

Ungolfed:

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

Mathematica, 387 347 300 284 Bytes

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]

Etwas entgolfet (alias alte Version), hatte keine volle Unterstützung für Gleichheitstests (zurückgegebene wahrheitsgemäße Werte, aber für nicht passende Taschen unbewertet gelassen).

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)

Implementiert den erforderlichen Datentyp mit head b.

Zunächst bwird definiert, zu sein Orderless. Jedes Objekt, das mit head an den Kernel übergeben bwird, sortiert seine Argumente automatisch. Selbst wenn dies b[3,2,1]eingegeben wird, sieht der Bewerter niemals etwas anderes als b[1,2,3].

Addition wird trivial als Verbinden der Elemente definiert.

Eine spezielle Regel für die Differenz von zwei Beuteln ist definiert (unten erklärt). Die Vorgängerversion hatte ein Hilfssymbol für Formausdrücke -bag.

Dann wird die Multiplikation (solange nes sich um eine positive ganze Zahl handelt) rekursiv definiert, n*b[...] = b[...] + (n-1)*b[...]was sich schließlich zu einer einfachen Summe reduziert.

Die Sonderregel für b[...] - b[...]zählt die Anzahl der verschiedenen Elemente in der Summe der Beutel und subtrahiert den zu subtrahierenden Beutel zweimal von diesem Ergebnis. Einfacher erklärt:

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

Oben ist eine Liste von Keys->Values. KeyValueMapmit Tableerstellt Listen von jedem Key ValueMal. (Es gibt auch eine Max[...,0]Möglichkeit, negative Längentabellen nicht zu erstellen). Dies kommt heraus als:

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

Das ist abgeflacht und der Kopf Listwird durch ersetzt b.

Die Division durch ganze Zahlen ist in den verwendeten Funktionen etwas ähnlich, es ist einfach die durchgehende Division der Elementzählung durch die ganze Zahl.

Division durch Mengen oder Zählung habe ich seit der ursprünglichen Implementierung geändert. Es wird nun rekursiv wie folgt vorgegangen. Sprich, teilen wir Beutel b1durch b2(die in der golfed Code sind cund ajeweils. Wenn (b1-b2) + b2 == b1, dann 1 addieren und daß das Ergebnis der Teilung hinzuzufügen (b1-b2)/b2. Falls nicht, geben 0 zurück und die Rekursion verlassen.

Wenn Taschen passen, built-in ==gibt True. Die letzte Zeile erzwingt ein, Falsewenn sie dies nicht tun.

Testfälle:

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

Q - 219 Zeichen

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}

azur Addition sfür Differenz (Subtraktion),m zur Multiplikation, dzur Division, czur Zählung, ezur Gleichheit.

Der Additionsalgorithmus ist der offensichtliche, er fügt nur die Säcke zusammen.

Die Subtraktionsfunktion indiziert im Eingabebeutel (als Array dargestellt) den gesamten Indexbereich, mit Ausnahme der ersten nIndizes jeder durch Gleichheit zu jedem Element in gebildeten Äquivalenzklasse y, wobei ndie Anzahl der Kopien dieses Vertreters in angegeben isty . Der Umgang mit möglichen Duplikaten ymacht dies zu einem echten Funktionsmonster.

Die Multiplikationsfunktion nimmt xWerte von jedemyy Wert . In dem Fall, dass es sich um einen einzelnen Wert handelt, werden diese Werte anstelle eines Arrays nur repliziert.

Die Divisionsfunktion erzeugt die Werte, deren Anzahl im Array größer als ist y , und entfernt dann Duplikate.

Die Zählfunktion berechnet die Anzahl der Elemente in y und gibt dann das Minimum zurück.

Zwei Taschen sind gleich, wenn ihre sortierten Array-Darstellungen gleich sind.

C. Quilley
quelle
2

Ruby, Klassendefinitionsantwort, 323 291 Bytes

Wollte meistens nur das machen Bag einer echten Klasse machen, weil Ruby flexibel mit Klassen umgehen kann. In diesem Fall erbt es von, Arrayweil es kürzer ist, als ein internes Array zu initialisieren und sich mit den anderen Dingen zu befassen.

Ich werde wahrscheinlich eine ernstere Antwort zum Golfen geben, die eine Funktion verwendet, um die Operationen von morgen zu erledigen. Ich bin sehr müde und hatte zu viel Spaß damit , obwohl ich mich mit der Definition derNumber * Bag Numerikklasse herumschlagen musste , um richtig arbeiten zu können. LOBEN SIE DIE COERCE-FUNKTION, UM ES ZU MACHEN, DASS ICH DIE NUMERIKKLASSEN-DEFINITIONEN NICHT MESSEN MUSSTE

Probieren Sie es online! (Whitespace spielt in Ruby keine Rolle, daher ist der Code dort etwas ungolfed.)

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
Wert Tinte
quelle
1

Ruby, 201 Bytes

Wie in meiner anderen Antwort versprochen, ist hier eine, die Funktionen verwendet, anstatt eine neue Klasse zu erstellen. Ich bin so kurz davor, die 200-Byte-Marke zu überschreiten ... Probieren Sie es online aus

Dies verwendet die gleichen Opcodes wie @Neil in seiner JavaScript-Antwort und die gleiche Reihenfolge der Argumente (lhs, opcode, rhs).

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

Der Code:

->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][]}
Wert Tinte
quelle
1

C ++, 555 551 Bytes

(Zeilenumbrüche zur besseren Lesbarkeit hinzugefügt - nur die erste neue Zeile wird benötigt und gezählt)

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

Erläuterung

Wir implementieren unsere Tasche als Karte von (Wert, Anzahl). Die Grundoperationen können durch Manipulieren der Zählwerte implementiert werden; Subtraktion und Ganzzahldivision müssen auch alle Elemente entfernen, deren Anzahl Null erreicht, damit dies std::map::operator==als Gleichheitstest funktioniert.

Der folgende erweiterte Code ist eine generische Version des oben genannten Codes, jedoch weitaus weniger vorteilhaft: Wir verwenden einen separaten Code, um alle Nullzählwerte s()herauszufiltern, und implementieren constOperationen in Form von Zuweisungsoperatoren auf idiomatische C ++ - Weise. Wir verwenden auch s(), um die Multiplikation durch 0Rückgabe eines wirklich leeren Beutels (getestet durch Hinzufügen (B{1}*0 != B{})von main()) durchzuführen. Das Original besteht diesen Test nicht und es ist nicht klar, ob es eine Anforderung ist.

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

Tests

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
quelle
Gute Antwort! +1. Dein Code muss im Beitrag richtig formatiert sein.
Yytsi
Ich wollte den Code absichtlich umbrechen, damit Sie alles sehen können. Die Alternative bestand darin, Zeilenumbrüche hinzuzufügen.
Toby Speight
1
Zeilenumbrüche hinzugefügt - Ich denke, das ist besser, weil Prettify jetzt funktioniert.
Toby Speight
1

Python 2.7 - 447B (Dateigröße)

Dies ist mein erster Versuch bei Codegolf, ich hoffe, dass er zufriedenstellt. Ich brauchte 2h (Aber ich bin immer noch ein Anfänger in Python)

Edit: Danke an "Kevin Lau - nicht Kenny" für diesen Hinweis:

  • Das Selbstargument von Pythons in einer Klasse kann durch alles ersetzt werden
  • Einrückung muss nur ein Leerzeichen sein
  • die eingebaute sort - funktion (ich wusste ich es gesehen hatte, dachte aber, dass es eine Methode in Listen ist)
  • __ radd __ wird nicht benötigt (ich unterstütze sowieso nur das Hinzufügen von B-Objekten (Bag-Typ))

Bearbeiten: Zusätzlich habe ich Platz gespart, indem ich Funktionen durch Lambda und neue Zeilen und Einrückungen durch mehr Semikolons ersetzt habe.

Code:

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

prüft:

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

Ausgabe:

True
True
True
True
True
True
True
True
True
False

Ich könnte es ein anderes Mal versuchen, wenn ich es als Basis setze. Edit: Vielleicht probiere ich es mal nur mit Funktionen.

Teck-Freak
quelle
Willkommen bei PPCG! Bei Python ist zu beachten, dass Sie in Klassenfunktionen nicht unbedingt die ersten Parameter aufrufen müssen self- so etwas ist Sgenauso gut. Ein weiterer Trick ist, dass die integrierte sortedFunktion genau das tut, was Sie von Ihrer neuen Funktion serwarten, sodass Sie auf die Funktionsdefinition verzichten können (da Sie sie nur einmal verwenden). Sie brauchen __radd__es nie, weil Sie niemals Taschen mit anderen als Taschen hinzufügen, obwohl Sie es immer noch brauchen __rmul__. Schließlich brauchen Sie nur ein Leerzeichen anstelle von vier, was Ihre Byteanzahl um einiges verringert
Value Ink