Maximum summed subsequences with non-adjacent items Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 23, 2019 at 23:30 UTC (7:30pm US/Eastern) The PPCG Site design is on its way - help us make it awesome! Sandbox for Proposed ChallengesConvert JSON string to Key / Value ArraysGeneralised Array RiffleShortest Longest Common Subsequence CodeFind how many pair elements sums up to NMaximum Maxima!Shuffle a mappingMake this dice game fairDisappearing ElementsSupreme Sum StringValid Badminton Score?
What helicopter has the most rotor blades?
Coin Game with infinite paradox
Etymology of 見舞い
Is Bran literally the world's memory?
Is "ein Herz wie das meine" an antiquated or colloquial use of the possesive pronoun?
“Since the train was delayed for more than an hour, passengers were given a full refund.” – Why is there no article before “passengers”?
Continue tikz picture on next page
Network questions
What is the difference between 准时 and 按时?
Should man-made satellites feature an intelligent inverted "cow catcher"?
Why does my GNOME settings mention "Moto C Plus"?
Who can become a wight?
What were wait-states, and why was it only an issue for PCs?
Who's this lady in the war room?
Is my guitar’s action too high?
Assertions In A Mock Callout Test
Married in secret, can marital status in passport be changed at a later date?
Reflections in a Square
Can gravitational waves pass through a black hole?
/bin/ls sorts differently than just ls
What documents does someone with a long-term visa need to travel to another Schengen country?
What's the connection between Mr. Nancy and fried chicken?
Can I take recommendation from someone I met at a conference?
tabularx column has extra padding at right?
Maximum summed subsequences with non-adjacent items
Announcing the arrival of Valued Associate #679: Cesar Manara
Planned maintenance scheduled April 23, 2019 at 23:30 UTC (7:30pm US/Eastern)
The PPCG Site design is on its way - help us make it awesome!
Sandbox for Proposed ChallengesConvert JSON string to Key / Value ArraysGeneralised Array RiffleShortest Longest Common Subsequence CodeFind how many pair elements sums up to NMaximum Maxima!Shuffle a mappingMake this dice game fairDisappearing ElementsSupreme Sum StringValid Badminton Score?
$begingroup$
Introduction:
Inspired by these two SO questions (no doubt from the same class): print the elements in the subarray of maximum sum without adjacent elements java and Maximum sum of non adjacent elements of an array, to be printed.
Challenge:
Given a list of integers, output a subsequence consisting of non-adjacent elements that have the highest sum. Here some examples:
[1,2,3,-1,-3,2,5]
would result in[1,3,5]
(with a sum of9
) at the 0-based indices[0,2,6]
.[4,5,4,3]
would result in either[4,4]
(with a sum of8
) at the 0-based indices[0,2]
or[5,3]
(also with a sum of8
) at the 0-based indices[1,3]
.[5,5,10,100,10,5]
would result in[5,100,5]
(with a sum of110
) at either the 0-based indices[0,3,5]
or[1,3,5]
.
What's most important about these examples above, the indices containing the elements are at least 2 apart from each other. If we look at the example [5,5,10,100,10,5]
more in depth: we have the following potential subsequence containing non-adjacent items; with their indices below it; with their sums below that:
[[5],[10],[100],[10],[5],[5],[100,5],[10,5],[10,10],[5,5],[5,10],[5,100],[5,5],[5,10],[5,100],[5,10],[5,100,5],[5,100,5],[5,10,5],[5,10,10]] // non-adjacent subsequences
[[5],[ 4],[ 3],[ 2],[1],[0],[ 3,5],[ 2,5],[ 2, 4],[1,5],[1, 4],[1, 3],[0,5],[0, 4],[0, 3],[0, 2],[1, 3,5],[0, 3,5],[0, 2,5],[0, 2, 4]] // at these 0-based indices
[ 5, 10, 100, 10, 5, 5, 105, 15, 20, 10, 15, 105, 10, 15, 105, 15, 110, 110, 20, 25] // with these sums
^ ^ // and these two maximums
Since the maximum sums are 110
, we output [5,100,5]
as result.
Challenge rules:
- You are allowed to output key-value pairs of the index + value. So instead of
[5,100,5]
you can output[[0,5],[3,100],[5,5]]
or[[1,5],[3,100],[5,5]]
as result (or[[1,5],[4,100],[6,5]]
/[[2,5],[4,100],[6,5]]
when 1-based indexing is used instead of 0-based).- If you use key-value pairs, they can also be in reverse or random order, since it's clear which values are meant due to the paired index.
- Outputting just the indices without values isn't allowed. It should either output the values, or the values/indices as key-value pairs (or two separated lists for 'keys' and 'values' of the same size if key-value pairs are not possible in your language of choice).
- You are allowed to output all possible subsequences with the maximum sum instead of just one.
- As you can see from the examples, the input-list can contain negative and duplicated values as well. You can assume the input-integers are within the range $[-999,999]$.
- The output-list cannot be empty and must always contain at least one element (if a list would only contain negative values, a list containing the single lowest negative value would then be output as result - see last two test cases).
- If there is one possible output but for multiple different indices, it's allowed to output both of them even though they might look duplicates. (i.e. the example above, may output
[[5,100,5],[5,100,5]]
for both possible index-combinations).
Test cases:
Input: Possible outputs: At 0-based indices: With sum:
[1,2,3,-1,-3,2,5] [1,3,5] [0,2,6] 9
[4,5,4,3] [4,4]/[5,3] [0,2]/[1,3] 8
[5,5,10,100,10,5] [5,100,5] [0,3,5]/[1,3,5] 110
[10] [10] [0] 10
[1,1,1] [1,1] [0,2] 2
[-3,7,4,-2,4] [7,4] [1,4] 11
[1,7,4,-2] [7] [1] 7
[1,2,-3,-4,5,6,-7] [2,6] [1,5] 8
[800,-31,0,0,421,726] [800,726]/[800,0,726] [0,5]/[0,3,5]/[0,2,5] 1526
[-1,7,8,-5,40,40] [8,40] [2,4]/[2,5] 48
[-5,-18,-3,-1,-10] [-1] [3] -1
[0,-3,-41,0,-99,-2,0] [0]/[0,0]/[0,0,0] [0]/[3]/[6]/[0,3]/
[0,6],[3,6]/[0,3,6] 0
code-golf number array-manipulation integer
$endgroup$
|
show 8 more comments
$begingroup$
Introduction:
Inspired by these two SO questions (no doubt from the same class): print the elements in the subarray of maximum sum without adjacent elements java and Maximum sum of non adjacent elements of an array, to be printed.
Challenge:
Given a list of integers, output a subsequence consisting of non-adjacent elements that have the highest sum. Here some examples:
[1,2,3,-1,-3,2,5]
would result in[1,3,5]
(with a sum of9
) at the 0-based indices[0,2,6]
.[4,5,4,3]
would result in either[4,4]
(with a sum of8
) at the 0-based indices[0,2]
or[5,3]
(also with a sum of8
) at the 0-based indices[1,3]
.[5,5,10,100,10,5]
would result in[5,100,5]
(with a sum of110
) at either the 0-based indices[0,3,5]
or[1,3,5]
.
What's most important about these examples above, the indices containing the elements are at least 2 apart from each other. If we look at the example [5,5,10,100,10,5]
more in depth: we have the following potential subsequence containing non-adjacent items; with their indices below it; with their sums below that:
[[5],[10],[100],[10],[5],[5],[100,5],[10,5],[10,10],[5,5],[5,10],[5,100],[5,5],[5,10],[5,100],[5,10],[5,100,5],[5,100,5],[5,10,5],[5,10,10]] // non-adjacent subsequences
[[5],[ 4],[ 3],[ 2],[1],[0],[ 3,5],[ 2,5],[ 2, 4],[1,5],[1, 4],[1, 3],[0,5],[0, 4],[0, 3],[0, 2],[1, 3,5],[0, 3,5],[0, 2,5],[0, 2, 4]] // at these 0-based indices
[ 5, 10, 100, 10, 5, 5, 105, 15, 20, 10, 15, 105, 10, 15, 105, 15, 110, 110, 20, 25] // with these sums
^ ^ // and these two maximums
Since the maximum sums are 110
, we output [5,100,5]
as result.
Challenge rules:
- You are allowed to output key-value pairs of the index + value. So instead of
[5,100,5]
you can output[[0,5],[3,100],[5,5]]
or[[1,5],[3,100],[5,5]]
as result (or[[1,5],[4,100],[6,5]]
/[[2,5],[4,100],[6,5]]
when 1-based indexing is used instead of 0-based).- If you use key-value pairs, they can also be in reverse or random order, since it's clear which values are meant due to the paired index.
- Outputting just the indices without values isn't allowed. It should either output the values, or the values/indices as key-value pairs (or two separated lists for 'keys' and 'values' of the same size if key-value pairs are not possible in your language of choice).
- You are allowed to output all possible subsequences with the maximum sum instead of just one.
- As you can see from the examples, the input-list can contain negative and duplicated values as well. You can assume the input-integers are within the range $[-999,999]$.
- The output-list cannot be empty and must always contain at least one element (if a list would only contain negative values, a list containing the single lowest negative value would then be output as result - see last two test cases).
- If there is one possible output but for multiple different indices, it's allowed to output both of them even though they might look duplicates. (i.e. the example above, may output
[[5,100,5],[5,100,5]]
for both possible index-combinations).
Test cases:
Input: Possible outputs: At 0-based indices: With sum:
[1,2,3,-1,-3,2,5] [1,3,5] [0,2,6] 9
[4,5,4,3] [4,4]/[5,3] [0,2]/[1,3] 8
[5,5,10,100,10,5] [5,100,5] [0,3,5]/[1,3,5] 110
[10] [10] [0] 10
[1,1,1] [1,1] [0,2] 2
[-3,7,4,-2,4] [7,4] [1,4] 11
[1,7,4,-2] [7] [1] 7
[1,2,-3,-4,5,6,-7] [2,6] [1,5] 8
[800,-31,0,0,421,726] [800,726]/[800,0,726] [0,5]/[0,3,5]/[0,2,5] 1526
[-1,7,8,-5,40,40] [8,40] [2,4]/[2,5] 48
[-5,-18,-3,-1,-10] [-1] [3] -1
[0,-3,-41,0,-99,-2,0] [0]/[0,0]/[0,0,0] [0]/[3]/[6]/[0,3]/
[0,6],[3,6]/[0,3,6] 0
code-golf number array-manipulation integer
$endgroup$
$begingroup$
If there is more than one identical set (but from different indices) is it ok to list all of them? e.g.[5,100,5]
twice for your third example.
$endgroup$
– Nick Kennedy
Apr 17 at 13:53
1
$begingroup$
powerset
is a set of subsets isn't it? but it looks like you are returning a set of subsequences? [4,5,4,3] would result in either [4,4] where [4,4] is clearly not a set.
$endgroup$
– Expired Data
Apr 17 at 14:19
1
$begingroup$
@Arnauld Yes, if the values are key-value pairs with their index it's clear which indexed values are meant in the input, so they can be in any order. Will also edit this into the challenge description.
$endgroup$
– Kevin Cruijssen
Apr 17 at 16:47
2
$begingroup$
Just to be sure: outputting the indices isn't an option, is it?
$endgroup$
– Shaggy
Apr 17 at 22:19
1
$begingroup$
The classical term is "subsequence". This has the same problem of people thinking of contiguous subsequences, though. I would say "subset" if we were actually working with sets here, but these are definitely sequences - order matters and duplicates are allowed.
$endgroup$
– user2357112
Apr 18 at 9:18
|
show 8 more comments
$begingroup$
Introduction:
Inspired by these two SO questions (no doubt from the same class): print the elements in the subarray of maximum sum without adjacent elements java and Maximum sum of non adjacent elements of an array, to be printed.
Challenge:
Given a list of integers, output a subsequence consisting of non-adjacent elements that have the highest sum. Here some examples:
[1,2,3,-1,-3,2,5]
would result in[1,3,5]
(with a sum of9
) at the 0-based indices[0,2,6]
.[4,5,4,3]
would result in either[4,4]
(with a sum of8
) at the 0-based indices[0,2]
or[5,3]
(also with a sum of8
) at the 0-based indices[1,3]
.[5,5,10,100,10,5]
would result in[5,100,5]
(with a sum of110
) at either the 0-based indices[0,3,5]
or[1,3,5]
.
What's most important about these examples above, the indices containing the elements are at least 2 apart from each other. If we look at the example [5,5,10,100,10,5]
more in depth: we have the following potential subsequence containing non-adjacent items; with their indices below it; with their sums below that:
[[5],[10],[100],[10],[5],[5],[100,5],[10,5],[10,10],[5,5],[5,10],[5,100],[5,5],[5,10],[5,100],[5,10],[5,100,5],[5,100,5],[5,10,5],[5,10,10]] // non-adjacent subsequences
[[5],[ 4],[ 3],[ 2],[1],[0],[ 3,5],[ 2,5],[ 2, 4],[1,5],[1, 4],[1, 3],[0,5],[0, 4],[0, 3],[0, 2],[1, 3,5],[0, 3,5],[0, 2,5],[0, 2, 4]] // at these 0-based indices
[ 5, 10, 100, 10, 5, 5, 105, 15, 20, 10, 15, 105, 10, 15, 105, 15, 110, 110, 20, 25] // with these sums
^ ^ // and these two maximums
Since the maximum sums are 110
, we output [5,100,5]
as result.
Challenge rules:
- You are allowed to output key-value pairs of the index + value. So instead of
[5,100,5]
you can output[[0,5],[3,100],[5,5]]
or[[1,5],[3,100],[5,5]]
as result (or[[1,5],[4,100],[6,5]]
/[[2,5],[4,100],[6,5]]
when 1-based indexing is used instead of 0-based).- If you use key-value pairs, they can also be in reverse or random order, since it's clear which values are meant due to the paired index.
- Outputting just the indices without values isn't allowed. It should either output the values, or the values/indices as key-value pairs (or two separated lists for 'keys' and 'values' of the same size if key-value pairs are not possible in your language of choice).
- You are allowed to output all possible subsequences with the maximum sum instead of just one.
- As you can see from the examples, the input-list can contain negative and duplicated values as well. You can assume the input-integers are within the range $[-999,999]$.
- The output-list cannot be empty and must always contain at least one element (if a list would only contain negative values, a list containing the single lowest negative value would then be output as result - see last two test cases).
- If there is one possible output but for multiple different indices, it's allowed to output both of them even though they might look duplicates. (i.e. the example above, may output
[[5,100,5],[5,100,5]]
for both possible index-combinations).
Test cases:
Input: Possible outputs: At 0-based indices: With sum:
[1,2,3,-1,-3,2,5] [1,3,5] [0,2,6] 9
[4,5,4,3] [4,4]/[5,3] [0,2]/[1,3] 8
[5,5,10,100,10,5] [5,100,5] [0,3,5]/[1,3,5] 110
[10] [10] [0] 10
[1,1,1] [1,1] [0,2] 2
[-3,7,4,-2,4] [7,4] [1,4] 11
[1,7,4,-2] [7] [1] 7
[1,2,-3,-4,5,6,-7] [2,6] [1,5] 8
[800,-31,0,0,421,726] [800,726]/[800,0,726] [0,5]/[0,3,5]/[0,2,5] 1526
[-1,7,8,-5,40,40] [8,40] [2,4]/[2,5] 48
[-5,-18,-3,-1,-10] [-1] [3] -1
[0,-3,-41,0,-99,-2,0] [0]/[0,0]/[0,0,0] [0]/[3]/[6]/[0,3]/
[0,6],[3,6]/[0,3,6] 0
code-golf number array-manipulation integer
$endgroup$
Introduction:
Inspired by these two SO questions (no doubt from the same class): print the elements in the subarray of maximum sum without adjacent elements java and Maximum sum of non adjacent elements of an array, to be printed.
Challenge:
Given a list of integers, output a subsequence consisting of non-adjacent elements that have the highest sum. Here some examples:
[1,2,3,-1,-3,2,5]
would result in[1,3,5]
(with a sum of9
) at the 0-based indices[0,2,6]
.[4,5,4,3]
would result in either[4,4]
(with a sum of8
) at the 0-based indices[0,2]
or[5,3]
(also with a sum of8
) at the 0-based indices[1,3]
.[5,5,10,100,10,5]
would result in[5,100,5]
(with a sum of110
) at either the 0-based indices[0,3,5]
or[1,3,5]
.
What's most important about these examples above, the indices containing the elements are at least 2 apart from each other. If we look at the example [5,5,10,100,10,5]
more in depth: we have the following potential subsequence containing non-adjacent items; with their indices below it; with their sums below that:
[[5],[10],[100],[10],[5],[5],[100,5],[10,5],[10,10],[5,5],[5,10],[5,100],[5,5],[5,10],[5,100],[5,10],[5,100,5],[5,100,5],[5,10,5],[5,10,10]] // non-adjacent subsequences
[[5],[ 4],[ 3],[ 2],[1],[0],[ 3,5],[ 2,5],[ 2, 4],[1,5],[1, 4],[1, 3],[0,5],[0, 4],[0, 3],[0, 2],[1, 3,5],[0, 3,5],[0, 2,5],[0, 2, 4]] // at these 0-based indices
[ 5, 10, 100, 10, 5, 5, 105, 15, 20, 10, 15, 105, 10, 15, 105, 15, 110, 110, 20, 25] // with these sums
^ ^ // and these two maximums
Since the maximum sums are 110
, we output [5,100,5]
as result.
Challenge rules:
- You are allowed to output key-value pairs of the index + value. So instead of
[5,100,5]
you can output[[0,5],[3,100],[5,5]]
or[[1,5],[3,100],[5,5]]
as result (or[[1,5],[4,100],[6,5]]
/[[2,5],[4,100],[6,5]]
when 1-based indexing is used instead of 0-based).- If you use key-value pairs, they can also be in reverse or random order, since it's clear which values are meant due to the paired index.
- Outputting just the indices without values isn't allowed. It should either output the values, or the values/indices as key-value pairs (or two separated lists for 'keys' and 'values' of the same size if key-value pairs are not possible in your language of choice).
- You are allowed to output all possible subsequences with the maximum sum instead of just one.
- As you can see from the examples, the input-list can contain negative and duplicated values as well. You can assume the input-integers are within the range $[-999,999]$.
- The output-list cannot be empty and must always contain at least one element (if a list would only contain negative values, a list containing the single lowest negative value would then be output as result - see last two test cases).
- If there is one possible output but for multiple different indices, it's allowed to output both of them even though they might look duplicates. (i.e. the example above, may output
[[5,100,5],[5,100,5]]
for both possible index-combinations).
Test cases:
Input: Possible outputs: At 0-based indices: With sum:
[1,2,3,-1,-3,2,5] [1,3,5] [0,2,6] 9
[4,5,4,3] [4,4]/[5,3] [0,2]/[1,3] 8
[5,5,10,100,10,5] [5,100,5] [0,3,5]/[1,3,5] 110
[10] [10] [0] 10
[1,1,1] [1,1] [0,2] 2
[-3,7,4,-2,4] [7,4] [1,4] 11
[1,7,4,-2] [7] [1] 7
[1,2,-3,-4,5,6,-7] [2,6] [1,5] 8
[800,-31,0,0,421,726] [800,726]/[800,0,726] [0,5]/[0,3,5]/[0,2,5] 1526
[-1,7,8,-5,40,40] [8,40] [2,4]/[2,5] 48
[-5,-18,-3,-1,-10] [-1] [3] -1
[0,-3,-41,0,-99,-2,0] [0]/[0,0]/[0,0,0] [0]/[3]/[6]/[0,3]/
[0,6],[3,6]/[0,3,6] 0
code-golf number array-manipulation integer
code-golf number array-manipulation integer
edited Apr 18 at 9:23
Kevin Cruijssen
asked Apr 17 at 13:19
Kevin CruijssenKevin Cruijssen
43.4k573222
43.4k573222
$begingroup$
If there is more than one identical set (but from different indices) is it ok to list all of them? e.g.[5,100,5]
twice for your third example.
$endgroup$
– Nick Kennedy
Apr 17 at 13:53
1
$begingroup$
powerset
is a set of subsets isn't it? but it looks like you are returning a set of subsequences? [4,5,4,3] would result in either [4,4] where [4,4] is clearly not a set.
$endgroup$
– Expired Data
Apr 17 at 14:19
1
$begingroup$
@Arnauld Yes, if the values are key-value pairs with their index it's clear which indexed values are meant in the input, so they can be in any order. Will also edit this into the challenge description.
$endgroup$
– Kevin Cruijssen
Apr 17 at 16:47
2
$begingroup$
Just to be sure: outputting the indices isn't an option, is it?
$endgroup$
– Shaggy
Apr 17 at 22:19
1
$begingroup$
The classical term is "subsequence". This has the same problem of people thinking of contiguous subsequences, though. I would say "subset" if we were actually working with sets here, but these are definitely sequences - order matters and duplicates are allowed.
$endgroup$
– user2357112
Apr 18 at 9:18
|
show 8 more comments
$begingroup$
If there is more than one identical set (but from different indices) is it ok to list all of them? e.g.[5,100,5]
twice for your third example.
$endgroup$
– Nick Kennedy
Apr 17 at 13:53
1
$begingroup$
powerset
is a set of subsets isn't it? but it looks like you are returning a set of subsequences? [4,5,4,3] would result in either [4,4] where [4,4] is clearly not a set.
$endgroup$
– Expired Data
Apr 17 at 14:19
1
$begingroup$
@Arnauld Yes, if the values are key-value pairs with their index it's clear which indexed values are meant in the input, so they can be in any order. Will also edit this into the challenge description.
$endgroup$
– Kevin Cruijssen
Apr 17 at 16:47
2
$begingroup$
Just to be sure: outputting the indices isn't an option, is it?
$endgroup$
– Shaggy
Apr 17 at 22:19
1
$begingroup$
The classical term is "subsequence". This has the same problem of people thinking of contiguous subsequences, though. I would say "subset" if we were actually working with sets here, but these are definitely sequences - order matters and duplicates are allowed.
$endgroup$
– user2357112
Apr 18 at 9:18
$begingroup$
If there is more than one identical set (but from different indices) is it ok to list all of them? e.g.
[5,100,5]
twice for your third example.$endgroup$
– Nick Kennedy
Apr 17 at 13:53
$begingroup$
If there is more than one identical set (but from different indices) is it ok to list all of them? e.g.
[5,100,5]
twice for your third example.$endgroup$
– Nick Kennedy
Apr 17 at 13:53
1
1
$begingroup$
powerset
is a set of subsets isn't it? but it looks like you are returning a set of subsequences? [4,5,4,3] would result in either [4,4] where [4,4] is clearly not a set.$endgroup$
– Expired Data
Apr 17 at 14:19
$begingroup$
powerset
is a set of subsets isn't it? but it looks like you are returning a set of subsequences? [4,5,4,3] would result in either [4,4] where [4,4] is clearly not a set.$endgroup$
– Expired Data
Apr 17 at 14:19
1
1
$begingroup$
@Arnauld Yes, if the values are key-value pairs with their index it's clear which indexed values are meant in the input, so they can be in any order. Will also edit this into the challenge description.
$endgroup$
– Kevin Cruijssen
Apr 17 at 16:47
$begingroup$
@Arnauld Yes, if the values are key-value pairs with their index it's clear which indexed values are meant in the input, so they can be in any order. Will also edit this into the challenge description.
$endgroup$
– Kevin Cruijssen
Apr 17 at 16:47
2
2
$begingroup$
Just to be sure: outputting the indices isn't an option, is it?
$endgroup$
– Shaggy
Apr 17 at 22:19
$begingroup$
Just to be sure: outputting the indices isn't an option, is it?
$endgroup$
– Shaggy
Apr 17 at 22:19
1
1
$begingroup$
The classical term is "subsequence". This has the same problem of people thinking of contiguous subsequences, though. I would say "subset" if we were actually working with sets here, but these are definitely sequences - order matters and duplicates are allowed.
$endgroup$
– user2357112
Apr 18 at 9:18
$begingroup$
The classical term is "subsequence". This has the same problem of people thinking of contiguous subsequences, though. I would say "subset" if we were actually working with sets here, but these are definitely sequences - order matters and duplicates are allowed.
$endgroup$
– user2357112
Apr 18 at 9:18
|
show 8 more comments
20 Answers
20
active
oldest
votes
$begingroup$
Haskell, 60 bytes
snd.([]%)
r%(h:t)=max(r%t)$(r++[h])%drop 1t
r%_=(sum r<$r,r)
Try it online!
The helper function %
recursively branches on choosing whether the include the first element and drop the second, or to skip the first element. It takes the maximum of all outcomes, which are tuples whose first element is the sum, and whose second element is the corresponding list which is extracted for the output.
To handle the rule that the empty list is disallowed even if it would have the smallest trick, we do a cute trick of writing sum r<$r
rather than sum r
.This makes a list whose elements all are sum r
and whose length is that of r
. That way, when we choose the maximum, we prioritize any list over an empty r
, but otherwise comparisons depend on the first element which is sum r
.
$endgroup$
add a comment |
$begingroup$
R, 136 125 bytes
function(l,G=unlist(Map(combn,list(y<-seq(a=l)),y,c(function(x)'if'(all(diff(x)>1),l[x],-Inf)),F),F))G[which.max(Map(sum,G))]
Try it online!
-6 bytes thanks to digEmAll, who incidentally also outgolfed me.
Returns the shortest subsequence as a list
, breaking ties on lexicographically first by indices.
Brute-force generates all index subsequences, then Filter
s for those that are non-adjacent, i.e., where all(diff(x)>1)
. Then subsets [
into l
using these indices, selecting [[
the first one where the sum is the max (which.max
).
I'm pretty sure this is the first R answer I've ever written that uses sad, Filter
!Filter
is ungolfy, no wonder I've never used it...
$endgroup$
$begingroup$
130
$endgroup$
– digEmAll
yesterday
$begingroup$
@digEmAll thanks!
$endgroup$
– Giuseppe
11 hours ago
add a comment |
$begingroup$
05AB1E, 14 bytes
Saved 1 byte thanks to Kevin Cruijssen
ā<æʒĆ¥≠W}èΣO}θ
Try it online!
or as a Test Suite
Explanation
ā< # push [0 ... len(input)-1]
æ # compute powerset
ʒ } # filter, keep lists where:
≠W # no element is 1 in the
¥ # deltas
Ć # of the list with the head appended
è # index into the input with each
ΣO} # sort by sum
θ # take the last element
$endgroup$
$begingroup$
You may not be happy, but it's still 4 bytes shorter than my initial solution. ;) And you can golf 1 more changing¤ª
toĆ
.
$endgroup$
– Kevin Cruijssen
Apr 17 at 16:40
$begingroup$
@KevinCruijssen: Oh yeah! For some reason I had convinced myself I needed a repeat element at the end. Thanks!
$endgroup$
– Emigna
Apr 17 at 17:00
add a comment |
$begingroup$
Brachylog (v2), 14 bytes
~ba~c∋₁ᵐᶠ+ᵒt
Try it online!
Function submission; input from the left, output from the right, as usual. Very slow; a five-element list is probably the maximum for testing on TIO.
~ba~c∋₁ᵐᶠ+ᵒt
~b Prepend an arbitrary element to the input
a Take a prefix or suffix of the resulting list
~c Ordered partition into contiguous sublists
∋₁ Take the second element
ᵐ of each sublist
ᶠ Find all possible ways to do this
+ᵒ Sort by sum
t Take the greatest
The results we get from prefixes aren't incorrect, but also aren't interesting; all possible results are generated via taking a suffix (which is possibly the list itself, but cannot be empty), but "suffix" is more verbose in Brachylog than "prefix or suffix", so I went with the version that's terser (and less efficient but still correct). The basic idea is that for each element we want in the output list, the partition into contiguous sublists needs to place that element and the element before into the same sublist (because the element is the second element of the sublist), so two consecutive elements can't appear in the result. On the other hand, it's fairly clear that any list without two consecutive elements can appear in the result. So once we have all possible candidate lists, we can just take the sums of all of them and see which one is largest.
$endgroup$
add a comment |
$begingroup$
Husk, 11 bytes
►Σ†!¹mü≈tṖŀ
Try it online!
Explanation
►Σ†!¹mü≈tṖŀ Implicit input, say L=[4,5,3,4].
ŀ Indices: [1,2,3,4]
Ṗ Powerset: [[],[1],[2],[1,2],..,[1,2,3,4]]
t Tail (remove the empty list): [[1],[2],[1,2],..,[1,2,3,4]]
m For each,
ü de-duplicate by
≈ differing by at most 1.
For example, [1,2,4] becomes [1,4].
† Deep map
!¹ indexing into L: [[4],[5],[4],..,[5,4],[4,3]]
► Maximum by
Σ sum: [5,4]
$endgroup$
add a comment |
$begingroup$
Jelly, 16 14 bytes
JŒPḊf’$ÐḟịµSÞṪ
Try it online!
Thanks to @EriktheOutgolfer for saving 2 bytes!
$endgroup$
$begingroup$
14 bytes.
$endgroup$
– Erik the Outgolfer
Apr 17 at 18:17
add a comment |
$begingroup$
JavaScript (ES6), 138 132 130 129 126 bytes
Outputs key-value pairs.
a=>a.reduce((a,x,i)=>[...a,...a.map(y=>[[x,i],...y])],[[]]).map(m=a=>a.some(s=p=([v,i])=>p-(s=~~s+v,p=i)<2)|s<m||(r=a,m=s))&&r
Try it online!
Step 1
We first compute the powerset of the input with $[value, index]$ pairs.
a.reduce((a, x, i) => // for each value x at position i:
[ // update a[] to a new array consisting of:
...a, // all previous entries
...a.map(y => // for each value y in a[]:
[[x, i], ...y] // append [x, i], followed by all original entries
) // end of map()
], // end of new array
[[]] // start with a = [[]]
) // end of reduce()
Step 2
We then look for the maximum sum $m$ among these sets, discarding sets with at least two adjacent elements. The best set is stored in $r$.
.map(m = // initialize m to a non-numeric value
a => // for each entry a[] in the powerset:
a.some(s = p = // initialize s and p to non numeric values
([v, i]) => // for each value v and each index i in a[]:
p - ( // compute p - i
s = ~~s + v, // add v to s
p = i // update p to i
) < 2 // if p - i is less than 2, yield true
) | // end of some()
s < m || // unless some() was truthy or s is less than m,
(r = a, m = s) // save a[] in r[] and update m to s
) && r // end of map(); return r[]
$endgroup$
add a comment |
$begingroup$
T-SQL, 122 119 bytes
Input is a table variable.
This query picks all elements from the table variable, combining these with all non-adjacent elements with higher position values and show the text generated for the highest sum of these values.
WITH C(y,j,v)as(SELECT*,x*1FROM @
UNION ALL
SELECT y+','+x,i,v+x
FROM @ JOIN C ON j+1<i)SELECT
TOP 1y FROM C ORDER BY-v
Try it online ungolfed
$endgroup$
add a comment |
$begingroup$
Haskell, 81 80 bytes
snd.maximum.map((,)=<<sum).tail.f
f(a:b:c)=f(b:c)++map(a:)(f c)
f a=[]:map(:[])a
Try it online!
f
builds all valid subsequences by either skipping the next element (f(b:c)
) or using it and skipping the next (map(a:)(f c)
) and recursively work on the rest. For the result, build all subsequences (f
), drop the empty subsequence (which occurs first in the list: tail
), make pairs (<sum>,<subsequence>)
(map((,)=<<sum)
), find the maximum (pairs are compared in lexicographical order) -> maximum
) and drop the sum (snd
).
Edit: -1 byte thanks to @Lynn.
$endgroup$
1
$begingroup$
map(:[])a
is a byte shorter than(pure<$>a)
^^
$endgroup$
– Lynn
Apr 18 at 18:38
add a comment |
$begingroup$
Wolfram Language (Mathematica), 144 bytes
If[Max[a=#]>(d=Max[m=Tr/@(g=a[[#]]&/@Select[Subsets[Range[x=Length@#],2,x]&@#,FreeQ[Differences@#,1]&]&@a)]),Max@a,g[[#]]&@@@Position[m,d]]&
Try it online!
$endgroup$
add a comment |
$begingroup$
Pyth, 19 bytes
esDm@LQdtf!q#1.+TyU
Try it online here, or verify all the test cases at once here.
esDm@LQdtf!q#1.+TyUQ Implicit: Q=eval(input())
Trailing Q inferred
UQ Generate range [0-len(Q))
y Take the powerset of the above
f Filter keep elements of the above, as T, using:
.+T Take differences of consecutive elements of T
q#1 Keep those differences equal to 1
! Logical NOT - empty lists evaluate to true, populated ones to false
Result of the filter is those sets without consecutive numbers
t Drop the first element (empty set)
m Map the remaining sets, as d, using:
L d For each element of d...
@ Q ... get the element in Q with that index
sD Order the sets by their sum
e Take the last element, implicit print
$endgroup$
add a comment |
$begingroup$
Gaia, 24 bytes
e:w;ċz⟨ọ1>¦ẏ⟩⁇‼⁇E‡ev2%Σ⌠
Try it online!
Ugh, E‡
does some weird stuff...according to the documentation, it should do something like "given length i
set of lists X
and length j
set of indices Y
, return X[i][Y[j]]
", but instead returns [X[i][Y[j]] X[i][Y[-j]]
where negative indexing represents the complement, so we have to do ev2%
to extract only the ones we want.
e | eval as a list l
: | dup
w | wrap as a list
; | push l again
ċ | push [1..len(l)]
z | push all subsets of [1..len(l)] -- index powerset.
⟨ ⟩⁇ | filter this for:
ọ | deltas
1>¦ | are greater than 1
ẏ | all (all deltas greater than 1)
‼⁇ | filter for non-empty lists
E‡ | table extract elements. Given l and index set i, this pushes
| [l[i] l[setdiff(1..l,i)]] for some reason
ev2% | get the l[i] only by unlisting, reversing, and taking every other element
Σ⌠ | Get the one with the maximum sum
$endgroup$
$begingroup$
Out of curiosity, why does the output have two trailing]]
instead of one?
$endgroup$
– Kevin Cruijssen
Apr 18 at 19:14
$begingroup$
@KevinCruijssen Just another fun quirk of the interpreter; all lists are printed out like that, so[[1] [2]]
gets printed[[1]] [2]]]]
which makes it super hard to read/debug list output.
$endgroup$
– Giuseppe
Apr 18 at 19:27
$begingroup$
I think it's because of the expressionre.sub(" ?$","]",result)
in the interpreter which should instead bere.sub(" +$","]",result)
but my python is super bad.
$endgroup$
– Giuseppe
Apr 18 at 19:37
add a comment |
$begingroup$
J, 54 bytes
[:(>@:@/:+/&>)]<@#~"1[:(#~0=1 1+/@E."1])[:#:@.@i.2^#
Try it online!
$endgroup$
add a comment |
$begingroup$
R, 108 107 bytes
function(v,M=-Inf)for(j in J<-seq(a=v))for(i in combn(J,j,,F))if(all(diff(i)>1)&sum(v[i])>sum(M))M=v[i]
M
Try it online!
-1 thanks to @Giuseppe
$endgroup$
add a comment |
$begingroup$
Haskell, 300 168 bytes
import Data.List
h[]=1>2
h(x:y)=fst$foldl(a c->((fst a)&&(c-snd a>1),c))(1<2,x)y
z=snd.last.sortOn fst.map((,)=<<sum.snd).filter(h.fst).map unzip.subsequences.zip[0..]
Try it online!
-132 bytes thanks to all the feedback from @nimi :)
Original
Ungolfed (original)
import Data.List
import Data.Function
f :: [Int] -> [(Int, Int)] -- attach indices for later use
f [] = []
f xs = zip xs [0..length xs]
g :: [[(Int, Int)]] -> [([Int], [Int])] -- rearrange into list of tuples
g [] = []
g (x:xs) = (map fst x, map snd x) : g xs
h :: [Int] -> Bool -- predicate that checks if the indices are at least 2 apart from each other
h [] = False
h (x:xs) = fst $ foldl (acc curr -> ((fst acc) && (curr - snd acc > 1), curr)) (True, x) xs
j :: [([Int], [Int])] -> [([Int], [Int])] -- remove sets that don't satisfy the condition
j xs = filter ((elements, indices) -> h indices) xs
k :: [([Int], [Int])] -> [(Int, ([Int], [Int]))] -- calculate some of elements
k xs = map ((elements, indices) -> (foldl1 (+) elements, (elements, indices))) xs
l :: [(Int, ([Int], [Int]))] -> ([Int], [Int]) -- grab max
l xs = snd $ last $ sortBy (compare `on` fst) xs
z -- put things together
```
New contributor
$endgroup$
1
$begingroup$
Some tips: flip the element and its index within the pairs returned byf
:f x=zip[0..length x]x
, sof
becomesf=zip[0..]
.g
is justg=map unzip
. The function to filter with inj
ish.fst
(<- flipped pairs!).j=filter(h.fst)
. Thefoldl1+
fromk
issum
and with a pointfree pair makingk=map((,)=<<sum.snd)
.sortBy(...)
can be replaced bysortOn fst
:l=snd.last.sortOn fst
. Finally as you are using all functions only once, you can inline them into a single pointfree expression:z=snd.last.sortOn fst.map((,)=<<sum.snd).filter(h.fst).map unzip.subsequences.zip[0..]
$endgroup$
– nimi
Apr 17 at 16:31
$begingroup$
.... Try it online!.
$endgroup$
– nimi
Apr 17 at 16:31
$begingroup$
oh, and no need to importData.Function
anymore.
$endgroup$
– nimi
Apr 17 at 16:32
$begingroup$
That's great, thanks for the feedback :)
$endgroup$
– bugs
Apr 17 at 17:05
$begingroup$
Nexth
: we're looking for non-adjacent elements, i.e. the difference of adjacent indices must be>1
.zipWith(-)=<<tail
builds such a list of differences, but fails for the empty list, so we need an additionaltail
on thesubsequences
to get rid of it. Inline again. Try it online!
$endgroup$
– nimi
Apr 17 at 17:27
|
show 1 more comment
$begingroup$
Charcoal, 46 bytes
≔⟦υ⟧ηFθ«≔υζ≔Eη⁺κ⟦ι⟧υ≔⁺ζηη»≔Φ⁺υηιη≔EηΣιζI§η⌕ζ⌈ζ
Try it online! Link is to verbose version of code. Explanation:
≔⟦υ⟧η
The variable u
is predefined with an empty list. This is put in a list which is assigned to h
. These variables act as accumulators. u
contains the sublists that include the latest element of the input q
while h
contains the sublists that do not (and therefore are suitable for appending the next element of the input).
Fθ«
Loop over the elements of the input.
≔υζ
Save the list of sublists that contain the previous element.
≔Eη⁺κ⟦ι⟧υ
Take all of the sublists that do not contain the previous element, append the current element, and save the result as the list of sublists that contain the current element. (I don't use Push
here as I need to clone the list.)
≔⁺ζηη»
Concatenate both previous sublists into the new list of sublists that do not contain the current element.
≔Φ⁺υηιη
Concatenate the sublists one last time and remove the original empty list (which Charcoal can't sum anyway).
≔EηΣιζ
Compute the sums of all of the sublists.
I§η⌕ζ⌈ζ
Find an index of the greatest sum and output the corresponding sublist.
$endgroup$
add a comment |
$begingroup$
Wolfram Language (Mathematica), 70 bytes
MaximalBy[Select[q=Rest@Subsets@#,Or@@(MatchQ[#~Riffle~_]/@q)&],Tr,1]&
Try it online!
High-level search
Select[q=Rest@Subsets@#, ] (*choose nonempty subsets of the input such that*)
Or@@(MatchQ[ ]/@q)& (*there exists a subset of the input which matches*)
#~Riffle~_ (*this list, with an item inserted between adjacent elements*)
MaximalBy[ ,Tr,1]& (*and return one with the greatest total*)
,1
is required so as not to inadvertently return invalid sets (otherwise, for example, an input of 1,1,1
would result in an output of 1,1,1,1,1,1
)
$endgroup$
add a comment |
$begingroup$
Japt -h
, 22 bytes
Êo à k_mÄ øZÃm!gU
fÊñx
Try it
$endgroup$
add a comment |
$begingroup$
Japt -h
, 21 bytes
Ever have one of those challenges where you completely forget how to golf?!
ð¤à fÊk_än ø1îmgUÃñx
Try it
ð¤à fÊk_än ø1îmgUÃñx :Implicit input of array U
ð :Indices of elements that return true when
¤ : Converted to a base-2 string (to account for 0s)
à :Combinations
f :Filter by
Ê : Length (to remove the empty combination)
k_ :Remove elements that return true
än : Deltas
ø1 : Contains 1
à :End remove
® :Map
m : Map
gU : Index into U
à :End map
ñ :Sort by
x : Sum
:Implicit output of last element
$endgroup$
add a comment |
$begingroup$
Python 2, 63 70 65 bytes
f=lambda a:a and max([a[:1],a[:1]+f(a[2:]),f(a[1:])],key=sum)or a
Try it online!
5 bytes thx to ArBo
$endgroup$
$begingroup$
Your test case[1, 7, 4, -2] [1, 4] 5 7
is getting the wrong answer.
$endgroup$
– xnor
2 days ago
$begingroup$
@xnor: fixed now.
$endgroup$
– Chas Brown
2 days ago
$begingroup$
65 bytes
$endgroup$
– ArBo
2 days ago
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "200"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
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
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f183390%2fmaximum-summed-subsequences-with-non-adjacent-items%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
20 Answers
20
active
oldest
votes
20 Answers
20
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Haskell, 60 bytes
snd.([]%)
r%(h:t)=max(r%t)$(r++[h])%drop 1t
r%_=(sum r<$r,r)
Try it online!
The helper function %
recursively branches on choosing whether the include the first element and drop the second, or to skip the first element. It takes the maximum of all outcomes, which are tuples whose first element is the sum, and whose second element is the corresponding list which is extracted for the output.
To handle the rule that the empty list is disallowed even if it would have the smallest trick, we do a cute trick of writing sum r<$r
rather than sum r
.This makes a list whose elements all are sum r
and whose length is that of r
. That way, when we choose the maximum, we prioritize any list over an empty r
, but otherwise comparisons depend on the first element which is sum r
.
$endgroup$
add a comment |
$begingroup$
Haskell, 60 bytes
snd.([]%)
r%(h:t)=max(r%t)$(r++[h])%drop 1t
r%_=(sum r<$r,r)
Try it online!
The helper function %
recursively branches on choosing whether the include the first element and drop the second, or to skip the first element. It takes the maximum of all outcomes, which are tuples whose first element is the sum, and whose second element is the corresponding list which is extracted for the output.
To handle the rule that the empty list is disallowed even if it would have the smallest trick, we do a cute trick of writing sum r<$r
rather than sum r
.This makes a list whose elements all are sum r
and whose length is that of r
. That way, when we choose the maximum, we prioritize any list over an empty r
, but otherwise comparisons depend on the first element which is sum r
.
$endgroup$
add a comment |
$begingroup$
Haskell, 60 bytes
snd.([]%)
r%(h:t)=max(r%t)$(r++[h])%drop 1t
r%_=(sum r<$r,r)
Try it online!
The helper function %
recursively branches on choosing whether the include the first element and drop the second, or to skip the first element. It takes the maximum of all outcomes, which are tuples whose first element is the sum, and whose second element is the corresponding list which is extracted for the output.
To handle the rule that the empty list is disallowed even if it would have the smallest trick, we do a cute trick of writing sum r<$r
rather than sum r
.This makes a list whose elements all are sum r
and whose length is that of r
. That way, when we choose the maximum, we prioritize any list over an empty r
, but otherwise comparisons depend on the first element which is sum r
.
$endgroup$
Haskell, 60 bytes
snd.([]%)
r%(h:t)=max(r%t)$(r++[h])%drop 1t
r%_=(sum r<$r,r)
Try it online!
The helper function %
recursively branches on choosing whether the include the first element and drop the second, or to skip the first element. It takes the maximum of all outcomes, which are tuples whose first element is the sum, and whose second element is the corresponding list which is extracted for the output.
To handle the rule that the empty list is disallowed even if it would have the smallest trick, we do a cute trick of writing sum r<$r
rather than sum r
.This makes a list whose elements all are sum r
and whose length is that of r
. That way, when we choose the maximum, we prioritize any list over an empty r
, but otherwise comparisons depend on the first element which is sum r
.
answered Apr 19 at 1:50
xnorxnor
94.4k18193454
94.4k18193454
add a comment |
add a comment |
$begingroup$
R, 136 125 bytes
function(l,G=unlist(Map(combn,list(y<-seq(a=l)),y,c(function(x)'if'(all(diff(x)>1),l[x],-Inf)),F),F))G[which.max(Map(sum,G))]
Try it online!
-6 bytes thanks to digEmAll, who incidentally also outgolfed me.
Returns the shortest subsequence as a list
, breaking ties on lexicographically first by indices.
Brute-force generates all index subsequences, then Filter
s for those that are non-adjacent, i.e., where all(diff(x)>1)
. Then subsets [
into l
using these indices, selecting [[
the first one where the sum is the max (which.max
).
I'm pretty sure this is the first R answer I've ever written that uses sad, Filter
!Filter
is ungolfy, no wonder I've never used it...
$endgroup$
$begingroup$
130
$endgroup$
– digEmAll
yesterday
$begingroup$
@digEmAll thanks!
$endgroup$
– Giuseppe
11 hours ago
add a comment |
$begingroup$
R, 136 125 bytes
function(l,G=unlist(Map(combn,list(y<-seq(a=l)),y,c(function(x)'if'(all(diff(x)>1),l[x],-Inf)),F),F))G[which.max(Map(sum,G))]
Try it online!
-6 bytes thanks to digEmAll, who incidentally also outgolfed me.
Returns the shortest subsequence as a list
, breaking ties on lexicographically first by indices.
Brute-force generates all index subsequences, then Filter
s for those that are non-adjacent, i.e., where all(diff(x)>1)
. Then subsets [
into l
using these indices, selecting [[
the first one where the sum is the max (which.max
).
I'm pretty sure this is the first R answer I've ever written that uses sad, Filter
!Filter
is ungolfy, no wonder I've never used it...
$endgroup$
$begingroup$
130
$endgroup$
– digEmAll
yesterday
$begingroup$
@digEmAll thanks!
$endgroup$
– Giuseppe
11 hours ago
add a comment |
$begingroup$
R, 136 125 bytes
function(l,G=unlist(Map(combn,list(y<-seq(a=l)),y,c(function(x)'if'(all(diff(x)>1),l[x],-Inf)),F),F))G[which.max(Map(sum,G))]
Try it online!
-6 bytes thanks to digEmAll, who incidentally also outgolfed me.
Returns the shortest subsequence as a list
, breaking ties on lexicographically first by indices.
Brute-force generates all index subsequences, then Filter
s for those that are non-adjacent, i.e., where all(diff(x)>1)
. Then subsets [
into l
using these indices, selecting [[
the first one where the sum is the max (which.max
).
I'm pretty sure this is the first R answer I've ever written that uses sad, Filter
!Filter
is ungolfy, no wonder I've never used it...
$endgroup$
R, 136 125 bytes
function(l,G=unlist(Map(combn,list(y<-seq(a=l)),y,c(function(x)'if'(all(diff(x)>1),l[x],-Inf)),F),F))G[which.max(Map(sum,G))]
Try it online!
-6 bytes thanks to digEmAll, who incidentally also outgolfed me.
Returns the shortest subsequence as a list
, breaking ties on lexicographically first by indices.
Brute-force generates all index subsequences, then Filter
s for those that are non-adjacent, i.e., where all(diff(x)>1)
. Then subsets [
into l
using these indices, selecting [[
the first one where the sum is the max (which.max
).
I'm pretty sure this is the first R answer I've ever written that uses sad, Filter
!Filter
is ungolfy, no wonder I've never used it...
edited 11 hours ago
answered Apr 18 at 13:56
GiuseppeGiuseppe
18k31155
18k31155
$begingroup$
130
$endgroup$
– digEmAll
yesterday
$begingroup$
@digEmAll thanks!
$endgroup$
– Giuseppe
11 hours ago
add a comment |
$begingroup$
130
$endgroup$
– digEmAll
yesterday
$begingroup$
@digEmAll thanks!
$endgroup$
– Giuseppe
11 hours ago
$begingroup$
130
$endgroup$
– digEmAll
yesterday
$begingroup$
130
$endgroup$
– digEmAll
yesterday
$begingroup$
@digEmAll thanks!
$endgroup$
– Giuseppe
11 hours ago
$begingroup$
@digEmAll thanks!
$endgroup$
– Giuseppe
11 hours ago
add a comment |
$begingroup$
05AB1E, 14 bytes
Saved 1 byte thanks to Kevin Cruijssen
ā<æʒĆ¥≠W}èΣO}θ
Try it online!
or as a Test Suite
Explanation
ā< # push [0 ... len(input)-1]
æ # compute powerset
ʒ } # filter, keep lists where:
≠W # no element is 1 in the
¥ # deltas
Ć # of the list with the head appended
è # index into the input with each
ΣO} # sort by sum
θ # take the last element
$endgroup$
$begingroup$
You may not be happy, but it's still 4 bytes shorter than my initial solution. ;) And you can golf 1 more changing¤ª
toĆ
.
$endgroup$
– Kevin Cruijssen
Apr 17 at 16:40
$begingroup$
@KevinCruijssen: Oh yeah! For some reason I had convinced myself I needed a repeat element at the end. Thanks!
$endgroup$
– Emigna
Apr 17 at 17:00
add a comment |
$begingroup$
05AB1E, 14 bytes
Saved 1 byte thanks to Kevin Cruijssen
ā<æʒĆ¥≠W}èΣO}θ
Try it online!
or as a Test Suite
Explanation
ā< # push [0 ... len(input)-1]
æ # compute powerset
ʒ } # filter, keep lists where:
≠W # no element is 1 in the
¥ # deltas
Ć # of the list with the head appended
è # index into the input with each
ΣO} # sort by sum
θ # take the last element
$endgroup$
$begingroup$
You may not be happy, but it's still 4 bytes shorter than my initial solution. ;) And you can golf 1 more changing¤ª
toĆ
.
$endgroup$
– Kevin Cruijssen
Apr 17 at 16:40
$begingroup$
@KevinCruijssen: Oh yeah! For some reason I had convinced myself I needed a repeat element at the end. Thanks!
$endgroup$
– Emigna
Apr 17 at 17:00
add a comment |
$begingroup$
05AB1E, 14 bytes
Saved 1 byte thanks to Kevin Cruijssen
ā<æʒĆ¥≠W}èΣO}θ
Try it online!
or as a Test Suite
Explanation
ā< # push [0 ... len(input)-1]
æ # compute powerset
ʒ } # filter, keep lists where:
≠W # no element is 1 in the
¥ # deltas
Ć # of the list with the head appended
è # index into the input with each
ΣO} # sort by sum
θ # take the last element
$endgroup$
05AB1E, 14 bytes
Saved 1 byte thanks to Kevin Cruijssen
ā<æʒĆ¥≠W}èΣO}θ
Try it online!
or as a Test Suite
Explanation
ā< # push [0 ... len(input)-1]
æ # compute powerset
ʒ } # filter, keep lists where:
≠W # no element is 1 in the
¥ # deltas
Ć # of the list with the head appended
è # index into the input with each
ΣO} # sort by sum
θ # take the last element
edited Apr 17 at 17:00
answered Apr 17 at 14:39
EmignaEmigna
48.2k434147
48.2k434147
$begingroup$
You may not be happy, but it's still 4 bytes shorter than my initial solution. ;) And you can golf 1 more changing¤ª
toĆ
.
$endgroup$
– Kevin Cruijssen
Apr 17 at 16:40
$begingroup$
@KevinCruijssen: Oh yeah! For some reason I had convinced myself I needed a repeat element at the end. Thanks!
$endgroup$
– Emigna
Apr 17 at 17:00
add a comment |
$begingroup$
You may not be happy, but it's still 4 bytes shorter than my initial solution. ;) And you can golf 1 more changing¤ª
toĆ
.
$endgroup$
– Kevin Cruijssen
Apr 17 at 16:40
$begingroup$
@KevinCruijssen: Oh yeah! For some reason I had convinced myself I needed a repeat element at the end. Thanks!
$endgroup$
– Emigna
Apr 17 at 17:00
$begingroup$
You may not be happy, but it's still 4 bytes shorter than my initial solution. ;) And you can golf 1 more changing
¤ª
to Ć
.$endgroup$
– Kevin Cruijssen
Apr 17 at 16:40
$begingroup$
You may not be happy, but it's still 4 bytes shorter than my initial solution. ;) And you can golf 1 more changing
¤ª
to Ć
.$endgroup$
– Kevin Cruijssen
Apr 17 at 16:40
$begingroup$
@KevinCruijssen: Oh yeah! For some reason I had convinced myself I needed a repeat element at the end. Thanks!
$endgroup$
– Emigna
Apr 17 at 17:00
$begingroup$
@KevinCruijssen: Oh yeah! For some reason I had convinced myself I needed a repeat element at the end. Thanks!
$endgroup$
– Emigna
Apr 17 at 17:00
add a comment |
$begingroup$
Brachylog (v2), 14 bytes
~ba~c∋₁ᵐᶠ+ᵒt
Try it online!
Function submission; input from the left, output from the right, as usual. Very slow; a five-element list is probably the maximum for testing on TIO.
~ba~c∋₁ᵐᶠ+ᵒt
~b Prepend an arbitrary element to the input
a Take a prefix or suffix of the resulting list
~c Ordered partition into contiguous sublists
∋₁ Take the second element
ᵐ of each sublist
ᶠ Find all possible ways to do this
+ᵒ Sort by sum
t Take the greatest
The results we get from prefixes aren't incorrect, but also aren't interesting; all possible results are generated via taking a suffix (which is possibly the list itself, but cannot be empty), but "suffix" is more verbose in Brachylog than "prefix or suffix", so I went with the version that's terser (and less efficient but still correct). The basic idea is that for each element we want in the output list, the partition into contiguous sublists needs to place that element and the element before into the same sublist (because the element is the second element of the sublist), so two consecutive elements can't appear in the result. On the other hand, it's fairly clear that any list without two consecutive elements can appear in the result. So once we have all possible candidate lists, we can just take the sums of all of them and see which one is largest.
$endgroup$
add a comment |
$begingroup$
Brachylog (v2), 14 bytes
~ba~c∋₁ᵐᶠ+ᵒt
Try it online!
Function submission; input from the left, output from the right, as usual. Very slow; a five-element list is probably the maximum for testing on TIO.
~ba~c∋₁ᵐᶠ+ᵒt
~b Prepend an arbitrary element to the input
a Take a prefix or suffix of the resulting list
~c Ordered partition into contiguous sublists
∋₁ Take the second element
ᵐ of each sublist
ᶠ Find all possible ways to do this
+ᵒ Sort by sum
t Take the greatest
The results we get from prefixes aren't incorrect, but also aren't interesting; all possible results are generated via taking a suffix (which is possibly the list itself, but cannot be empty), but "suffix" is more verbose in Brachylog than "prefix or suffix", so I went with the version that's terser (and less efficient but still correct). The basic idea is that for each element we want in the output list, the partition into contiguous sublists needs to place that element and the element before into the same sublist (because the element is the second element of the sublist), so two consecutive elements can't appear in the result. On the other hand, it's fairly clear that any list without two consecutive elements can appear in the result. So once we have all possible candidate lists, we can just take the sums of all of them and see which one is largest.
$endgroup$
add a comment |
$begingroup$
Brachylog (v2), 14 bytes
~ba~c∋₁ᵐᶠ+ᵒt
Try it online!
Function submission; input from the left, output from the right, as usual. Very slow; a five-element list is probably the maximum for testing on TIO.
~ba~c∋₁ᵐᶠ+ᵒt
~b Prepend an arbitrary element to the input
a Take a prefix or suffix of the resulting list
~c Ordered partition into contiguous sublists
∋₁ Take the second element
ᵐ of each sublist
ᶠ Find all possible ways to do this
+ᵒ Sort by sum
t Take the greatest
The results we get from prefixes aren't incorrect, but also aren't interesting; all possible results are generated via taking a suffix (which is possibly the list itself, but cannot be empty), but "suffix" is more verbose in Brachylog than "prefix or suffix", so I went with the version that's terser (and less efficient but still correct). The basic idea is that for each element we want in the output list, the partition into contiguous sublists needs to place that element and the element before into the same sublist (because the element is the second element of the sublist), so two consecutive elements can't appear in the result. On the other hand, it's fairly clear that any list without two consecutive elements can appear in the result. So once we have all possible candidate lists, we can just take the sums of all of them and see which one is largest.
$endgroup$
Brachylog (v2), 14 bytes
~ba~c∋₁ᵐᶠ+ᵒt
Try it online!
Function submission; input from the left, output from the right, as usual. Very slow; a five-element list is probably the maximum for testing on TIO.
~ba~c∋₁ᵐᶠ+ᵒt
~b Prepend an arbitrary element to the input
a Take a prefix or suffix of the resulting list
~c Ordered partition into contiguous sublists
∋₁ Take the second element
ᵐ of each sublist
ᶠ Find all possible ways to do this
+ᵒ Sort by sum
t Take the greatest
The results we get from prefixes aren't incorrect, but also aren't interesting; all possible results are generated via taking a suffix (which is possibly the list itself, but cannot be empty), but "suffix" is more verbose in Brachylog than "prefix or suffix", so I went with the version that's terser (and less efficient but still correct). The basic idea is that for each element we want in the output list, the partition into contiguous sublists needs to place that element and the element before into the same sublist (because the element is the second element of the sublist), so two consecutive elements can't appear in the result. On the other hand, it's fairly clear that any list without two consecutive elements can appear in the result. So once we have all possible candidate lists, we can just take the sums of all of them and see which one is largest.
answered Apr 17 at 17:54
community wiki
ais523
add a comment |
add a comment |
$begingroup$
Husk, 11 bytes
►Σ†!¹mü≈tṖŀ
Try it online!
Explanation
►Σ†!¹mü≈tṖŀ Implicit input, say L=[4,5,3,4].
ŀ Indices: [1,2,3,4]
Ṗ Powerset: [[],[1],[2],[1,2],..,[1,2,3,4]]
t Tail (remove the empty list): [[1],[2],[1,2],..,[1,2,3,4]]
m For each,
ü de-duplicate by
≈ differing by at most 1.
For example, [1,2,4] becomes [1,4].
† Deep map
!¹ indexing into L: [[4],[5],[4],..,[5,4],[4,3]]
► Maximum by
Σ sum: [5,4]
$endgroup$
add a comment |
$begingroup$
Husk, 11 bytes
►Σ†!¹mü≈tṖŀ
Try it online!
Explanation
►Σ†!¹mü≈tṖŀ Implicit input, say L=[4,5,3,4].
ŀ Indices: [1,2,3,4]
Ṗ Powerset: [[],[1],[2],[1,2],..,[1,2,3,4]]
t Tail (remove the empty list): [[1],[2],[1,2],..,[1,2,3,4]]
m For each,
ü de-duplicate by
≈ differing by at most 1.
For example, [1,2,4] becomes [1,4].
† Deep map
!¹ indexing into L: [[4],[5],[4],..,[5,4],[4,3]]
► Maximum by
Σ sum: [5,4]
$endgroup$
add a comment |
$begingroup$
Husk, 11 bytes
►Σ†!¹mü≈tṖŀ
Try it online!
Explanation
►Σ†!¹mü≈tṖŀ Implicit input, say L=[4,5,3,4].
ŀ Indices: [1,2,3,4]
Ṗ Powerset: [[],[1],[2],[1,2],..,[1,2,3,4]]
t Tail (remove the empty list): [[1],[2],[1,2],..,[1,2,3,4]]
m For each,
ü de-duplicate by
≈ differing by at most 1.
For example, [1,2,4] becomes [1,4].
† Deep map
!¹ indexing into L: [[4],[5],[4],..,[5,4],[4,3]]
► Maximum by
Σ sum: [5,4]
$endgroup$
Husk, 11 bytes
►Σ†!¹mü≈tṖŀ
Try it online!
Explanation
►Σ†!¹mü≈tṖŀ Implicit input, say L=[4,5,3,4].
ŀ Indices: [1,2,3,4]
Ṗ Powerset: [[],[1],[2],[1,2],..,[1,2,3,4]]
t Tail (remove the empty list): [[1],[2],[1,2],..,[1,2,3,4]]
m For each,
ü de-duplicate by
≈ differing by at most 1.
For example, [1,2,4] becomes [1,4].
† Deep map
!¹ indexing into L: [[4],[5],[4],..,[5,4],[4,3]]
► Maximum by
Σ sum: [5,4]
edited Apr 17 at 18:06
answered Apr 17 at 17:51
ZgarbZgarb
26.9k462231
26.9k462231
add a comment |
add a comment |
$begingroup$
Jelly, 16 14 bytes
JŒPḊf’$ÐḟịµSÞṪ
Try it online!
Thanks to @EriktheOutgolfer for saving 2 bytes!
$endgroup$
$begingroup$
14 bytes.
$endgroup$
– Erik the Outgolfer
Apr 17 at 18:17
add a comment |
$begingroup$
Jelly, 16 14 bytes
JŒPḊf’$ÐḟịµSÞṪ
Try it online!
Thanks to @EriktheOutgolfer for saving 2 bytes!
$endgroup$
$begingroup$
14 bytes.
$endgroup$
– Erik the Outgolfer
Apr 17 at 18:17
add a comment |
$begingroup$
Jelly, 16 14 bytes
JŒPḊf’$ÐḟịµSÞṪ
Try it online!
Thanks to @EriktheOutgolfer for saving 2 bytes!
$endgroup$
Jelly, 16 14 bytes
JŒPḊf’$ÐḟịµSÞṪ
Try it online!
Thanks to @EriktheOutgolfer for saving 2 bytes!
edited Apr 17 at 18:25
answered Apr 17 at 14:15
Nick KennedyNick Kennedy
1,89149
1,89149
$begingroup$
14 bytes.
$endgroup$
– Erik the Outgolfer
Apr 17 at 18:17
add a comment |
$begingroup$
14 bytes.
$endgroup$
– Erik the Outgolfer
Apr 17 at 18:17
$begingroup$
14 bytes.
$endgroup$
– Erik the Outgolfer
Apr 17 at 18:17
$begingroup$
14 bytes.
$endgroup$
– Erik the Outgolfer
Apr 17 at 18:17
add a comment |
$begingroup$
JavaScript (ES6), 138 132 130 129 126 bytes
Outputs key-value pairs.
a=>a.reduce((a,x,i)=>[...a,...a.map(y=>[[x,i],...y])],[[]]).map(m=a=>a.some(s=p=([v,i])=>p-(s=~~s+v,p=i)<2)|s<m||(r=a,m=s))&&r
Try it online!
Step 1
We first compute the powerset of the input with $[value, index]$ pairs.
a.reduce((a, x, i) => // for each value x at position i:
[ // update a[] to a new array consisting of:
...a, // all previous entries
...a.map(y => // for each value y in a[]:
[[x, i], ...y] // append [x, i], followed by all original entries
) // end of map()
], // end of new array
[[]] // start with a = [[]]
) // end of reduce()
Step 2
We then look for the maximum sum $m$ among these sets, discarding sets with at least two adjacent elements. The best set is stored in $r$.
.map(m = // initialize m to a non-numeric value
a => // for each entry a[] in the powerset:
a.some(s = p = // initialize s and p to non numeric values
([v, i]) => // for each value v and each index i in a[]:
p - ( // compute p - i
s = ~~s + v, // add v to s
p = i // update p to i
) < 2 // if p - i is less than 2, yield true
) | // end of some()
s < m || // unless some() was truthy or s is less than m,
(r = a, m = s) // save a[] in r[] and update m to s
) && r // end of map(); return r[]
$endgroup$
add a comment |
$begingroup$
JavaScript (ES6), 138 132 130 129 126 bytes
Outputs key-value pairs.
a=>a.reduce((a,x,i)=>[...a,...a.map(y=>[[x,i],...y])],[[]]).map(m=a=>a.some(s=p=([v,i])=>p-(s=~~s+v,p=i)<2)|s<m||(r=a,m=s))&&r
Try it online!
Step 1
We first compute the powerset of the input with $[value, index]$ pairs.
a.reduce((a, x, i) => // for each value x at position i:
[ // update a[] to a new array consisting of:
...a, // all previous entries
...a.map(y => // for each value y in a[]:
[[x, i], ...y] // append [x, i], followed by all original entries
) // end of map()
], // end of new array
[[]] // start with a = [[]]
) // end of reduce()
Step 2
We then look for the maximum sum $m$ among these sets, discarding sets with at least two adjacent elements. The best set is stored in $r$.
.map(m = // initialize m to a non-numeric value
a => // for each entry a[] in the powerset:
a.some(s = p = // initialize s and p to non numeric values
([v, i]) => // for each value v and each index i in a[]:
p - ( // compute p - i
s = ~~s + v, // add v to s
p = i // update p to i
) < 2 // if p - i is less than 2, yield true
) | // end of some()
s < m || // unless some() was truthy or s is less than m,
(r = a, m = s) // save a[] in r[] and update m to s
) && r // end of map(); return r[]
$endgroup$
add a comment |
$begingroup$
JavaScript (ES6), 138 132 130 129 126 bytes
Outputs key-value pairs.
a=>a.reduce((a,x,i)=>[...a,...a.map(y=>[[x,i],...y])],[[]]).map(m=a=>a.some(s=p=([v,i])=>p-(s=~~s+v,p=i)<2)|s<m||(r=a,m=s))&&r
Try it online!
Step 1
We first compute the powerset of the input with $[value, index]$ pairs.
a.reduce((a, x, i) => // for each value x at position i:
[ // update a[] to a new array consisting of:
...a, // all previous entries
...a.map(y => // for each value y in a[]:
[[x, i], ...y] // append [x, i], followed by all original entries
) // end of map()
], // end of new array
[[]] // start with a = [[]]
) // end of reduce()
Step 2
We then look for the maximum sum $m$ among these sets, discarding sets with at least two adjacent elements. The best set is stored in $r$.
.map(m = // initialize m to a non-numeric value
a => // for each entry a[] in the powerset:
a.some(s = p = // initialize s and p to non numeric values
([v, i]) => // for each value v and each index i in a[]:
p - ( // compute p - i
s = ~~s + v, // add v to s
p = i // update p to i
) < 2 // if p - i is less than 2, yield true
) | // end of some()
s < m || // unless some() was truthy or s is less than m,
(r = a, m = s) // save a[] in r[] and update m to s
) && r // end of map(); return r[]
$endgroup$
JavaScript (ES6), 138 132 130 129 126 bytes
Outputs key-value pairs.
a=>a.reduce((a,x,i)=>[...a,...a.map(y=>[[x,i],...y])],[[]]).map(m=a=>a.some(s=p=([v,i])=>p-(s=~~s+v,p=i)<2)|s<m||(r=a,m=s))&&r
Try it online!
Step 1
We first compute the powerset of the input with $[value, index]$ pairs.
a.reduce((a, x, i) => // for each value x at position i:
[ // update a[] to a new array consisting of:
...a, // all previous entries
...a.map(y => // for each value y in a[]:
[[x, i], ...y] // append [x, i], followed by all original entries
) // end of map()
], // end of new array
[[]] // start with a = [[]]
) // end of reduce()
Step 2
We then look for the maximum sum $m$ among these sets, discarding sets with at least two adjacent elements. The best set is stored in $r$.
.map(m = // initialize m to a non-numeric value
a => // for each entry a[] in the powerset:
a.some(s = p = // initialize s and p to non numeric values
([v, i]) => // for each value v and each index i in a[]:
p - ( // compute p - i
s = ~~s + v, // add v to s
p = i // update p to i
) < 2 // if p - i is less than 2, yield true
) | // end of some()
s < m || // unless some() was truthy or s is less than m,
(r = a, m = s) // save a[] in r[] and update m to s
) && r // end of map(); return r[]
edited Apr 18 at 2:32
answered Apr 17 at 14:56
ArnauldArnauld
81.8k798337
81.8k798337
add a comment |
add a comment |
$begingroup$
T-SQL, 122 119 bytes
Input is a table variable.
This query picks all elements from the table variable, combining these with all non-adjacent elements with higher position values and show the text generated for the highest sum of these values.
WITH C(y,j,v)as(SELECT*,x*1FROM @
UNION ALL
SELECT y+','+x,i,v+x
FROM @ JOIN C ON j+1<i)SELECT
TOP 1y FROM C ORDER BY-v
Try it online ungolfed
$endgroup$
add a comment |
$begingroup$
T-SQL, 122 119 bytes
Input is a table variable.
This query picks all elements from the table variable, combining these with all non-adjacent elements with higher position values and show the text generated for the highest sum of these values.
WITH C(y,j,v)as(SELECT*,x*1FROM @
UNION ALL
SELECT y+','+x,i,v+x
FROM @ JOIN C ON j+1<i)SELECT
TOP 1y FROM C ORDER BY-v
Try it online ungolfed
$endgroup$
add a comment |
$begingroup$
T-SQL, 122 119 bytes
Input is a table variable.
This query picks all elements from the table variable, combining these with all non-adjacent elements with higher position values and show the text generated for the highest sum of these values.
WITH C(y,j,v)as(SELECT*,x*1FROM @
UNION ALL
SELECT y+','+x,i,v+x
FROM @ JOIN C ON j+1<i)SELECT
TOP 1y FROM C ORDER BY-v
Try it online ungolfed
$endgroup$
T-SQL, 122 119 bytes
Input is a table variable.
This query picks all elements from the table variable, combining these with all non-adjacent elements with higher position values and show the text generated for the highest sum of these values.
WITH C(y,j,v)as(SELECT*,x*1FROM @
UNION ALL
SELECT y+','+x,i,v+x
FROM @ JOIN C ON j+1<i)SELECT
TOP 1y FROM C ORDER BY-v
Try it online ungolfed
edited Apr 18 at 13:21
answered Apr 18 at 3:50
t-clausen.dkt-clausen.dk
2,134414
2,134414
add a comment |
add a comment |
$begingroup$
Haskell, 81 80 bytes
snd.maximum.map((,)=<<sum).tail.f
f(a:b:c)=f(b:c)++map(a:)(f c)
f a=[]:map(:[])a
Try it online!
f
builds all valid subsequences by either skipping the next element (f(b:c)
) or using it and skipping the next (map(a:)(f c)
) and recursively work on the rest. For the result, build all subsequences (f
), drop the empty subsequence (which occurs first in the list: tail
), make pairs (<sum>,<subsequence>)
(map((,)=<<sum)
), find the maximum (pairs are compared in lexicographical order) -> maximum
) and drop the sum (snd
).
Edit: -1 byte thanks to @Lynn.
$endgroup$
1
$begingroup$
map(:[])a
is a byte shorter than(pure<$>a)
^^
$endgroup$
– Lynn
Apr 18 at 18:38
add a comment |
$begingroup$
Haskell, 81 80 bytes
snd.maximum.map((,)=<<sum).tail.f
f(a:b:c)=f(b:c)++map(a:)(f c)
f a=[]:map(:[])a
Try it online!
f
builds all valid subsequences by either skipping the next element (f(b:c)
) or using it and skipping the next (map(a:)(f c)
) and recursively work on the rest. For the result, build all subsequences (f
), drop the empty subsequence (which occurs first in the list: tail
), make pairs (<sum>,<subsequence>)
(map((,)=<<sum)
), find the maximum (pairs are compared in lexicographical order) -> maximum
) and drop the sum (snd
).
Edit: -1 byte thanks to @Lynn.
$endgroup$
1
$begingroup$
map(:[])a
is a byte shorter than(pure<$>a)
^^
$endgroup$
– Lynn
Apr 18 at 18:38
add a comment |
$begingroup$
Haskell, 81 80 bytes
snd.maximum.map((,)=<<sum).tail.f
f(a:b:c)=f(b:c)++map(a:)(f c)
f a=[]:map(:[])a
Try it online!
f
builds all valid subsequences by either skipping the next element (f(b:c)
) or using it and skipping the next (map(a:)(f c)
) and recursively work on the rest. For the result, build all subsequences (f
), drop the empty subsequence (which occurs first in the list: tail
), make pairs (<sum>,<subsequence>)
(map((,)=<<sum)
), find the maximum (pairs are compared in lexicographical order) -> maximum
) and drop the sum (snd
).
Edit: -1 byte thanks to @Lynn.
$endgroup$
Haskell, 81 80 bytes
snd.maximum.map((,)=<<sum).tail.f
f(a:b:c)=f(b:c)++map(a:)(f c)
f a=[]:map(:[])a
Try it online!
f
builds all valid subsequences by either skipping the next element (f(b:c)
) or using it and skipping the next (map(a:)(f c)
) and recursively work on the rest. For the result, build all subsequences (f
), drop the empty subsequence (which occurs first in the list: tail
), make pairs (<sum>,<subsequence>)
(map((,)=<<sum)
), find the maximum (pairs are compared in lexicographical order) -> maximum
) and drop the sum (snd
).
Edit: -1 byte thanks to @Lynn.
edited Apr 18 at 18:51
answered Apr 18 at 14:15
niminimi
32.9k32490
32.9k32490
1
$begingroup$
map(:[])a
is a byte shorter than(pure<$>a)
^^
$endgroup$
– Lynn
Apr 18 at 18:38
add a comment |
1
$begingroup$
map(:[])a
is a byte shorter than(pure<$>a)
^^
$endgroup$
– Lynn
Apr 18 at 18:38
1
1
$begingroup$
map(:[])a
is a byte shorter than (pure<$>a)
^^$endgroup$
– Lynn
Apr 18 at 18:38
$begingroup$
map(:[])a
is a byte shorter than (pure<$>a)
^^$endgroup$
– Lynn
Apr 18 at 18:38
add a comment |
$begingroup$
Wolfram Language (Mathematica), 144 bytes
If[Max[a=#]>(d=Max[m=Tr/@(g=a[[#]]&/@Select[Subsets[Range[x=Length@#],2,x]&@#,FreeQ[Differences@#,1]&]&@a)]),Max@a,g[[#]]&@@@Position[m,d]]&
Try it online!
$endgroup$
add a comment |
$begingroup$
Wolfram Language (Mathematica), 144 bytes
If[Max[a=#]>(d=Max[m=Tr/@(g=a[[#]]&/@Select[Subsets[Range[x=Length@#],2,x]&@#,FreeQ[Differences@#,1]&]&@a)]),Max@a,g[[#]]&@@@Position[m,d]]&
Try it online!
$endgroup$
add a comment |
$begingroup$
Wolfram Language (Mathematica), 144 bytes
If[Max[a=#]>(d=Max[m=Tr/@(g=a[[#]]&/@Select[Subsets[Range[x=Length@#],2,x]&@#,FreeQ[Differences@#,1]&]&@a)]),Max@a,g[[#]]&@@@Position[m,d]]&
Try it online!
$endgroup$
Wolfram Language (Mathematica), 144 bytes
If[Max[a=#]>(d=Max[m=Tr/@(g=a[[#]]&/@Select[Subsets[Range[x=Length@#],2,x]&@#,FreeQ[Differences@#,1]&]&@a)]),Max@a,g[[#]]&@@@Position[m,d]]&
Try it online!
answered Apr 17 at 14:33
J42161217J42161217
14.3k21354
14.3k21354
add a comment |
add a comment |
$begingroup$
Pyth, 19 bytes
esDm@LQdtf!q#1.+TyU
Try it online here, or verify all the test cases at once here.
esDm@LQdtf!q#1.+TyUQ Implicit: Q=eval(input())
Trailing Q inferred
UQ Generate range [0-len(Q))
y Take the powerset of the above
f Filter keep elements of the above, as T, using:
.+T Take differences of consecutive elements of T
q#1 Keep those differences equal to 1
! Logical NOT - empty lists evaluate to true, populated ones to false
Result of the filter is those sets without consecutive numbers
t Drop the first element (empty set)
m Map the remaining sets, as d, using:
L d For each element of d...
@ Q ... get the element in Q with that index
sD Order the sets by their sum
e Take the last element, implicit print
$endgroup$
add a comment |
$begingroup$
Pyth, 19 bytes
esDm@LQdtf!q#1.+TyU
Try it online here, or verify all the test cases at once here.
esDm@LQdtf!q#1.+TyUQ Implicit: Q=eval(input())
Trailing Q inferred
UQ Generate range [0-len(Q))
y Take the powerset of the above
f Filter keep elements of the above, as T, using:
.+T Take differences of consecutive elements of T
q#1 Keep those differences equal to 1
! Logical NOT - empty lists evaluate to true, populated ones to false
Result of the filter is those sets without consecutive numbers
t Drop the first element (empty set)
m Map the remaining sets, as d, using:
L d For each element of d...
@ Q ... get the element in Q with that index
sD Order the sets by their sum
e Take the last element, implicit print
$endgroup$
add a comment |
$begingroup$
Pyth, 19 bytes
esDm@LQdtf!q#1.+TyU
Try it online here, or verify all the test cases at once here.
esDm@LQdtf!q#1.+TyUQ Implicit: Q=eval(input())
Trailing Q inferred
UQ Generate range [0-len(Q))
y Take the powerset of the above
f Filter keep elements of the above, as T, using:
.+T Take differences of consecutive elements of T
q#1 Keep those differences equal to 1
! Logical NOT - empty lists evaluate to true, populated ones to false
Result of the filter is those sets without consecutive numbers
t Drop the first element (empty set)
m Map the remaining sets, as d, using:
L d For each element of d...
@ Q ... get the element in Q with that index
sD Order the sets by their sum
e Take the last element, implicit print
$endgroup$
Pyth, 19 bytes
esDm@LQdtf!q#1.+TyU
Try it online here, or verify all the test cases at once here.
esDm@LQdtf!q#1.+TyUQ Implicit: Q=eval(input())
Trailing Q inferred
UQ Generate range [0-len(Q))
y Take the powerset of the above
f Filter keep elements of the above, as T, using:
.+T Take differences of consecutive elements of T
q#1 Keep those differences equal to 1
! Logical NOT - empty lists evaluate to true, populated ones to false
Result of the filter is those sets without consecutive numbers
t Drop the first element (empty set)
m Map the remaining sets, as d, using:
L d For each element of d...
@ Q ... get the element in Q with that index
sD Order the sets by their sum
e Take the last element, implicit print
edited Apr 17 at 15:06
answered Apr 17 at 13:40
SokSok
4,242925
4,242925
add a comment |
add a comment |
$begingroup$
Gaia, 24 bytes
e:w;ċz⟨ọ1>¦ẏ⟩⁇‼⁇E‡ev2%Σ⌠
Try it online!
Ugh, E‡
does some weird stuff...according to the documentation, it should do something like "given length i
set of lists X
and length j
set of indices Y
, return X[i][Y[j]]
", but instead returns [X[i][Y[j]] X[i][Y[-j]]
where negative indexing represents the complement, so we have to do ev2%
to extract only the ones we want.
e | eval as a list l
: | dup
w | wrap as a list
; | push l again
ċ | push [1..len(l)]
z | push all subsets of [1..len(l)] -- index powerset.
⟨ ⟩⁇ | filter this for:
ọ | deltas
1>¦ | are greater than 1
ẏ | all (all deltas greater than 1)
‼⁇ | filter for non-empty lists
E‡ | table extract elements. Given l and index set i, this pushes
| [l[i] l[setdiff(1..l,i)]] for some reason
ev2% | get the l[i] only by unlisting, reversing, and taking every other element
Σ⌠ | Get the one with the maximum sum
$endgroup$
$begingroup$
Out of curiosity, why does the output have two trailing]]
instead of one?
$endgroup$
– Kevin Cruijssen
Apr 18 at 19:14
$begingroup$
@KevinCruijssen Just another fun quirk of the interpreter; all lists are printed out like that, so[[1] [2]]
gets printed[[1]] [2]]]]
which makes it super hard to read/debug list output.
$endgroup$
– Giuseppe
Apr 18 at 19:27
$begingroup$
I think it's because of the expressionre.sub(" ?$","]",result)
in the interpreter which should instead bere.sub(" +$","]",result)
but my python is super bad.
$endgroup$
– Giuseppe
Apr 18 at 19:37
add a comment |
$begingroup$
Gaia, 24 bytes
e:w;ċz⟨ọ1>¦ẏ⟩⁇‼⁇E‡ev2%Σ⌠
Try it online!
Ugh, E‡
does some weird stuff...according to the documentation, it should do something like "given length i
set of lists X
and length j
set of indices Y
, return X[i][Y[j]]
", but instead returns [X[i][Y[j]] X[i][Y[-j]]
where negative indexing represents the complement, so we have to do ev2%
to extract only the ones we want.
e | eval as a list l
: | dup
w | wrap as a list
; | push l again
ċ | push [1..len(l)]
z | push all subsets of [1..len(l)] -- index powerset.
⟨ ⟩⁇ | filter this for:
ọ | deltas
1>¦ | are greater than 1
ẏ | all (all deltas greater than 1)
‼⁇ | filter for non-empty lists
E‡ | table extract elements. Given l and index set i, this pushes
| [l[i] l[setdiff(1..l,i)]] for some reason
ev2% | get the l[i] only by unlisting, reversing, and taking every other element
Σ⌠ | Get the one with the maximum sum
$endgroup$
$begingroup$
Out of curiosity, why does the output have two trailing]]
instead of one?
$endgroup$
– Kevin Cruijssen
Apr 18 at 19:14
$begingroup$
@KevinCruijssen Just another fun quirk of the interpreter; all lists are printed out like that, so[[1] [2]]
gets printed[[1]] [2]]]]
which makes it super hard to read/debug list output.
$endgroup$
– Giuseppe
Apr 18 at 19:27
$begingroup$
I think it's because of the expressionre.sub(" ?$","]",result)
in the interpreter which should instead bere.sub(" +$","]",result)
but my python is super bad.
$endgroup$
– Giuseppe
Apr 18 at 19:37
add a comment |
$begingroup$
Gaia, 24 bytes
e:w;ċz⟨ọ1>¦ẏ⟩⁇‼⁇E‡ev2%Σ⌠
Try it online!
Ugh, E‡
does some weird stuff...according to the documentation, it should do something like "given length i
set of lists X
and length j
set of indices Y
, return X[i][Y[j]]
", but instead returns [X[i][Y[j]] X[i][Y[-j]]
where negative indexing represents the complement, so we have to do ev2%
to extract only the ones we want.
e | eval as a list l
: | dup
w | wrap as a list
; | push l again
ċ | push [1..len(l)]
z | push all subsets of [1..len(l)] -- index powerset.
⟨ ⟩⁇ | filter this for:
ọ | deltas
1>¦ | are greater than 1
ẏ | all (all deltas greater than 1)
‼⁇ | filter for non-empty lists
E‡ | table extract elements. Given l and index set i, this pushes
| [l[i] l[setdiff(1..l,i)]] for some reason
ev2% | get the l[i] only by unlisting, reversing, and taking every other element
Σ⌠ | Get the one with the maximum sum
$endgroup$
Gaia, 24 bytes
e:w;ċz⟨ọ1>¦ẏ⟩⁇‼⁇E‡ev2%Σ⌠
Try it online!
Ugh, E‡
does some weird stuff...according to the documentation, it should do something like "given length i
set of lists X
and length j
set of indices Y
, return X[i][Y[j]]
", but instead returns [X[i][Y[j]] X[i][Y[-j]]
where negative indexing represents the complement, so we have to do ev2%
to extract only the ones we want.
e | eval as a list l
: | dup
w | wrap as a list
; | push l again
ċ | push [1..len(l)]
z | push all subsets of [1..len(l)] -- index powerset.
⟨ ⟩⁇ | filter this for:
ọ | deltas
1>¦ | are greater than 1
ẏ | all (all deltas greater than 1)
‼⁇ | filter for non-empty lists
E‡ | table extract elements. Given l and index set i, this pushes
| [l[i] l[setdiff(1..l,i)]] for some reason
ev2% | get the l[i] only by unlisting, reversing, and taking every other element
Σ⌠ | Get the one with the maximum sum
answered Apr 18 at 18:59
GiuseppeGiuseppe
18k31155
18k31155
$begingroup$
Out of curiosity, why does the output have two trailing]]
instead of one?
$endgroup$
– Kevin Cruijssen
Apr 18 at 19:14
$begingroup$
@KevinCruijssen Just another fun quirk of the interpreter; all lists are printed out like that, so[[1] [2]]
gets printed[[1]] [2]]]]
which makes it super hard to read/debug list output.
$endgroup$
– Giuseppe
Apr 18 at 19:27
$begingroup$
I think it's because of the expressionre.sub(" ?$","]",result)
in the interpreter which should instead bere.sub(" +$","]",result)
but my python is super bad.
$endgroup$
– Giuseppe
Apr 18 at 19:37
add a comment |
$begingroup$
Out of curiosity, why does the output have two trailing]]
instead of one?
$endgroup$
– Kevin Cruijssen
Apr 18 at 19:14
$begingroup$
@KevinCruijssen Just another fun quirk of the interpreter; all lists are printed out like that, so[[1] [2]]
gets printed[[1]] [2]]]]
which makes it super hard to read/debug list output.
$endgroup$
– Giuseppe
Apr 18 at 19:27
$begingroup$
I think it's because of the expressionre.sub(" ?$","]",result)
in the interpreter which should instead bere.sub(" +$","]",result)
but my python is super bad.
$endgroup$
– Giuseppe
Apr 18 at 19:37
$begingroup$
Out of curiosity, why does the output have two trailing
]]
instead of one?$endgroup$
– Kevin Cruijssen
Apr 18 at 19:14
$begingroup$
Out of curiosity, why does the output have two trailing
]]
instead of one?$endgroup$
– Kevin Cruijssen
Apr 18 at 19:14
$begingroup$
@KevinCruijssen Just another fun quirk of the interpreter; all lists are printed out like that, so
[[1] [2]]
gets printed [[1]] [2]]]]
which makes it super hard to read/debug list output.$endgroup$
– Giuseppe
Apr 18 at 19:27
$begingroup$
@KevinCruijssen Just another fun quirk of the interpreter; all lists are printed out like that, so
[[1] [2]]
gets printed [[1]] [2]]]]
which makes it super hard to read/debug list output.$endgroup$
– Giuseppe
Apr 18 at 19:27
$begingroup$
I think it's because of the expression
re.sub(" ?$","]",result)
in the interpreter which should instead be re.sub(" +$","]",result)
but my python is super bad.$endgroup$
– Giuseppe
Apr 18 at 19:37
$begingroup$
I think it's because of the expression
re.sub(" ?$","]",result)
in the interpreter which should instead be re.sub(" +$","]",result)
but my python is super bad.$endgroup$
– Giuseppe
Apr 18 at 19:37
add a comment |
$begingroup$
J, 54 bytes
[:(>@:@/:+/&>)]<@#~"1[:(#~0=1 1+/@E."1])[:#:@.@i.2^#
Try it online!
$endgroup$
add a comment |
$begingroup$
J, 54 bytes
[:(>@:@/:+/&>)]<@#~"1[:(#~0=1 1+/@E."1])[:#:@.@i.2^#
Try it online!
$endgroup$
add a comment |
$begingroup$
J, 54 bytes
[:(>@:@/:+/&>)]<@#~"1[:(#~0=1 1+/@E."1])[:#:@.@i.2^#
Try it online!
$endgroup$
J, 54 bytes
[:(>@:@/:+/&>)]<@#~"1[:(#~0=1 1+/@E."1])[:#:@.@i.2^#
Try it online!
answered Apr 19 at 4:52
JonahJonah
2,9281019
2,9281019
add a comment |
add a comment |
$begingroup$
R, 108 107 bytes
function(v,M=-Inf)for(j in J<-seq(a=v))for(i in combn(J,j,,F))if(all(diff(i)>1)&sum(v[i])>sum(M))M=v[i]
M
Try it online!
-1 thanks to @Giuseppe
$endgroup$
add a comment |
$begingroup$
R, 108 107 bytes
function(v,M=-Inf)for(j in J<-seq(a=v))for(i in combn(J,j,,F))if(all(diff(i)>1)&sum(v[i])>sum(M))M=v[i]
M
Try it online!
-1 thanks to @Giuseppe
$endgroup$
add a comment |
$begingroup$
R, 108 107 bytes
function(v,M=-Inf)for(j in J<-seq(a=v))for(i in combn(J,j,,F))if(all(diff(i)>1)&sum(v[i])>sum(M))M=v[i]
M
Try it online!
-1 thanks to @Giuseppe
$endgroup$
R, 108 107 bytes
function(v,M=-Inf)for(j in J<-seq(a=v))for(i in combn(J,j,,F))if(all(diff(i)>1)&sum(v[i])>sum(M))M=v[i]
M
Try it online!
-1 thanks to @Giuseppe
edited 10 hours ago
answered yesterday
digEmAlldigEmAll
3,624515
3,624515
add a comment |
add a comment |
$begingroup$
Haskell, 300 168 bytes
import Data.List
h[]=1>2
h(x:y)=fst$foldl(a c->((fst a)&&(c-snd a>1),c))(1<2,x)y
z=snd.last.sortOn fst.map((,)=<<sum.snd).filter(h.fst).map unzip.subsequences.zip[0..]
Try it online!
-132 bytes thanks to all the feedback from @nimi :)
Original
Ungolfed (original)
import Data.List
import Data.Function
f :: [Int] -> [(Int, Int)] -- attach indices for later use
f [] = []
f xs = zip xs [0..length xs]
g :: [[(Int, Int)]] -> [([Int], [Int])] -- rearrange into list of tuples
g [] = []
g (x:xs) = (map fst x, map snd x) : g xs
h :: [Int] -> Bool -- predicate that checks if the indices are at least 2 apart from each other
h [] = False
h (x:xs) = fst $ foldl (acc curr -> ((fst acc) && (curr - snd acc > 1), curr)) (True, x) xs
j :: [([Int], [Int])] -> [([Int], [Int])] -- remove sets that don't satisfy the condition
j xs = filter ((elements, indices) -> h indices) xs
k :: [([Int], [Int])] -> [(Int, ([Int], [Int]))] -- calculate some of elements
k xs = map ((elements, indices) -> (foldl1 (+) elements, (elements, indices))) xs
l :: [(Int, ([Int], [Int]))] -> ([Int], [Int]) -- grab max
l xs = snd $ last $ sortBy (compare `on` fst) xs
z -- put things together
```
New contributor
$endgroup$
1
$begingroup$
Some tips: flip the element and its index within the pairs returned byf
:f x=zip[0..length x]x
, sof
becomesf=zip[0..]
.g
is justg=map unzip
. The function to filter with inj
ish.fst
(<- flipped pairs!).j=filter(h.fst)
. Thefoldl1+
fromk
issum
and with a pointfree pair makingk=map((,)=<<sum.snd)
.sortBy(...)
can be replaced bysortOn fst
:l=snd.last.sortOn fst
. Finally as you are using all functions only once, you can inline them into a single pointfree expression:z=snd.last.sortOn fst.map((,)=<<sum.snd).filter(h.fst).map unzip.subsequences.zip[0..]
$endgroup$
– nimi
Apr 17 at 16:31
$begingroup$
.... Try it online!.
$endgroup$
– nimi
Apr 17 at 16:31
$begingroup$
oh, and no need to importData.Function
anymore.
$endgroup$
– nimi
Apr 17 at 16:32
$begingroup$
That's great, thanks for the feedback :)
$endgroup$
– bugs
Apr 17 at 17:05
$begingroup$
Nexth
: we're looking for non-adjacent elements, i.e. the difference of adjacent indices must be>1
.zipWith(-)=<<tail
builds such a list of differences, but fails for the empty list, so we need an additionaltail
on thesubsequences
to get rid of it. Inline again. Try it online!
$endgroup$
– nimi
Apr 17 at 17:27
|
show 1 more comment
$begingroup$
Haskell, 300 168 bytes
import Data.List
h[]=1>2
h(x:y)=fst$foldl(a c->((fst a)&&(c-snd a>1),c))(1<2,x)y
z=snd.last.sortOn fst.map((,)=<<sum.snd).filter(h.fst).map unzip.subsequences.zip[0..]
Try it online!
-132 bytes thanks to all the feedback from @nimi :)
Original
Ungolfed (original)
import Data.List
import Data.Function
f :: [Int] -> [(Int, Int)] -- attach indices for later use
f [] = []
f xs = zip xs [0..length xs]
g :: [[(Int, Int)]] -> [([Int], [Int])] -- rearrange into list of tuples
g [] = []
g (x:xs) = (map fst x, map snd x) : g xs
h :: [Int] -> Bool -- predicate that checks if the indices are at least 2 apart from each other
h [] = False
h (x:xs) = fst $ foldl (acc curr -> ((fst acc) && (curr - snd acc > 1), curr)) (True, x) xs
j :: [([Int], [Int])] -> [([Int], [Int])] -- remove sets that don't satisfy the condition
j xs = filter ((elements, indices) -> h indices) xs
k :: [([Int], [Int])] -> [(Int, ([Int], [Int]))] -- calculate some of elements
k xs = map ((elements, indices) -> (foldl1 (+) elements, (elements, indices))) xs
l :: [(Int, ([Int], [Int]))] -> ([Int], [Int]) -- grab max
l xs = snd $ last $ sortBy (compare `on` fst) xs
z -- put things together
```
New contributor
$endgroup$
1
$begingroup$
Some tips: flip the element and its index within the pairs returned byf
:f x=zip[0..length x]x
, sof
becomesf=zip[0..]
.g
is justg=map unzip
. The function to filter with inj
ish.fst
(<- flipped pairs!).j=filter(h.fst)
. Thefoldl1+
fromk
issum
and with a pointfree pair makingk=map((,)=<<sum.snd)
.sortBy(...)
can be replaced bysortOn fst
:l=snd.last.sortOn fst
. Finally as you are using all functions only once, you can inline them into a single pointfree expression:z=snd.last.sortOn fst.map((,)=<<sum.snd).filter(h.fst).map unzip.subsequences.zip[0..]
$endgroup$
– nimi
Apr 17 at 16:31
$begingroup$
.... Try it online!.
$endgroup$
– nimi
Apr 17 at 16:31
$begingroup$
oh, and no need to importData.Function
anymore.
$endgroup$
– nimi
Apr 17 at 16:32
$begingroup$
That's great, thanks for the feedback :)
$endgroup$
– bugs
Apr 17 at 17:05
$begingroup$
Nexth
: we're looking for non-adjacent elements, i.e. the difference of adjacent indices must be>1
.zipWith(-)=<<tail
builds such a list of differences, but fails for the empty list, so we need an additionaltail
on thesubsequences
to get rid of it. Inline again. Try it online!
$endgroup$
– nimi
Apr 17 at 17:27
|
show 1 more comment
$begingroup$
Haskell, 300 168 bytes
import Data.List
h[]=1>2
h(x:y)=fst$foldl(a c->((fst a)&&(c-snd a>1),c))(1<2,x)y
z=snd.last.sortOn fst.map((,)=<<sum.snd).filter(h.fst).map unzip.subsequences.zip[0..]
Try it online!
-132 bytes thanks to all the feedback from @nimi :)
Original
Ungolfed (original)
import Data.List
import Data.Function
f :: [Int] -> [(Int, Int)] -- attach indices for later use
f [] = []
f xs = zip xs [0..length xs]
g :: [[(Int, Int)]] -> [([Int], [Int])] -- rearrange into list of tuples
g [] = []
g (x:xs) = (map fst x, map snd x) : g xs
h :: [Int] -> Bool -- predicate that checks if the indices are at least 2 apart from each other
h [] = False
h (x:xs) = fst $ foldl (acc curr -> ((fst acc) && (curr - snd acc > 1), curr)) (True, x) xs
j :: [([Int], [Int])] -> [([Int], [Int])] -- remove sets that don't satisfy the condition
j xs = filter ((elements, indices) -> h indices) xs
k :: [([Int], [Int])] -> [(Int, ([Int], [Int]))] -- calculate some of elements
k xs = map ((elements, indices) -> (foldl1 (+) elements, (elements, indices))) xs
l :: [(Int, ([Int], [Int]))] -> ([Int], [Int]) -- grab max
l xs = snd $ last $ sortBy (compare `on` fst) xs
z -- put things together
```
New contributor
$endgroup$
Haskell, 300 168 bytes
import Data.List
h[]=1>2
h(x:y)=fst$foldl(a c->((fst a)&&(c-snd a>1),c))(1<2,x)y
z=snd.last.sortOn fst.map((,)=<<sum.snd).filter(h.fst).map unzip.subsequences.zip[0..]
Try it online!
-132 bytes thanks to all the feedback from @nimi :)
Original
Ungolfed (original)
import Data.List
import Data.Function
f :: [Int] -> [(Int, Int)] -- attach indices for later use
f [] = []
f xs = zip xs [0..length xs]
g :: [[(Int, Int)]] -> [([Int], [Int])] -- rearrange into list of tuples
g [] = []
g (x:xs) = (map fst x, map snd x) : g xs
h :: [Int] -> Bool -- predicate that checks if the indices are at least 2 apart from each other
h [] = False
h (x:xs) = fst $ foldl (acc curr -> ((fst acc) && (curr - snd acc > 1), curr)) (True, x) xs
j :: [([Int], [Int])] -> [([Int], [Int])] -- remove sets that don't satisfy the condition
j xs = filter ((elements, indices) -> h indices) xs
k :: [([Int], [Int])] -> [(Int, ([Int], [Int]))] -- calculate some of elements
k xs = map ((elements, indices) -> (foldl1 (+) elements, (elements, indices))) xs
l :: [(Int, ([Int], [Int]))] -> ([Int], [Int]) -- grab max
l xs = snd $ last $ sortBy (compare `on` fst) xs
z -- put things together
```
New contributor
edited Apr 17 at 17:14
New contributor
answered Apr 17 at 15:40
bugsbugs
2114
2114
New contributor
New contributor
1
$begingroup$
Some tips: flip the element and its index within the pairs returned byf
:f x=zip[0..length x]x
, sof
becomesf=zip[0..]
.g
is justg=map unzip
. The function to filter with inj
ish.fst
(<- flipped pairs!).j=filter(h.fst)
. Thefoldl1+
fromk
issum
and with a pointfree pair makingk=map((,)=<<sum.snd)
.sortBy(...)
can be replaced bysortOn fst
:l=snd.last.sortOn fst
. Finally as you are using all functions only once, you can inline them into a single pointfree expression:z=snd.last.sortOn fst.map((,)=<<sum.snd).filter(h.fst).map unzip.subsequences.zip[0..]
$endgroup$
– nimi
Apr 17 at 16:31
$begingroup$
.... Try it online!.
$endgroup$
– nimi
Apr 17 at 16:31
$begingroup$
oh, and no need to importData.Function
anymore.
$endgroup$
– nimi
Apr 17 at 16:32
$begingroup$
That's great, thanks for the feedback :)
$endgroup$
– bugs
Apr 17 at 17:05
$begingroup$
Nexth
: we're looking for non-adjacent elements, i.e. the difference of adjacent indices must be>1
.zipWith(-)=<<tail
builds such a list of differences, but fails for the empty list, so we need an additionaltail
on thesubsequences
to get rid of it. Inline again. Try it online!
$endgroup$
– nimi
Apr 17 at 17:27
|
show 1 more comment
1
$begingroup$
Some tips: flip the element and its index within the pairs returned byf
:f x=zip[0..length x]x
, sof
becomesf=zip[0..]
.g
is justg=map unzip
. The function to filter with inj
ish.fst
(<- flipped pairs!).j=filter(h.fst)
. Thefoldl1+
fromk
issum
and with a pointfree pair makingk=map((,)=<<sum.snd)
.sortBy(...)
can be replaced bysortOn fst
:l=snd.last.sortOn fst
. Finally as you are using all functions only once, you can inline them into a single pointfree expression:z=snd.last.sortOn fst.map((,)=<<sum.snd).filter(h.fst).map unzip.subsequences.zip[0..]
$endgroup$
– nimi
Apr 17 at 16:31
$begingroup$
.... Try it online!.
$endgroup$
– nimi
Apr 17 at 16:31
$begingroup$
oh, and no need to importData.Function
anymore.
$endgroup$
– nimi
Apr 17 at 16:32
$begingroup$
That's great, thanks for the feedback :)
$endgroup$
– bugs
Apr 17 at 17:05
$begingroup$
Nexth
: we're looking for non-adjacent elements, i.e. the difference of adjacent indices must be>1
.zipWith(-)=<<tail
builds such a list of differences, but fails for the empty list, so we need an additionaltail
on thesubsequences
to get rid of it. Inline again. Try it online!
$endgroup$
– nimi
Apr 17 at 17:27
1
1
$begingroup$
Some tips: flip the element and its index within the pairs returned by
f
: f x=zip[0..length x]x
, so f
becomes f=zip[0..]
. g
is just g=map unzip
. The function to filter with in j
is h.fst
(<- flipped pairs!). j=filter(h.fst)
. The foldl1+
from k
is sum
and with a pointfree pair making k=map((,)=<<sum.snd)
. sortBy(...)
can be replaced by sortOn fst
: l=snd.last.sortOn fst
. Finally as you are using all functions only once, you can inline them into a single pointfree expression: z=snd.last.sortOn fst.map((,)=<<sum.snd).filter(h.fst).map unzip.subsequences.zip[0..]
$endgroup$
– nimi
Apr 17 at 16:31
$begingroup$
Some tips: flip the element and its index within the pairs returned by
f
: f x=zip[0..length x]x
, so f
becomes f=zip[0..]
. g
is just g=map unzip
. The function to filter with in j
is h.fst
(<- flipped pairs!). j=filter(h.fst)
. The foldl1+
from k
is sum
and with a pointfree pair making k=map((,)=<<sum.snd)
. sortBy(...)
can be replaced by sortOn fst
: l=snd.last.sortOn fst
. Finally as you are using all functions only once, you can inline them into a single pointfree expression: z=snd.last.sortOn fst.map((,)=<<sum.snd).filter(h.fst).map unzip.subsequences.zip[0..]
$endgroup$
– nimi
Apr 17 at 16:31
$begingroup$
.... Try it online!.
$endgroup$
– nimi
Apr 17 at 16:31
$begingroup$
.... Try it online!.
$endgroup$
– nimi
Apr 17 at 16:31
$begingroup$
oh, and no need to import
Data.Function
anymore.$endgroup$
– nimi
Apr 17 at 16:32
$begingroup$
oh, and no need to import
Data.Function
anymore.$endgroup$
– nimi
Apr 17 at 16:32
$begingroup$
That's great, thanks for the feedback :)
$endgroup$
– bugs
Apr 17 at 17:05
$begingroup$
That's great, thanks for the feedback :)
$endgroup$
– bugs
Apr 17 at 17:05
$begingroup$
Next
h
: we're looking for non-adjacent elements, i.e. the difference of adjacent indices must be >1
. zipWith(-)=<<tail
builds such a list of differences, but fails for the empty list, so we need an additional tail
on the subsequences
to get rid of it. Inline again. Try it online!$endgroup$
– nimi
Apr 17 at 17:27
$begingroup$
Next
h
: we're looking for non-adjacent elements, i.e. the difference of adjacent indices must be >1
. zipWith(-)=<<tail
builds such a list of differences, but fails for the empty list, so we need an additional tail
on the subsequences
to get rid of it. Inline again. Try it online!$endgroup$
– nimi
Apr 17 at 17:27
|
show 1 more comment
$begingroup$
Charcoal, 46 bytes
≔⟦υ⟧ηFθ«≔υζ≔Eη⁺κ⟦ι⟧υ≔⁺ζηη»≔Φ⁺υηιη≔EηΣιζI§η⌕ζ⌈ζ
Try it online! Link is to verbose version of code. Explanation:
≔⟦υ⟧η
The variable u
is predefined with an empty list. This is put in a list which is assigned to h
. These variables act as accumulators. u
contains the sublists that include the latest element of the input q
while h
contains the sublists that do not (and therefore are suitable for appending the next element of the input).
Fθ«
Loop over the elements of the input.
≔υζ
Save the list of sublists that contain the previous element.
≔Eη⁺κ⟦ι⟧υ
Take all of the sublists that do not contain the previous element, append the current element, and save the result as the list of sublists that contain the current element. (I don't use Push
here as I need to clone the list.)
≔⁺ζηη»
Concatenate both previous sublists into the new list of sublists that do not contain the current element.
≔Φ⁺υηιη
Concatenate the sublists one last time and remove the original empty list (which Charcoal can't sum anyway).
≔EηΣιζ
Compute the sums of all of the sublists.
I§η⌕ζ⌈ζ
Find an index of the greatest sum and output the corresponding sublist.
$endgroup$
add a comment |
$begingroup$
Charcoal, 46 bytes
≔⟦υ⟧ηFθ«≔υζ≔Eη⁺κ⟦ι⟧υ≔⁺ζηη»≔Φ⁺υηιη≔EηΣιζI§η⌕ζ⌈ζ
Try it online! Link is to verbose version of code. Explanation:
≔⟦υ⟧η
The variable u
is predefined with an empty list. This is put in a list which is assigned to h
. These variables act as accumulators. u
contains the sublists that include the latest element of the input q
while h
contains the sublists that do not (and therefore are suitable for appending the next element of the input).
Fθ«
Loop over the elements of the input.
≔υζ
Save the list of sublists that contain the previous element.
≔Eη⁺κ⟦ι⟧υ
Take all of the sublists that do not contain the previous element, append the current element, and save the result as the list of sublists that contain the current element. (I don't use Push
here as I need to clone the list.)
≔⁺ζηη»
Concatenate both previous sublists into the new list of sublists that do not contain the current element.
≔Φ⁺υηιη
Concatenate the sublists one last time and remove the original empty list (which Charcoal can't sum anyway).
≔EηΣιζ
Compute the sums of all of the sublists.
I§η⌕ζ⌈ζ
Find an index of the greatest sum and output the corresponding sublist.
$endgroup$
add a comment |
$begingroup$
Charcoal, 46 bytes
≔⟦υ⟧ηFθ«≔υζ≔Eη⁺κ⟦ι⟧υ≔⁺ζηη»≔Φ⁺υηιη≔EηΣιζI§η⌕ζ⌈ζ
Try it online! Link is to verbose version of code. Explanation:
≔⟦υ⟧η
The variable u
is predefined with an empty list. This is put in a list which is assigned to h
. These variables act as accumulators. u
contains the sublists that include the latest element of the input q
while h
contains the sublists that do not (and therefore are suitable for appending the next element of the input).
Fθ«
Loop over the elements of the input.
≔υζ
Save the list of sublists that contain the previous element.
≔Eη⁺κ⟦ι⟧υ
Take all of the sublists that do not contain the previous element, append the current element, and save the result as the list of sublists that contain the current element. (I don't use Push
here as I need to clone the list.)
≔⁺ζηη»
Concatenate both previous sublists into the new list of sublists that do not contain the current element.
≔Φ⁺υηιη
Concatenate the sublists one last time and remove the original empty list (which Charcoal can't sum anyway).
≔EηΣιζ
Compute the sums of all of the sublists.
I§η⌕ζ⌈ζ
Find an index of the greatest sum and output the corresponding sublist.
$endgroup$
Charcoal, 46 bytes
≔⟦υ⟧ηFθ«≔υζ≔Eη⁺κ⟦ι⟧υ≔⁺ζηη»≔Φ⁺υηιη≔EηΣιζI§η⌕ζ⌈ζ
Try it online! Link is to verbose version of code. Explanation:
≔⟦υ⟧η
The variable u
is predefined with an empty list. This is put in a list which is assigned to h
. These variables act as accumulators. u
contains the sublists that include the latest element of the input q
while h
contains the sublists that do not (and therefore are suitable for appending the next element of the input).
Fθ«
Loop over the elements of the input.
≔υζ
Save the list of sublists that contain the previous element.
≔Eη⁺κ⟦ι⟧υ
Take all of the sublists that do not contain the previous element, append the current element, and save the result as the list of sublists that contain the current element. (I don't use Push
here as I need to clone the list.)
≔⁺ζηη»
Concatenate both previous sublists into the new list of sublists that do not contain the current element.
≔Φ⁺υηιη
Concatenate the sublists one last time and remove the original empty list (which Charcoal can't sum anyway).
≔EηΣιζ
Compute the sums of all of the sublists.
I§η⌕ζ⌈ζ
Find an index of the greatest sum and output the corresponding sublist.
answered Apr 17 at 20:03
NeilNeil
83.2k745179
83.2k745179
add a comment |
add a comment |
$begingroup$
Wolfram Language (Mathematica), 70 bytes
MaximalBy[Select[q=Rest@Subsets@#,Or@@(MatchQ[#~Riffle~_]/@q)&],Tr,1]&
Try it online!
High-level search
Select[q=Rest@Subsets@#, ] (*choose nonempty subsets of the input such that*)
Or@@(MatchQ[ ]/@q)& (*there exists a subset of the input which matches*)
#~Riffle~_ (*this list, with an item inserted between adjacent elements*)
MaximalBy[ ,Tr,1]& (*and return one with the greatest total*)
,1
is required so as not to inadvertently return invalid sets (otherwise, for example, an input of 1,1,1
would result in an output of 1,1,1,1,1,1
)
$endgroup$
add a comment |
$begingroup$
Wolfram Language (Mathematica), 70 bytes
MaximalBy[Select[q=Rest@Subsets@#,Or@@(MatchQ[#~Riffle~_]/@q)&],Tr,1]&
Try it online!
High-level search
Select[q=Rest@Subsets@#, ] (*choose nonempty subsets of the input such that*)
Or@@(MatchQ[ ]/@q)& (*there exists a subset of the input which matches*)
#~Riffle~_ (*this list, with an item inserted between adjacent elements*)
MaximalBy[ ,Tr,1]& (*and return one with the greatest total*)
,1
is required so as not to inadvertently return invalid sets (otherwise, for example, an input of 1,1,1
would result in an output of 1,1,1,1,1,1
)
$endgroup$
add a comment |
$begingroup$
Wolfram Language (Mathematica), 70 bytes
MaximalBy[Select[q=Rest@Subsets@#,Or@@(MatchQ[#~Riffle~_]/@q)&],Tr,1]&
Try it online!
High-level search
Select[q=Rest@Subsets@#, ] (*choose nonempty subsets of the input such that*)
Or@@(MatchQ[ ]/@q)& (*there exists a subset of the input which matches*)
#~Riffle~_ (*this list, with an item inserted between adjacent elements*)
MaximalBy[ ,Tr,1]& (*and return one with the greatest total*)
,1
is required so as not to inadvertently return invalid sets (otherwise, for example, an input of 1,1,1
would result in an output of 1,1,1,1,1,1
)
$endgroup$
Wolfram Language (Mathematica), 70 bytes
MaximalBy[Select[q=Rest@Subsets@#,Or@@(MatchQ[#~Riffle~_]/@q)&],Tr,1]&
Try it online!
High-level search
Select[q=Rest@Subsets@#, ] (*choose nonempty subsets of the input such that*)
Or@@(MatchQ[ ]/@q)& (*there exists a subset of the input which matches*)
#~Riffle~_ (*this list, with an item inserted between adjacent elements*)
MaximalBy[ ,Tr,1]& (*and return one with the greatest total*)
,1
is required so as not to inadvertently return invalid sets (otherwise, for example, an input of 1,1,1
would result in an output of 1,1,1,1,1,1
)
answered Apr 18 at 8:16
attinatattinat
60917
60917
add a comment |
add a comment |
$begingroup$
Japt -h
, 22 bytes
Êo à k_mÄ øZÃm!gU
fÊñx
Try it
$endgroup$
add a comment |
$begingroup$
Japt -h
, 22 bytes
Êo à k_mÄ øZÃm!gU
fÊñx
Try it
$endgroup$
add a comment |
$begingroup$
Japt -h
, 22 bytes
Êo à k_mÄ øZÃm!gU
fÊñx
Try it
$endgroup$
Japt -h
, 22 bytes
Êo à k_mÄ øZÃm!gU
fÊñx
Try it
answered Apr 18 at 20:10
Embodiment of IgnoranceEmbodiment of Ignorance
3,064127
3,064127
add a comment |
add a comment |
$begingroup$
Japt -h
, 21 bytes
Ever have one of those challenges where you completely forget how to golf?!
ð¤à fÊk_än ø1îmgUÃñx
Try it
ð¤à fÊk_än ø1îmgUÃñx :Implicit input of array U
ð :Indices of elements that return true when
¤ : Converted to a base-2 string (to account for 0s)
à :Combinations
f :Filter by
Ê : Length (to remove the empty combination)
k_ :Remove elements that return true
än : Deltas
ø1 : Contains 1
à :End remove
® :Map
m : Map
gU : Index into U
à :End map
ñ :Sort by
x : Sum
:Implicit output of last element
$endgroup$
add a comment |
$begingroup$
Japt -h
, 21 bytes
Ever have one of those challenges where you completely forget how to golf?!
ð¤à fÊk_än ø1îmgUÃñx
Try it
ð¤à fÊk_än ø1îmgUÃñx :Implicit input of array U
ð :Indices of elements that return true when
¤ : Converted to a base-2 string (to account for 0s)
à :Combinations
f :Filter by
Ê : Length (to remove the empty combination)
k_ :Remove elements that return true
än : Deltas
ø1 : Contains 1
à :End remove
® :Map
m : Map
gU : Index into U
à :End map
ñ :Sort by
x : Sum
:Implicit output of last element
$endgroup$
add a comment |
$begingroup$
Japt -h
, 21 bytes
Ever have one of those challenges where you completely forget how to golf?!
ð¤à fÊk_än ø1îmgUÃñx
Try it
ð¤à fÊk_än ø1îmgUÃñx :Implicit input of array U
ð :Indices of elements that return true when
¤ : Converted to a base-2 string (to account for 0s)
à :Combinations
f :Filter by
Ê : Length (to remove the empty combination)
k_ :Remove elements that return true
än : Deltas
ø1 : Contains 1
à :End remove
® :Map
m : Map
gU : Index into U
à :End map
ñ :Sort by
x : Sum
:Implicit output of last element
$endgroup$
Japt -h
, 21 bytes
Ever have one of those challenges where you completely forget how to golf?!
ð¤à fÊk_än ø1îmgUÃñx
Try it
ð¤à fÊk_än ø1îmgUÃñx :Implicit input of array U
ð :Indices of elements that return true when
¤ : Converted to a base-2 string (to account for 0s)
à :Combinations
f :Filter by
Ê : Length (to remove the empty combination)
k_ :Remove elements that return true
än : Deltas
ø1 : Contains 1
à :End remove
® :Map
m : Map
gU : Index into U
à :End map
ñ :Sort by
x : Sum
:Implicit output of last element
edited Apr 19 at 21:25
answered Apr 17 at 21:49
ShaggyShaggy
19.1k21768
19.1k21768
add a comment |
add a comment |
$begingroup$
Python 2, 63 70 65 bytes
f=lambda a:a and max([a[:1],a[:1]+f(a[2:]),f(a[1:])],key=sum)or a
Try it online!
5 bytes thx to ArBo
$endgroup$
$begingroup$
Your test case[1, 7, 4, -2] [1, 4] 5 7
is getting the wrong answer.
$endgroup$
– xnor
2 days ago
$begingroup$
@xnor: fixed now.
$endgroup$
– Chas Brown
2 days ago
$begingroup$
65 bytes
$endgroup$
– ArBo
2 days ago
add a comment |
$begingroup$
Python 2, 63 70 65 bytes
f=lambda a:a and max([a[:1],a[:1]+f(a[2:]),f(a[1:])],key=sum)or a
Try it online!
5 bytes thx to ArBo
$endgroup$
$begingroup$
Your test case[1, 7, 4, -2] [1, 4] 5 7
is getting the wrong answer.
$endgroup$
– xnor
2 days ago
$begingroup$
@xnor: fixed now.
$endgroup$
– Chas Brown
2 days ago
$begingroup$
65 bytes
$endgroup$
– ArBo
2 days ago
add a comment |
$begingroup$
Python 2, 63 70 65 bytes
f=lambda a:a and max([a[:1],a[:1]+f(a[2:]),f(a[1:])],key=sum)or a
Try it online!
5 bytes thx to ArBo
$endgroup$
Python 2, 63 70 65 bytes
f=lambda a:a and max([a[:1],a[:1]+f(a[2:]),f(a[1:])],key=sum)or a
Try it online!
5 bytes thx to ArBo
edited 2 days ago
answered Apr 19 at 23:04
Chas BrownChas Brown
5,2491523
5,2491523
$begingroup$
Your test case[1, 7, 4, -2] [1, 4] 5 7
is getting the wrong answer.
$endgroup$
– xnor
2 days ago
$begingroup$
@xnor: fixed now.
$endgroup$
– Chas Brown
2 days ago
$begingroup$
65 bytes
$endgroup$
– ArBo
2 days ago
add a comment |
$begingroup$
Your test case[1, 7, 4, -2] [1, 4] 5 7
is getting the wrong answer.
$endgroup$
– xnor
2 days ago
$begingroup$
@xnor: fixed now.
$endgroup$
– Chas Brown
2 days ago
$begingroup$
65 bytes
$endgroup$
– ArBo
2 days ago
$begingroup$
Your test case
[1, 7, 4, -2] [1, 4] 5 7
is getting the wrong answer.$endgroup$
– xnor
2 days ago
$begingroup$
Your test case
[1, 7, 4, -2] [1, 4] 5 7
is getting the wrong answer.$endgroup$
– xnor
2 days ago
$begingroup$
@xnor: fixed now.
$endgroup$
– Chas Brown
2 days ago
$begingroup$
@xnor: fixed now.
$endgroup$
– Chas Brown
2 days ago
$begingroup$
65 bytes
$endgroup$
– ArBo
2 days ago
$begingroup$
65 bytes
$endgroup$
– ArBo
2 days ago
add a comment |
If this is an answer to a challenge…
…Be sure to follow the challenge specification. However, please refrain from exploiting obvious loopholes. Answers abusing any of the standard loopholes are considered invalid. If you think a specification is unclear or underspecified, comment on the question instead.
…Try to optimize your score. For instance, answers to code-golf challenges should attempt to be as short as possible. You can always include a readable version of the code in addition to the competitive one.
Explanations of your answer make it more interesting to read and are very much encouraged.…Include a short header which indicates the language(s) of your code and its score, as defined by the challenge.
More generally…
…Please make sure to answer the question and provide sufficient detail.
…Avoid asking for help, clarification or responding to other answers (use comments instead).
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
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f183390%2fmaximum-summed-subsequences-with-non-adjacent-items%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
If there is more than one identical set (but from different indices) is it ok to list all of them? e.g.
[5,100,5]
twice for your third example.$endgroup$
– Nick Kennedy
Apr 17 at 13:53
1
$begingroup$
powerset
is a set of subsets isn't it? but it looks like you are returning a set of subsequences? [4,5,4,3] would result in either [4,4] where [4,4] is clearly not a set.$endgroup$
– Expired Data
Apr 17 at 14:19
1
$begingroup$
@Arnauld Yes, if the values are key-value pairs with their index it's clear which indexed values are meant in the input, so they can be in any order. Will also edit this into the challenge description.
$endgroup$
– Kevin Cruijssen
Apr 17 at 16:47
2
$begingroup$
Just to be sure: outputting the indices isn't an option, is it?
$endgroup$
– Shaggy
Apr 17 at 22:19
1
$begingroup$
The classical term is "subsequence". This has the same problem of people thinking of contiguous subsequences, though. I would say "subset" if we were actually working with sets here, but these are definitely sequences - order matters and duplicates are allowed.
$endgroup$
– user2357112
Apr 18 at 9:18