Mixing
Compute the superset
Clash Royale CLAN TAG#URR8PPP
up vote
7
down vote
favorite
Your task here is simple:
Given a list of integer sets, find the smallest set cover. In other words, find the shortest list of integer sets that contain all the elements in the original list of sets (but no other elements). For example:
[1,5] and [3,9] becomes [1,9] as it contains all of the elements in both [1,5] and [3,9]
[1,3] and [5,9] stays as [1,3] and [5,9], because you don't want to include 4
Sets are notated using range notation: [1,4] means the integers 1,2,3,4. Sets can also be unbounded: [3,] means all of the integers >= 3, and [,-1] means all of the integers <= -1. It is guaranteed that the first element of the range will not be greater than the second.
You can choose to take sets in string notation, or you can use 2-element tuples, using a constant non-integer as the "infinite" value. For example, in Javascript, you could use [3,] to notate all integers >= 3, as long as you consistently used across all test cases.
Test cases:
[1,3] => [1,3]
[1,] => [1,]
[,9] => [,9]
[,] => [,]
[1,3],[4,9] => [1,9]
[1,5],[8,9] => [1,5],[8,9]
[1,5],[1,5] => [1,5]
[1,5],[3,7] => [1,7]
[-10,7],[1,5] => [-10,7]
[1,1],[2,2],[3,3] => [1,3]
[3,7],[1,5] => [1,7]
[1,4],[8,] => [1,4],[8,]
[1,4],[-1,] => [-1,]
[1,4],[,5] => [,5]
[1,4],[,-10] => [1,4],[,-10]
[1,4],[,] => [,]
[1,4],[3,7],[8,9],[11,20] => [1,9],[11,20]
This is code-golf, so make your answer as short as possible!
code-golf set-theory
asked 3 hours ago
Nathan Merrill
6,86336114
 |Â
show 9 more comments
up vote
7
down vote
favorite
Your task here is simple:
Given a list of integer sets, find the smallest set cover. In other words, find the shortest list of integer sets that contain all the elements in the original list of sets (but no other elements). For example:
[1,5] and [3,9] becomes [1,9] as it contains all of the elements in both [1,5] and [3,9]
[1,3] and [5,9] stays as [1,3] and [5,9], because you don't want to include 4
Sets are notated using range notation: [1,4] means the integers 1,2,3,4. Sets can also be unbounded: [3,] means all of the integers >= 3, and [,-1] means all of the integers <= -1. It is guaranteed that the first element of the range will not be greater than the second.
You can choose to take sets in string notation, or you can use 2-element tuples, using a constant non-integer as the "infinite" value. For example, in Javascript, you could use [3,] to notate all integers >= 3, as long as you consistently used across all test cases.
Test cases:
[1,3] => [1,3]
[1,] => [1,]
[,9] => [,9]
[,] => [,]
[1,3],[4,9] => [1,9]
[1,5],[8,9] => [1,5],[8,9]
[1,5],[1,5] => [1,5]
[1,5],[3,7] => [1,7]
[-10,7],[1,5] => [-10,7]
[1,1],[2,2],[3,3] => [1,3]
[3,7],[1,5] => [1,7]
[1,4],[8,] => [1,4],[8,]
[1,4],[-1,] => [-1,]
[1,4],[,5] => [,5]
[1,4],[,-10] => [1,4],[,-10]
[1,4],[,] => [,]
[1,4],[3,7],[8,9],[11,20] => [1,9],[11,20]
This is code-golf, so make your answer as short as possible!
code-golf set-theory
asked 3 hours ago
Nathan Merrill
6,86336114
Related
– Nathan Merrill
3 hours ago
Can I useInfinityinstead?
– Luis felipe De jesus Munoz
3 hours ago
1
@LuisfelipeDejesusMunoz But[1,9]would also contain6,7which aren't in the original set list.
– AdmBorkBork
3 hours ago
1
Isn't this just the union of all the sets? (set cover is a completely different thing)
– user202729
2 hours ago
1
Do the output intervals have to be in sorted order?
– Mnemonic
1 hour ago
 |Â
show 9 more comments
up vote
7
down vote
favorite
up vote
7
down vote
favorite
Your task here is simple:
Given a list of integer sets, find the smallest set cover. In other words, find the shortest list of integer sets that contain all the elements in the original list of sets (but no other elements). For example:
[1,5] and [3,9] becomes [1,9] as it contains all of the elements in both [1,5] and [3,9]
[1,3] and [5,9] stays as [1,3] and [5,9], because you don't want to include 4
Sets are notated using range notation: [1,4] means the integers 1,2,3,4. Sets can also be unbounded: [3,] means all of the integers >= 3, and [,-1] means all of the integers <= -1. It is guaranteed that the first element of the range will not be greater than the second.
You can choose to take sets in string notation, or you can use 2-element tuples, using a constant non-integer as the "infinite" value. For example, in Javascript, you could use [3,] to notate all integers >= 3, as long as you consistently used across all test cases.
Test cases:
[1,3] => [1,3]
[1,] => [1,]
[,9] => [,9]
[,] => [,]
[1,3],[4,9] => [1,9]
[1,5],[8,9] => [1,5],[8,9]
[1,5],[1,5] => [1,5]
[1,5],[3,7] => [1,7]
[-10,7],[1,5] => [-10,7]
[1,1],[2,2],[3,3] => [1,3]
[3,7],[1,5] => [1,7]
[1,4],[8,] => [1,4],[8,]
[1,4],[-1,] => [-1,]
[1,4],[,5] => [,5]
[1,4],[,-10] => [1,4],[,-10]
[1,4],[,] => [,]
[1,4],[3,7],[8,9],[11,20] => [1,9],[11,20]
This is code-golf, so make your answer as short as possible!
code-golf set-theory
asked 3 hours ago
Nathan Merrill
6,86336114
Your task here is simple:
Given a list of integer sets, find the smallest set cover. In other words, find the shortest list of integer sets that contain all the elements in the original list of sets (but no other elements). For example:
[1,5] and [3,9] becomes [1,9] as it contains all of the elements in both [1,5] and [3,9]
[1,3] and [5,9] stays as [1,3] and [5,9], because you don't want to include 4
Sets are notated using range notation: [1,4] means the integers 1,2,3,4. Sets can also be unbounded: [3,] means all of the integers >= 3, and [,-1] means all of the integers <= -1. It is guaranteed that the first element of the range will not be greater than the second.
You can choose to take sets in string notation, or you can use 2-element tuples, using a constant non-integer as the "infinite" value. For example, in Javascript, you could use [3,] to notate all integers >= 3, as long as you consistently used across all test cases.
Test cases:
[1,3] => [1,3]
[1,] => [1,]
[,9] => [,9]
[,] => [,]
[1,3],[4,9] => [1,9]
[1,5],[8,9] => [1,5],[8,9]
[1,5],[1,5] => [1,5]
[1,5],[3,7] => [1,7]
[-10,7],[1,5] => [-10,7]
[1,1],[2,2],[3,3] => [1,3]
[3,7],[1,5] => [1,7]
[1,4],[8,] => [1,4],[8,]
[1,4],[-1,] => [-1,]
[1,4],[,5] => [,5]
[1,4],[,-10] => [1,4],[,-10]
[1,4],[,] => [,]
[1,4],[3,7],[8,9],[11,20] => [1,9],[11,20]
This is code-golf, so make your answer as short as possible!
code-golf set-theory
code-golf set-theory
asked 3 hours ago
Nathan Merrill
6,86336114
asked 3 hours ago
Nathan Merrill
6,86336114
edited 3 hours ago
asked 3 hours ago
Nathan Merrill
6,86336114
asked 3 hours ago
Nathan Merrill
6,86336114
asked 3 hours ago
Nathan Merrill
6,86336114
6,86336114
Related
– Nathan Merrill
3 hours ago
Can I useInfinityinstead?
– Luis felipe De jesus Munoz
3 hours ago
1
@LuisfelipeDejesusMunoz But[1,9]would also contain6,7which aren't in the original set list.
– AdmBorkBork
3 hours ago
1
Isn't this just the union of all the sets? (set cover is a completely different thing)
– user202729
2 hours ago
1
Do the output intervals have to be in sorted order?
– Mnemonic
1 hour ago
 |Â
show 9 more comments
Related
– Nathan Merrill
3 hours ago
Can I useInfinityinstead?
– Luis felipe De jesus Munoz
3 hours ago
1
@LuisfelipeDejesusMunoz But[1,9]would also contain6,7which aren't in the original set list.
– AdmBorkBork
3 hours ago
1
Isn't this just the union of all the sets? (set cover is a completely different thing)
– user202729
2 hours ago
1
Do the output intervals have to be in sorted order?
– Mnemonic
1 hour ago
Related
– Nathan Merrill
3 hours ago
Related
– Nathan Merrill
3 hours ago
Can I use
Infinity instead – Luis felipe De jesus Munoz
3 hours ago
Can I use
Infinity instead – Luis felipe De jesus Munoz
3 hours ago
1
1
@LuisfelipeDejesusMunoz But
[1,9] would also contain 6,7 which aren't in the original set list.– AdmBorkBork
3 hours ago
@LuisfelipeDejesusMunoz But
[1,9] would also contain 6,7 which aren't in the original set list.– AdmBorkBork
3 hours ago
1
1
Isn't this just the union of all the sets? (set cover is a completely different thing)
– user202729
2 hours ago
Isn't this just the union of all the sets? (set cover is a completely different thing)
– user202729
2 hours ago
1
1
Do the output intervals have to be in sorted order?
– Mnemonic
1 hour ago
Do the output intervals have to be in sorted order?
– Mnemonic
1 hour ago
 |Â
show 9 more comments
2 Answers
2
active
oldest
votes
up vote
2
down vote
JavaScript (ES6), 104 bytes
Saved 1 byte thanks to @Shaggy
Expects +/-Infinity for infinite values.
a=>(a.sort(([p],[P])=>p-P).map(m=M=([p,q])=>p<=M+1?M=q>M?q:M:(b.push([m,M]),m=p,M=q),b=),b[0]=[m,M],b)
Try it online!
Commented
a => ( // a = input array
a.sort(([p], [P]) => // sort the intervals by their lower bound; we do not care about
p - P) // the upper bounds for now
.map(m = M = // initialize m and M to non-numeric values
([p, q]) => // for each interval [p, q] in a:
p <= M + 1 ? // if M is a number and p is less than or equal to M + 1:
M = q > M ? q : M // update the maximum M to max(M, q)
: ( // else (we've found a gap, or this is the 1st iteration):
b.push([m, M]), // push the interval [m, M] in b
m = p, // update the minimum m to p
M = q // update the maximum M to q
), //
b = // start with b = empty array
), // end of map()
b[0] = [m, M], b // overwrite the 1st entry of b with the last interval [m, M]
) // and return the final result
answered 2 hours ago
Arnauld
65.2k581275
You could save a bytes by using the parentheses at the end to enclose the whole functions and then replacing the&&with a comma.
– Shaggy
47 mins ago
add a comment |Â
up vote
0
down vote
Python 2, 118 113 112 111 bytes
def f(x,a=):
x.sort();b,c=x[0]
for l,r in x:
if l>c+1:a+=[(b,c)];b,c=l,r
else:c=max(c,r)
return[(b,c)]+a
Try it online!
answered 1 hour ago
Mnemonic
4,3471529
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
JavaScript (ES6), 104 bytes
Saved 1 byte thanks to @Shaggy
Expects +/-Infinity for infinite values.
a=>(a.sort(([p],[P])=>p-P).map(m=M=([p,q])=>p<=M+1?M=q>M?q:M:(b.push([m,M]),m=p,M=q),b=),b[0]=[m,M],b)
Try it online!
Commented
a => ( // a = input array
a.sort(([p], [P]) => // sort the intervals by their lower bound; we do not care about
p - P) // the upper bounds for now
.map(m = M = // initialize m and M to non-numeric values
([p, q]) => // for each interval [p, q] in a:
p <= M + 1 ? // if M is a number and p is less than or equal to M + 1:
M = q > M ? q : M // update the maximum M to max(M, q)
: ( // else (we've found a gap, or this is the 1st iteration):
b.push([m, M]), // push the interval [m, M] in b
m = p, // update the minimum m to p
M = q // update the maximum M to q
), //
b = // start with b = empty array
), // end of map()
b[0] = [m, M], b // overwrite the 1st entry of b with the last interval [m, M]
) // and return the final result
answered 2 hours ago
Arnauld
65.2k581275
You could save a bytes by using the parentheses at the end to enclose the whole functions and then replacing the&&with a comma.
– Shaggy
47 mins ago
add a comment |Â
up vote
2
down vote
JavaScript (ES6), 104 bytes
Saved 1 byte thanks to @Shaggy
Expects +/-Infinity for infinite values.
a=>(a.sort(([p],[P])=>p-P).map(m=M=([p,q])=>p<=M+1?M=q>M?q:M:(b.push([m,M]),m=p,M=q),b=),b[0]=[m,M],b)
Try it online!
Commented
a => ( // a = input array
a.sort(([p], [P]) => // sort the intervals by their lower bound; we do not care about
p - P) // the upper bounds for now
.map(m = M = // initialize m and M to non-numeric values
([p, q]) => // for each interval [p, q] in a:
p <= M + 1 ? // if M is a number and p is less than or equal to M + 1:
M = q > M ? q : M // update the maximum M to max(M, q)
: ( // else (we've found a gap, or this is the 1st iteration):
b.push([m, M]), // push the interval [m, M] in b
m = p, // update the minimum m to p
M = q // update the maximum M to q
), //
b = // start with b = empty array
), // end of map()
b[0] = [m, M], b // overwrite the 1st entry of b with the last interval [m, M]
) // and return the final result
answered 2 hours ago
Arnauld
65.2k581275
You could save a bytes by using the parentheses at the end to enclose the whole functions and then replacing the&&with a comma.
– Shaggy
47 mins ago
add a comment |Â
up vote
2
down vote
up vote
2
down vote
JavaScript (ES6), 104 bytes
Saved 1 byte thanks to @Shaggy
Expects +/-Infinity for infinite values.
a=>(a.sort(([p],[P])=>p-P).map(m=M=([p,q])=>p<=M+1?M=q>M?q:M:(b.push([m,M]),m=p,M=q),b=),b[0]=[m,M],b)
Try it online!
Commented
a => ( // a = input array
a.sort(([p], [P]) => // sort the intervals by their lower bound; we do not care about
p - P) // the upper bounds for now
.map(m = M = // initialize m and M to non-numeric values
([p, q]) => // for each interval [p, q] in a:
p <= M + 1 ? // if M is a number and p is less than or equal to M + 1:
M = q > M ? q : M // update the maximum M to max(M, q)
: ( // else (we've found a gap, or this is the 1st iteration):
b.push([m, M]), // push the interval [m, M] in b
m = p, // update the minimum m to p
M = q // update the maximum M to q
), //
b = // start with b = empty array
), // end of map()
b[0] = [m, M], b // overwrite the 1st entry of b with the last interval [m, M]
) // and return the final result
answered 2 hours ago
Arnauld
65.2k581275
JavaScript (ES6), 104 bytes
Saved 1 byte thanks to @Shaggy
Expects +/-Infinity for infinite values.
a=>(a.sort(([p],[P])=>p-P).map(m=M=([p,q])=>p<=M+1?M=q>M?q:M:(b.push([m,M]),m=p,M=q),b=),b[0]=[m,M],b)
Try it online!
Commented
a => ( // a = input array
a.sort(([p], [P]) => // sort the intervals by their lower bound; we do not care about
p - P) // the upper bounds for now
.map(m = M = // initialize m and M to non-numeric values
([p, q]) => // for each interval [p, q] in a:
p <= M + 1 ? // if M is a number and p is less than or equal to M + 1:
M = q > M ? q : M // update the maximum M to max(M, q)
: ( // else (we've found a gap, or this is the 1st iteration):
b.push([m, M]), // push the interval [m, M] in b
m = p, // update the minimum m to p
M = q // update the maximum M to q
), //
b = // start with b = empty array
), // end of map()
b[0] = [m, M], b // overwrite the 1st entry of b with the last interval [m, M]
) // and return the final result
answered 2 hours ago
Arnauld
65.2k581275
edited 39 mins ago
answered 2 hours ago
Arnauld
65.2k581275
answered 2 hours ago
Arnauld
65.2k581275
answered 2 hours ago
Arnauld
65.2k581275
65.2k581275
You could save a bytes by using the parentheses at the end to enclose the whole functions and then replacing the&&with a comma.
– Shaggy
47 mins ago
add a comment |Â
You could save a bytes by using the parentheses at the end to enclose the whole functions and then replacing the&&with a comma.
– Shaggy
47 mins ago
You could save a bytes by using the parentheses at the end to enclose the whole functions and then replacing the
&& with a comma.– Shaggy
47 mins ago
You could save a bytes by using the parentheses at the end to enclose the whole functions and then replacing the
&& with a comma.– Shaggy
47 mins ago
add a comment |Â
up vote
0
down vote
Python 2, 118 113 112 111 bytes
def f(x,a=):
x.sort();b,c=x[0]
for l,r in x:
if l>c+1:a+=[(b,c)];b,c=l,r
else:c=max(c,r)
return[(b,c)]+a
Try it online!
answered 1 hour ago
Mnemonic
4,3471529
add a comment |Â
up vote
0
down vote
Python 2, 118 113 112 111 bytes
def f(x,a=):
x.sort();b,c=x[0]
for l,r in x:
if l>c+1:a+=[(b,c)];b,c=l,r
else:c=max(c,r)
return[(b,c)]+a
Try it online!
answered 1 hour ago
Mnemonic
4,3471529
add a comment |Â
up vote
0
down vote
up vote
0
down vote
Python 2, 118 113 112 111 bytes
def f(x,a=):
x.sort();b,c=x[0]
for l,r in x:
if l>c+1:a+=[(b,c)];b,c=l,r
else:c=max(c,r)
return[(b,c)]+a
Try it online!
answered 1 hour ago
Mnemonic
4,3471529
Python 2, 118 113 112 111 bytes
def f(x,a=):
x.sort();b,c=x[0]
for l,r in x:
if l>c+1:a+=[(b,c)];b,c=l,r
else:c=max(c,r)
return[(b,c)]+a
Try it online!
answered 1 hour ago
Mnemonic
4,3471529
edited 1 hour ago
answered 1 hour ago
Mnemonic
4,3471529
answered 1 hour ago
Mnemonic
4,3471529
answered 1 hour ago
Mnemonic
4,3471529
4,3471529
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f172922%2fcompute-the-superset%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Related
– Nathan Merrill
3 hours ago
Can I use
Infinityinstead?– Luis felipe De jesus Munoz
3 hours ago
1
@LuisfelipeDejesusMunoz But
[1,9]would also contain6,7which aren't in the original set list.– AdmBorkBork
3 hours ago
1
Isn't this just the union of all the sets? (set cover is a completely different thing)
– user202729
2 hours ago
1
Do the output intervals have to be in sorted order?
– Mnemonic
1 hour ago