20
\$\begingroup\$

A bag, also called a multiset, is an unordered collection. You can call it a set that allows duplicates, or a list (or an array) that is not ordered/indexed. In this challenge, you are asked to implement bag operations: addition, difference, multiplication, division, counting and equality test.

Operations

The specified operations may not be conventional.

  • addition combines two bags into one, conserving the total number of each value
    [1,2,2,3] + [1,2,4] = [1,1,2,2,2,3,4]
  • difference removes from a bag each element of another bag, or does nothing if no such element
    [1,2,2,4] - [1,2] = [2,4] [1,2,3] - [2,4] = [1,3]
  • multiplication multiplies each element in the bag.
    [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]
  • division is an uncommon one: each n equal elements are put in n equal new bags, elements that cannot form an n-group remain in the bag. Return any one of the n new bags.
    [1,1,2,2,2] / 2 = [1,2] [1,2,2,3,3,3] / 3 = [3]
  • counting counts how many divisor bags can be produced from the dividend bag
    [1,1,2,2,2,2,3,3,3] c [1,2,3] = 2
  • equality test checks if two bags have the same numbers of each element
    [1,2,2,3] == [3,2,1,2] = truthy [1,2,3] == [1,2,2,3] = falsy (can also use = for this)

If you are using your own symbols for the operators, please specify.

Formats

Bags will be displayed as lists of the form [1,1,2,3,4]. You can use any other bracket than square ones, or even use quotes, or nothing at all. The elements will be integers(mathematically, not necessarily int) for the purpose of this question. Bags do not have to be sorted.

The input format will be two bags or a bag and an integer, with an operator. You can specify your own format as long as it contains these three.

The output format should be a single bag of the same format.

Rules

  • you may not use built-in functions, operations or libraries (including the standard library) that already implement these; it's ok though to use list concatenation and multiplication since they are by definition list operations, not bag operations (which happen to basically do the same thing)
  • standard loopholes apply
  • shortest answer wins

Test cases

[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
\$\endgroup\$
  • 2
    \$\begingroup\$ Maybe relax the input format? For example allow to take the bag, bag/number, and operator as separate arguments, or in a free format. Otherwise an important part of the challenge is parsing the input, which is not particularly interesting \$\endgroup\$ – Luis Mendo Jul 3 '16 at 2:41
  • \$\begingroup\$ @LuisMendo split-on-space is sufficient to parse this, if you have a language that can evaluate strings as lists at all, don't you think? I'm inexperienced at posting challenges, so please enlighten me :-) \$\endgroup\$ – busukxuan Jul 3 '16 at 2:44
  • \$\begingroup\$ I couldn't find a relevant meta post, but see for example the wording here: you can read the integer as its decimal representation, unary representation (using a character of your choice), byte array (big or little endian) or single byte (if this is your languages largest data type). Or here: Input and output formats are flexible as usual (arrays, lists, list of lists, strings with reasonable separators, etc). \$\endgroup\$ – Luis Mendo Jul 3 '16 at 3:02
  • \$\begingroup\$ @LuisMendo it's basically free now. And about the integer, I just meant that in the mathematical sense, not the data type. \$\endgroup\$ – busukxuan Jul 3 '16 at 3:14
  • 1
    \$\begingroup\$ @LuisMendo nope, the symbols need to make sense, even if only a little. Well, you can use one = for equality test. \$\endgroup\$ – busukxuan Jul 3 '16 at 3:18

10 Answers 10

3
\$\begingroup\$

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

Split by operation

>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

Explanation

Addition

‚˜,}

Put one bag in other and flatten them to one bag.

Multiplication

и˜Qis}

Make sure the number is on the top of the stack. Call this X.

GD})˜,}

Duplicate the bag X times and join to one bag.

Count

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

For each element in the divisor bag, count number of occurences in dividend bag.
The minimum count will be the number of bags we can make.

Equality

 {s{Q,}

Sort both bags and check if they're equal.

Division

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

Count how many times each unique element occurs in the bag.
If it occurs at least as many times as the divisor. Keep (nr_of_copies_total // divisor) copies in the bag.

Difference

svy†¬yQi¦}} 

For each element in the subtrahend, sort it to the front of the minuend.
If the current subtrahend if equal to the first element in the minuend, remove it from the minuend.

\$\endgroup\$
9
\$\begingroup\$

APL (155)

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

This defines an operator 'bag', which defines bag operations for given functions. I.e. +∆ would be addition. It then reads a line from the keyboard and evaluates it as an APL expression.

The functions are:

  • +∆, addition
  • -∆, subtraction
  • ×∆, multiplication
  • ÷∆, division
  • ⊂∆, counting
  • ≡∆, equivalence (though due to golfing any unrecognized function will do equivalence)

Explanation:

  • ∆←{...}: define an operator :

    • O←⍺⍺: store the given function in O (⎕CR won't work with ⍺⍺ directly)
    • O←⎕CR'O': get the string representation of that function
    • '+'=O...:: for addition,
      • ⍺,⍵: join the two lists together
      • R[⍋R←...]: and sort the result
    • '-'=O:: for subtraction,
      • ⍺{...}⍵: run the following recursive function:
        • ⍵≡⍬:⍺: if the subtrahend is empty, return the minuend
        • ⍺/⍨(⍳⍴⍺)≢⍺⍳⊃⍵∇1↓⍵: otherwise, remove the first element of the subtrahend from both the subtrahend and the minuend and try again
    • (⍬=⍴⍵)∧K←'×'=O: for multiplication, and if the right argument is not a bag:
      • ⍵/⍺: replicate each element in the left argument by the right argument
    • K:: ...and if the right argument is a bag:
      • ⍺/⍵: replicate each element in the right argument by the left argument (this is so that multiplication is commutative)
    • '÷'=O:: for division,
      • ⍵≤⍺∘.+⍺: see which elements in ⍺ occur at least ⍵ times,
      • ⍺/⍨: select those from ⍺,
      • : and remove all duplicates from that list
    • '⊂'=O:: for counting,
      • ⍵{...}⍺: run the following recursive function:
        • (∪⍺)≢∪⍵:0: if one list contains elements the other doesn't, the result is 0
        • 1+⍺∇⍵-∆⍺: otherwise, subtract the dividend from the divisor, try again, and increment the result.
    • : if none of the above, do the equivalence test:
      • ⍺[⍋⍺]≡⍵[⍋⍵]: sort both lists and see if they are equal
  • : read an expression from the keyboard, evaluate it, and output the result.

Test cases:

      ∆←{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
\$\endgroup\$
  • \$\begingroup\$ Really professional solution and great write-up! +1 \$\endgroup\$ – user15259 Jul 5 '16 at 17:31
  • \$\begingroup\$ Your writeup and explanation is really solid! One thing, though: for division, I believe the spec is worded in a way that [2,2,2,2,2,2]/3 should give [2,2], but yours seems to give [2]. \$\endgroup\$ – Value Ink Jul 5 '16 at 23:46
  • \$\begingroup\$ You don't need to code the REPL. If you just define , the user will be dumped into APL's native REPL, where is now valid. I think you can save some bytes by moving subtraction to the end as it is the only one that requires two lines. Instead of the ⎕CR, use * to symbolize count, and do O←⍺⍺2, then 2=O: for plus, 1=O for mult, 0=O: for equiv, 7<O: for count, and 0<O: for div (with implied 0>O: for subtr). \$\endgroup\$ – Adám Aug 29 '16 at 6:32
6
\$\begingroup\$

JavaScript (ES6), 260 bytes

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

Takes 3 parameters. The first parameter is an array, the second is an operator, the third depends on the operator. Bags are required to hold non-negative integers.

[...] 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));
    }
}
\$\endgroup\$
6
\$\begingroup\$

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

This function must be in a file. To write the function in the command window you must use endfunction or end.

Thanks to Luis Mendo for saving 18 bytes.

The operations are:

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

Usage example:

>> 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
\$\endgroup\$
5
\$\begingroup\$

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]

Slightly degolfed (a.k.a old version), didn't have full support for equality tests (returned truthy values, but left unevaluated for non-matching bags).

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)

Implements the required data type with head b.

First b is defined to be Orderless. Any object passed to the kernel with head b will autosort its arguments. So even if b[3,2,1] is typed in, the evaluator will never see anything other than b[1,2,3].

Addition is trivially defined as joining the elements.

A special rule for the difference of two bags is defined (explained below). Previous version had an auxiliary symbol for expressions of form -bag.

Then multiplication (as long as n is a positive integer) is recursively defined as n*b[...] = b[...] + (n-1)*b[...] which will eventually reduce to a simple sum.

The special rule for b[...] - b[...] counts the number of distinct elements in the sum of the bags and subtracts the bag to be subtracted twice from that result. Easier explained:

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

Above is a list of Keys->Values. KeyValueMap with Table creates lists of each Key Value times. (there's also a Max[...,0] there to not attempt creation of negative length tables). This comes out as:

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

which is flattened and head List is replaced with b.

Division by integers is somewhat similar in functions used, it is simply the floored division of the element counts by the integer.

Division by sets or counting I've changed since the original implementation. It is now recursively done as follows. Say, we divide bag b1 by b2 (which in the golfed code are c and a respectively. If (b1-b2) + b2 == b1, then add 1 and add to that the result of dividing (b1-b2)/b2. If not, return 0 and exit the recursion.

If bags match, built-in == gives True. The last line forces a False if they don't.

Test cases:

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
\$\endgroup\$
2
\$\begingroup\$

Q - 219 characters

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}

a for addition, s for difference (subtraction), m for multiplication, d for division, c for counting, e for equality.

The addition algorithm is the obvious one, just joining the bags.

The subtraction function indexes in input bag (represented as an array) with the entire index range, except for the first n indices of each equivalence class formed by equality to each element in y, where n is the number of copies of that representative in y. Handling possible duplicates in y makes this a real monster of a function.

The multiplication function takes x values from each y, in the case that y is a single value, instead of an array, it just replicates them.

The division function produces the values whose count in the array is greater than y, and then removes duplicates.

The counting function calculates the counts of each element in y, and then returns the minimum.

Two bags are equal if their sorted array representations are equal.

\$\endgroup\$
2
\$\begingroup\$

Ruby, class definition answer, 323 291 bytes

Mostly just wanted to make the Bag an actual class because of Ruby's flexibility with classes. In this case, it inherits from Array because it's shorter than having to initialize an internal array and dealing with the other stuff.

I'll probably do a more-serious golfing answer that uses a function to deal with the operations tomorrow. I'm very tired and I had too much fun with this even though I had to wrangle with the numerics class definition to get Number * Bag working properly PRAISE THE COERCE FUNCTION FOR MAKING IT SO I DIDN'T NEED TO MESS UP THE NUMERICS CLASS DEFINITIONS

Try it online! (Whitespace doesn't matter in Ruby, so the code is slightly ungolfed there.)

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
\$\endgroup\$
1
\$\begingroup\$

Ruby, 201 bytes

As promised in my other answer, here's one that uses functions instead of building a new class. I'm so close to breaching the 200 byte mark... Try it online

This uses the same opcodes as @Neil in his JavaScript answer, and the same order of arguments (lhs, opcode, rhs)

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

The 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][]}
\$\endgroup\$
1
\$\begingroup\$

C++, 555 551 bytes

(line breaks added for readability - only the first newline is required and counted)

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

Explanation

We implement our bag as a map of (value, count). The basic operations can be implemented by manipulating the counts; subtraction and integer division also need to remove any elements whose count reaches zero, so that std::map::operator== will work as the equality test.

The following expanded code is a generic version of the above, much less golfed: we use a separate s() to squeeze out any zero-count values, and we implement const operations in terms of assignment operators in the idiomatic C++ way. We also use s() to make multiplication by 0 return a truly empty bag (tested by adding (B{1}*0 != B{}) to main()); the original fails this test, and it's not clear whether it's a requirement.

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})
        ;
}
\$\endgroup\$
  • \$\begingroup\$ Nice answer! +1. Your code needs proper formatting in the post. \$\endgroup\$ – Yytsi Jul 6 '16 at 9:22
  • \$\begingroup\$ I deliberately wanted the code to wrap, so you can see it all. The alternative was to add line breaks. \$\endgroup\$ – Toby Speight Jul 6 '16 at 10:15
  • 1
    \$\begingroup\$ Line breaks added - I think this is better, because prettify now works. \$\endgroup\$ – Toby Speight Jul 6 '16 at 10:25
1
\$\begingroup\$

Python 2.7 - 447B (filesize)

This is my first try at Codegolf, I hope it satisfies. I needed 2h. (But I'm still a beginner at Python)

Edit: Thanks to "Kevin Lau - not Kenny" for pointing out these:

  • pythons self argument in a class can be replaced by anything
  • indentation only has to be a single space
  • the builtin sorted - funktion (I knew I had seen it, but I thought it to be a method in lists)
  • __ radd __ is not needed (I only support adding B-objects(Bag-type) anyways)

Edit: Additionally I saved space by replacing functions with lambdas and new lines and indentations with more semicolons.

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

checks:

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

Output:

True
True
True
True
True
True
True
True
True
False

I might try it an other time with set as basis some time. Edit: Maybe I'll even try with functions only.

\$\endgroup\$
  • \$\begingroup\$ Welcome to PPCG! A thing to note about Python is you don't actually need to call the first parameters in class functions self -- something like S would do just as well. Another trick is that the built-in sorted function does exactly what you want out of your new function s, so you can forgo the function definition (seeing as you only use it once). You don't ever need __radd__ because you never add non-bags with bags, although you still need __rmul__. Finally, you only need one space of indent instead of four, which trims down your byte count by quite a bit \$\endgroup\$ – Value Ink Jul 6 '16 at 20:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.