Implement bag operations
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 inO(⎕CRwon't work with⍺⍺directly)O←⎕CR'O': get the string representation of that function'+'=O...:: for addition,⍺,⍵: join the two lists togetherR[⍋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 01+⍺∇⍵-∆⍺: 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
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));
}
}
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