14
Lets take a set of integers greater than 1 and call it X. We will define S(i) to be the set of all members of X divisible by i where i > 1. Would like to choose from these subsets a group of sets such that
Their union is the set X
No element of X is in two of the sets.
For example we can regroup {3..11} as
{3,4,5,6,7,8,9,10,11}
S(3): {3, 6, 9, }
S(4): { 4, 8, }
S(5): { 5, 10, }
S(7): { 7, }
S(11):{ 11}
Some sets cannot be expressed in this way. For example if we take {3..12}, 12 is a multiple of both 3 and 4 preventing our sets from being mutually exclusive.
Some sets can be expressed in multiple ways, for example {4..8} can be represented as
{4,5,6,7,8}
S(4): {4, 8}
S(5): { 5, }
S(6): { 6, }
S(7): { 7, }
but it can also be represented as
{4,5,6,7,8}
S(2): {4, 6, 8}
S(5): { 5, }
S(7): { 7, }
Task
Our goal is to write a program that will take a set as input and output the smallest number of subsets that cover it in this fashion. If there are none you should output some value other than a positive integer (for example 0).
This is a code-golf question so answers will be scored in bytes, with less bytes being better.
Tests
{3..11} -> 5
{4..8} -> 3
{22,24,26,30} -> 1
{5} -> 1
Post Rock Garf Hunter
Posted 2017-07-15T16:07:41.280
Reputation: 55 382
If there are none you should output some value other than a positive integer (for example 0). Can't our program result in undefined behaviour instead? – Mr. Xcoder – 2017-07-15T16:13:05.237
Also, can you add a test case like
[5..5]? Can we receive things like[8..4]? – Mr. Xcoder – 2017-07-15T16:14:20.820@Mr.Xcoder No it may not. Programs should be able to identify impossible cases not just loop forever or crash on them. – Post Rock Garf Hunter – 2017-07-15T16:14:28.110
1"
12is a multiple of both3and4preventing our sets from being mutually exclusive": why? I don't see anything else in the problem statement which requires12to go into both subsets. – Peter Taylor – 2017-07-15T16:14:54.603@Mr.Xcoder I added
[5]I don't know what[8..4]is supposed to mean. – Post Rock Garf Hunter – 2017-07-15T16:15:27.550@WheatWizard [8..4] means [8,7,6,5,4] – Mr. Xcoder – 2017-07-15T16:15:47.163
@PeterTaylor It is required to go in those sets. I'll try to work that in. – Post Rock Garf Hunter – 2017-07-15T16:16:10.330
1Also, what's with the test cases?
[22,24,26,30]are all multiples of2. Are you sure it wouldn't be better to delete this and sandbox it? – Peter Taylor – 2017-07-15T16:16:30.703@Mr.Xcoder Thats the same as
[4,5,6,7,8], sets do not have order – Post Rock Garf Hunter – 2017-07-15T16:16:34.333@PeterTaylor that should have said one, I must've hit the wrong key when I was copying it over – Post Rock Garf Hunter – 2017-07-15T16:17:59.803
@PeterTaylor Does that clarify why we can't add 12? The wording is very tricky. – Post Rock Garf Hunter – 2017-07-15T16:22:52.130
Parameterised names ftw. "We can define the subset
S(i)as the set of elements ofXwhich are divisible byi". – Peter Taylor – 2017-07-15T16:37:47.943Add more test cases please.. – J42161217 – 2017-07-15T17:45:15.250
Ah, also needs to require the divisor to be greater than 1. – Peter Taylor – 2017-07-15T19:01:22.913
Is it even possible to have no solution? – Zacharý – 2017-07-15T21:44:12.690
@Zacharý The example
[3..12]has no solution as explained. – Post Rock Garf Hunter – 2017-07-15T21:57:31.603