14
\$\begingroup\$

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 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
\$\endgroup\$
16
  • \$\begingroup\$ 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? \$\endgroup\$
    – Mr. Xcoder
    Jul 15, 2017 at 16:13
  • \$\begingroup\$ Also, can you add a test case like [5..5]? Can we receive things like [8..4]? \$\endgroup\$
    – Mr. Xcoder
    Jul 15, 2017 at 16:14
  • \$\begingroup\$ @Mr.Xcoder No it may not. Programs should be able to identify impossible cases not just loop forever or crash on them. \$\endgroup\$
    – Wheat Wizard
    Jul 15, 2017 at 16:14
  • 1
    \$\begingroup\$ "12 is a multiple of both 3 and 4 preventing our sets from being mutually exclusive": why? I don't see anything else in the problem statement which requires 12 to go into both subsets. \$\endgroup\$ Jul 15, 2017 at 16:14
  • 1
    \$\begingroup\$ Also, what's with the test cases? [22,24,26,30] are all multiples of 2. Are you sure it wouldn't be better to delete this and sandbox it? \$\endgroup\$ Jul 15, 2017 at 16:16

6 Answers 6

6
\$\begingroup\$

Python 2, 167 bytes

lambda a:([q for q in range(a[-1])if a in[sorted(sum(j,[]))for j in combinations([[p for p in a if p%i<1]for i in range(2,1+a[-1])],q)]]+[0])[0]
from itertools import*

Try it online!

-9 bytes thanks to Zacharý
-4 bytes thanks to Mr. Xcoder
-2 bytes by using lists instead of sets
-5 bytes by using a in [...] rather than any([a == ...]).
-2 bytes thanks to Mr. Xcoder
-8 bytes by merging statements
-5 bytes thanks to Mr. Xcoder
-7 bytes thanks to Mr. Xcoder / Zacharý
+7 bytes to fix bug
-1 byte thanks to ovs

note

This is extremely slow for larger maximum numbers because it is in no way optimized; it did not within 2 minutes on Mr. Xcoder's device for [22, 24, 26, 30].

\$\endgroup\$
0
5
\$\begingroup\$

Clingo, 51 bytes

{s(2..X)}:-x(X).:-x(X),{s(I):X\I=0}!=1.:~s(I).[1,I]

Demo

$ echo 'x(3..11).' | clingo cover.lp -
clingo version 5.1.0
Reading from cover.lp ...
Solving...
Answer: 1
x(3) x(4) x(5) x(6) x(7) x(8) x(9) x(10) x(11) s(3) s(4) s(5) s(7) s(11)
Optimization: 5
OPTIMUM FOUND

Models       : 1
  Optimum    : yes
Optimization : 5
Calls        : 1
Time         : 0.003s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 0.010s
$ echo 'x(4..8).' | clingo cover.lp -
clingo version 5.1.0
Reading from cover.lp ...
Solving...
Answer: 1
x(4) x(5) x(6) x(7) x(8) s(3) s(4) s(5) s(7)
Optimization: 4
Answer: 2
x(4) x(5) x(6) x(7) x(8) s(2) s(5) s(7)
Optimization: 3
OPTIMUM FOUND

Models       : 2
  Optimum    : yes
Optimization : 3
Calls        : 1
Time         : 0.001s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 0.000s
$ echo 'x(22;24;26;30).' | clingo cover.lp -
clingo version 5.1.0
Reading from cover.lp ...
Solving...
Answer: 1
x(22) x(24) x(26) x(30) s(5) s(8) s(22) s(26)
Optimization: 4
Answer: 2
x(22) x(24) x(26) x(30) s(3) s(22) s(26)
Optimization: 3
Answer: 3
x(22) x(24) x(26) x(30) s(2)
Optimization: 1
OPTIMUM FOUND

Models       : 3
  Optimum    : yes
Optimization : 1
Calls        : 1
Time         : 0.004s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 0.000s
$ echo 'x(5).' | clingo cover.lp -
clingo version 5.1.0
Reading from cover.lp ...
Solving...
Answer: 1
x(5) s(5)
Optimization: 1
OPTIMUM FOUND

Models       : 1
  Optimum    : yes
Optimization : 1
Calls        : 1
Time         : 0.001s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 0.000s
\$\endgroup\$
2
  • \$\begingroup\$ This seems to not detect cases without solutions like x(3..12). (or do I need to update?). BTW, can you suggest a good introduction to clingo? \$\endgroup\$ Jul 17, 2017 at 12:03
  • 1
    \$\begingroup\$ @ChristianSievers Oops, that was a bug, which I’ve now fixed. It should output UNSATISFIABLE in such a case. I mostly used the Potassco guide. \$\endgroup\$ Jul 17, 2017 at 12:12
4
\$\begingroup\$

Mathematica, 105 bytes

Length@Select[Subsets@Table[Select[s,Mod[#,i]==0&],{i,2,Max[s=#]}],Sort@Flatten@#==Sort@s&][[1]]~Check~0&

Try it online
copy and paste the code with ctrl+v,
paste the input at the end of the code,
hit shift+enter to run

input

[{3,4,5,6,7,8,9,10,11}]

takes a list as input
outputs 0 if there are none

\$\endgroup\$
3
  • \$\begingroup\$ Nice use of Check \$\endgroup\$
    – Keyu Gan
    Jul 16, 2017 at 2:27
  • \$\begingroup\$ Why didn't you undelete your first answer once you had a working version? \$\endgroup\$
    – Neil
    Jul 16, 2017 at 15:41
  • \$\begingroup\$ Because this was a totally new approach? Is there a problem? \$\endgroup\$
    – ZaMoC
    Jul 16, 2017 at 15:43
4
\$\begingroup\$

Haskell, 136 bytes

import Data.List
f l|m<-maximum l=(sort[n|(n,c)<-[(length s,[i|j<-s,i<-[j,2*j..m],elem i l])|s<-subsequences[2..m]],c\\l==l\\c]++[0])!!0

Try it online!

How it works

f l     =                           -- input set is l
   |m<-maximum l                    -- bind m to maximum of l
       [   |s<-subsequences[2..m]]  -- for all subsequences s of [2..m]
        (length s, )                -- make a pair where the first element is the length of s
            [i|j<-s,i<-[j,2*j..m],elem i l]
                                    -- and the second element all multiples of the numbers of s that are also in l
     [n|(n,c)<-       ,c\\l==l\\c]  -- for all such pairs (n,c), keep the n when c has the same elements as l, i.e. each element exactly once
   sort[ ]++[0]                     -- sort those n and append a 0 (if there's no match, the list of n is empty)
 (     )!!0                         -- pick the first element

Take a lot of time for {22,24,26,30}.

\$\endgroup\$
3
\$\begingroup\$

Jelly, 38 35 34 33 31 28 25 24 23 20 19 bytes

ṀḊŒPð%þ@⁹¬Sḟ1ðÐḟL€Ḣ

-5 bytes thanks to Leaky Nun

Try it online!

I think the third test case works, but it is very slow. 0 is outputted when there are no solutions.

Explanation (might have gotten this explanation wrong):

ṀḊŒPð%þ@⁹¬Sḟ1ðÐḟL€Ḣ     (input z)
ṀḊ                      - 2 .. max(z)
  ŒP                    - powerset
    ð                   - new dyadic chain
     %þ@⁹               - modulo table of z and that
         ¬              - logical not
          S             - sum
           ḟ1           - filter out 1's
             ðÐḟ        - filter out elements that satisfy that condition
                L€      - length of each element
                  Ḣ     - first element
       
     
          
\$\endgroup\$
7
  • 1
    \$\begingroup\$ 18 bytes \$\endgroup\$
    – Leaky Nun
    Jul 16, 2017 at 12:53
  • \$\begingroup\$ Thanks! And thank you for not submitting that yourself! \$\endgroup\$
    – Adalynn
    Jul 16, 2017 at 13:26
  • \$\begingroup\$ I've got a different 18 byte solution closer to my original, I personal like this one better: ṀḊŒPðḍ@þ@⁹Sḟ1ðÐḟḢL \$\endgroup\$
    – Adalynn
    Jul 16, 2017 at 13:29
  • \$\begingroup\$ Woah... ṀḊ actually is a really cool trick! \$\endgroup\$
    – Adalynn
    Jul 16, 2017 at 13:30
  • \$\begingroup\$ Whoops, that doesn't work, and neither does my rewrite! This should output 0, not 1 \$\endgroup\$
    – Adalynn
    Jul 16, 2017 at 13:48
2
\$\begingroup\$

Julia, 91 bytes

x->(t=[];for i in x z=findfirst(x->x==0,i%(2:maximum(x)));z∈t?1:push!(t,z) end;length(t))
\$\endgroup\$
4
  • \$\begingroup\$ Um ... did you forget to include a link within the language name, or is it actually named "[Julia]"? \$\endgroup\$
    – Adalynn
    Jul 16, 2017 at 15:04
  • \$\begingroup\$ You are right, the name is Julia without brackets \$\endgroup\$
    – Tanj
    Jul 16, 2017 at 15:08
  • \$\begingroup\$ You might want to fix that on your other answers as well! \$\endgroup\$
    – Adalynn
    Jul 16, 2017 at 15:09
  • \$\begingroup\$ Wow, that was a lot of answers! And if you want to insert a link, the syntax is [Text to display](link to website) \$\endgroup\$
    – Adalynn
    Jul 16, 2017 at 15:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.