9
Your goal is to compute the set intersection of two lists of integers. The intersection is defined as the unique un-ordered group of integers found at least once in both input list.
Input
The input may be in any format desired (function parameter, stdio, etc.), and consists of two lists of integers. You many not assume anything about each list other than they may contain any non-negative number of integers (i.e. they are unsorted, possibly may contain duplicates, may have different lengths, and may even be empty). It is assumed that each integer will fit in your language's native signed integer type, may be more than 1 decimal digit long, and are signed.
Example input:
1 4 3 9 8 8 3 7 0
10 1 4 4 8 -1
Output
The output is any list-like of integers representing the set intersection of the two lists to any format desired (return value, stdio, etc.). There is no requirement that the output be sorted, though you are welcome to provide an implementation that happens to always be sorted. The output must form a valid un-ordered set (e.g. it must not contain any duplicate values).
Example test cases (note that the order of the output is not important):
First two lines are the input lists, third line is the output. (empty) denotes the empty list.
(empty)
(empty)
(empty)
1000
(empty)
(empty)
3 1 2 4 3 1 1 1 1 3
3 1 -1 0 8 3 3 1
1 3
1 2 1
3 3 4
(empty)
Scoring
This is code golf; shortest answer in bytes wins.
Standard loop-holes are prohibited. You may use any built-in features not designed for set-like operations.
Prohibited built-in features:
- set creation/removing duplicates
- set difference/intersection/union
- Generalized membership testing (e.g. anything similar to the
inkeyword in Python,indexOf-like functions, etc). Note that the use of "foreach item in list" constructs are allowed (assuming they don't violate any of the other restrictions), despite the fact that Python re-uses theinkeyword to create this construct. - These prohibited built-ins are "viral", i.e. if there's a larger built-in containing any of these sub-features, it is similarly prohibited (e.g. filtering by membership in a list).
Any built-ins not on the above list are allowed (ex. sorting, integer equality testing, list append/remove by index, filtering, etc.).
For example, take the following two example snippets (Python-like code):
# prohibited: filters by testing if each value in tmpList is a member of listA
result = tmpList.filter(listA)
# ok: filtering by a lambda which manually iterates over listA and checks for equality
def my_in_func(val, slist):
for a in slist:
if(val == a):
return True
return False
result = filter(lambda v: my_in_func(val, listA), tmpList)
You are welcome to implement any of these set-like features yourself and they will count towards your score.
Your solution should complete in a reasonable amount of time (say, less than a minutes on whatever hardware you have for two lists ~length 1000 each).
helloworld922
Posted 2016-03-05T18:59:41.270
Reputation: 2 503
5
By the way, confusion and miscommunication are common in do X without Y, which is why they are officially one of the thing to avoid when writing challenges.
– Dennis – 2016-03-06T00:06:15.1932@Dennis Yeah, I guess this problem really has become one of those :( When I first wrote it, I was hoping it might be an interesting problem, but as soon as I started working out a ruleset I should have just killed the challenge. – helloworld922 – 2016-03-06T00:18:05.407
Is a builtin which performs run length encoding allowed? – isaacg – 2016-03-06T19:46:11.020
That should be fine. – helloworld922 – 2016-03-06T20:08:32.330
1May there be duplicates in the output? – Adám – 2016-03-08T21:16:55.247
@Nᴮᶻ No, the output is not allowed to have duplicate values, e.g. the output must be a set. – helloworld922 – 2016-03-08T23:11:22.730
Too restrictive: If you have in your mind one solution... It is not so good.... – RosLuP – 2017-11-04T13:35:50.587