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\$
  • \$\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 '17 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 '17 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\$ – Post Rock Garf Hunter Jul 15 '17 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\$ – Peter Taylor Jul 15 '17 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\$ – Peter Taylor Jul 15 '17 at 16:16
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\$
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\$
  • \$\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\$ – Christian Sievers Jul 17 '17 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\$ – Anders Kaseorg Jul 17 '17 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\$
  • \$\begingroup\$ Nice use of Check \$\endgroup\$ – Keyu Gan Jul 16 '17 at 2:27
  • \$\begingroup\$ Why didn't you undelete your first answer once you had a working version? \$\endgroup\$ – Neil Jul 16 '17 at 15:41
  • \$\begingroup\$ Because this was a totally new approach? Is there a problem? \$\endgroup\$ – J42161217 Jul 16 '17 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\$
  • 1
    \$\begingroup\$ 18 bytes \$\endgroup\$ – Leaky Nun Jul 16 '17 at 12:53
  • \$\begingroup\$ Thanks! And thank you for not submitting that yourself! \$\endgroup\$ – Zacharý Jul 16 '17 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\$ – Zacharý Jul 16 '17 at 13:29
  • \$\begingroup\$ Woah... ṀḊ actually is a really cool trick! \$\endgroup\$ – Zacharý Jul 16 '17 at 13:30
  • \$\begingroup\$ Whoops, that doesn't work, and neither does my rewrite! This should output 0, not 1 \$\endgroup\$ – Zacharý Jul 16 '17 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\$
  • \$\begingroup\$ Um ... did you forget to include a link within the language name, or is it actually named "[Julia]"? \$\endgroup\$ – Zacharý Jul 16 '17 at 15:04
  • \$\begingroup\$ You are right, the name is Julia without brackets \$\endgroup\$ – Tanj Jul 16 '17 at 15:08
  • \$\begingroup\$ You might want to fix that on your other answers as well! \$\endgroup\$ – Zacharý Jul 16 '17 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\$ – Zacharý Jul 16 '17 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.