20
2
Inspired (with the explanation stolen from) this
Background
Say you have two lists A = [a_1, a_2, ..., a_n]
and B = [b_1, b_2, ..., b_n]
of integers. We say A
is potentially-divisible by B
if there is a permutation of B
that makes a_i
divisible by b_i
for all i
. The problem is then: is it possible to reorder (i.e. permute) B
so that a_i
is divisible by b_i
for all i
?
For example, if you have
A = [6, 12, 8]
B = [3, 4, 6]
Then the answer would be True
, as B
can be reordered to be B = [3, 6, 4]
and then we would have that a_1 / b_1 = 2
, a_2 / b_2 = 2
, and a_3 / b_3 = 2
, all of which are integers, so A
is potentially-divisible by B
.
As an example which should output False
, we could have:
A = [10, 12, 6, 5, 21, 25]
B = [2, 7, 5, 3, 12, 3]
The reason this is False
is that we can't reorder B
as 25 and 5 are in A
, but the only divisor in B
would be 5, so one would be left out.
Your task
Your task is, obviously, to determine whether two lists (given as input) are potentially divisible. You may take input in any accepted manner, as with output.
Duplicates in the lists are a possibility, and the only size restrictions on the integers are your language. All integers in both lists will be larger than 0, and both lists will be of equal size.
As with all decision-problems the output values must be 2 distinct values that represent true and false.
This is a code-golf so shortest code wins!
Test cases
Input, input => output
[6, 12, 8], [3, 4, 6] => True
[10, 5, 7], [1, 5, 100] => False
[14, 10053, 6, 9] [1,1,1,1] => True
[12] [7] => False
[0, 6, 19, 1, 3] [2, 3, 4, 5, 6] => undefined
3@Shaggy from the question: both lists will be of equal size – caird coinheringaahing – 2017-08-27T20:16:58.780
2Why is the last test case undefined? – Dennis – 2017-08-27T21:29:21.687
1@Dennis one of the lists has a 0 in it – caird coinheringaahing – 2017-08-27T21:31:13.690
1Right. (Not sure why, 0 is divisible by all integers.) Do the two outputs have to be truthy and falsy, or just consistent? – Dennis – 2017-08-27T21:41:12.770
@Dennis 1) it's in case 0 is in the second list, to avoid 0 division errors 2) just consistent – caird coinheringaahing – 2017-08-27T21:55:04.783