20
2
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
2Maybe 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 – Luis Mendo – 2016-07-03T02:41:55.940
@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 :-) – busukxuan – 2016-07-03T02:44:41.077
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).
– Luis Mendo – 2016-07-03T03:02:06.773@LuisMendo it's basically free now. And about the integer, I just meant that in the mathematical sense, not the data type. – busukxuan – 2016-07-03T03:14:42.823
Can the symbol used for the operator be chosen freely as part of the input format? For example, can it be a number? I'm not suggesting that it should or that it shouldn't; I just think it's important to know – Luis Mendo – 2016-07-03T03:17:35.523
1@LuisMendo nope, the symbols need to make sense, even if only a little. Well, you can use one = for equality test. – busukxuan – 2016-07-03T03:18:49.937
"you may not use built-in functions, operations or libraries (including the standard library) that already implement these..." Does this mean that, for instance, in Python, I cannot simply do
if bag1==bag2:print('1')
? – R. Kap – 2016-07-03T06:53:19.863@R.Kap You can use it if it helps. It's a list comparison, you need to add something to it to make it a bag comparison. – busukxuan – 2016-07-03T06:55:54.593
Can we use a different symbol for division and for counting? – Leaky Nun – 2016-07-03T07:22:02.947
You say "the symbols need to make sense", what does this objectively mean? – Leaky Nun – 2016-07-03T07:22:57.293
@LeakyNun I'd like them to be different, after all I don't want that to be an unnecessary difficulty, since for both operations the dividend is the product of the divisor and the quotient (not necessarily so as some bags may be "cut short", but the same goes to integer division), and the division symbol is intended to mean that for A/B=C, C is such that B*C=A, with both operations described by one symbol. – busukxuan – 2016-07-03T07:34:39.170
@LeakyNun now that you had me think about it, maybe having different symbols isn't a problem at all, since in logs and exponents the base, index and value are also three different values each expressible in the other two by three different operators. – busukxuan – 2016-07-03T07:40:18.060