# Cap the highest values in a list so that the sum equals a given number

A slightly more challenging one compared to my previous challenge. Given a list of positive integers (>0) and the positive integer m, output a list of positive integers that are capped values of the input values so that the sum of the capped values equals m. Cap the highest values first. And keep the same order.

Cases

(Given 'list' and 'sum' output 'list')

• Given 4, 2 and 6 output 4, 2 no capping needed (ncn), keep order (ko)
• Given 2, 4 and 6 output 2, 4 ncn, ko
• Given 3, 3 and 6 output 3, 3 ncn
• Given 3, 3 and 7 output 3, 3 ncn

Then this:

• Given 4, 2 and 5 output 3, 2 cap the highest (cth), ko
• Given 2, 4 and 5 output 2, 3 cth, ko
• Given 3, 3 and 5 output 3, 2 or 2, 3 cap any of the highest (cath)

Then this:

• Given 5, 4, 2 and 10 output 4, 4, 2 cth, ko
• Given 2, 4, 5 and 10 output 2, 4, 4 cth, ko
• Given 4, 4, 2 and 7 output 3, 2, 2 or 2, 3, 2 cth, cath, ko
• Given 4, 2, 4 and 7 output 3, 2, 2 or 2, 2, 3 cth, cath, ko

Then this:

• Given 4, 4, 2 and 5 output 2, 2, 1 or any permutation (oap)
• Given 2, 4, 4 and 5 output 1, 2, 2 oap
• Given 4, 4, 2 and 4 output 1, 2, 1 oap
• Given 2, 4, 4 and 4 output 1, 1, 2 oap
• Given 70, 80, 90 and 10 output 3, 3, 4 oap

Then this:

• Given 4, 2, 4 and 2 output an error or a falsy value, because the sum of 3 positive integers cannot be 2.

Rules

• Both input and output are all about positive integers (>0)
• The number of values in the input and output list are equal.
• The sum of the output values is exactly equal to m or less than m only if the sum of the input values was already lower.
• If the sum of the values in the input list is already lower then or equal to m, no capping is needed. (ncn)
• Cap the highest values first (cth)
• When multiple values are the highest value and equally high, it doesn't matter which you cap. (cath)
• The capped values in the output list have to be in the same order as their original values in the input list. (ko)
• When at some point (thinking iteratively) all values are equally high, it stops being important which you cap.
• If there's no solution output an error or a falsy value.

The winner

The shortest valid answer - measured in bytes - wins.

Apart form the rules, I'm interested to see a program that keeps a value intact as long as possible. Consider the input values a plant each with the heights 10,2,10 and the maximum m=5, it would be a waste to cap the baby plant in the middle.

• -1 for "no recursion". It makes this difficult if not impossible for many languages (not just esolangs), it's an ambiguous and unobservable requirement and I don't think it adds anything to the challenge. – Not a tree Jul 12 '17 at 22:47
• What are the allowable answers to 3, 2 and 3? – Ørjan Johansen Jul 13 '17 at 0:26
• Could you add a test case for when m is greater than the total? – Jonathan Allan Jul 13 '17 at 1:03
• Could you also explain the rules more clearly? I cant quite understand the ko rule - in the 4,4,2 and 5 case are you capping the 2 to 1 or are you capping one of the 4s to a 1 and then rearranging the items to match the input in some way? (note that if it is done iteratively we reach 2,2,2 at which point we can cath and yield 1,2,2 following all the other rules). – Jonathan Allan Jul 13 '17 at 1:31
• @JonathanAllan Your right. When at some point (thinking iteratively) all are an even height, it stops being important which you cap. – Christiaan Westerbeek Jul 13 '17 at 5:46

# Jelly, 17 bytes

œṡṀ‘jṀ’µS>⁴µ¿¹0Ạ?


Try it online!

Uses iterative approach: repetitively subtract 1 from the highest element.

œṡṀ‘jṀ’µS>⁴µ¿¹0Ạ? - Main link. First input list, second input integer.
µ¿       - While:
S             - Sum of the list
>            - greater than
⁴           - second input
µ            - Do:
œṡ                    - split list by first occurrence of
Ṁ                   - the maximum element
‘                  - increment all
j                 - join by
Ṁ                - maximum element
’               - increment
?   - If:
Ạ      - no elements are non-zero
¹        - Then: output the list
0       - Else: return 0.


# Python 3, 7077 56 bytes

-21 bytes thanks to Jonathan Allan!

def f(l,n):
while n/all(l)<sum(l):l[l.index(max(l))]-=1


Try it online!

• @JonathanAllan I added a fix for the latter case that didn't change the byte count. I also am unsure about the first issue seeing as it doesn't line up with an iterative approach to reducing values. I will await further clarification prior to making a fix. – notjagan Jul 13 '17 at 1:48
• This answer is fine now. Check the update of my question – Christiaan Westerbeek Jul 13 '17 at 5:48
• Save 11 bytes with while n/all(l)<sum(l):l[l.index(max(l))]-=1 – Jonathan Allan Jul 13 '17 at 23:01
• ...in fact meta consensus is that return values may be modified inputs passed by reference, like l here, so this saves another 10 bytes – Jonathan Allan Jul 13 '17 at 23:45
• @JonathanAllan Nice! I don't know why this didn't occur to me earlier. – notjagan Jul 13 '17 at 23:54

# PHP>=7.1, 94 bytes

<?for([$a,$s]=$_GET;array_sum($a)>$s;)$a[array_flip($a)[max($a)]]--;print_r(min($a)?$a:0);


replace array_flip($a)[max($a)] with array_search(max($a),$a) to cap the last/first item with the maximum value

PHP Sandbox Online

# Mathematica, 79 bytes

(u:=Plus@@a;For[a=#2,u>#,a[[#&@@a~Position~Max@a]]--];Min@a>0&&u==#||Quit[];a)&


Takes sum and List of integers

# Haskell, 53 bytes

c takes an integer and a list of integers, returning a list of integers. Use as c 6 [4,2].

c n=until((<=n).sum)f
f(x:y)|any(>x)y=x:f y|x>1=x-1:y


Try it online!

# How it works

• c n applies f to its (implicit) list argument until its sum is <= n.
• f takes and returns a list of integers. It finds the first maximum value in the list by recursing, and then reduces it by 1, unless the maximum is <=1, in which case a non-exhaustive patterns error is raised.

# R, 61 56 bytes

-5 bytes thanks to Leaky Nun

function(l,s){while(sum(l)>s)l[which.max(l)]=max(l)-1;l}


Anonymous function. Returns a vector with first entry zero (falsey in R) for invalid input.

Try it online!

# Jelly, 17 bytes

Note: this solution was ready just as the question was put on hold 33 hours ago.

_MḢ$¦S>¥ ç⁹$ÐLẠȧ$ A dyadic link returning the list of positive integers or 0 (an error rather than 0 is also possible by moving Ạȧ$ from the end of the second line to the end of the first line).

Try it online! or see a test suite.

### How?

_MḢ$¦S>¥ - Link 1, single conditional decrement: list a; number m - ...subtracts 1 from the first maximal element of a if sum(a)>m - else subtracts 0 from the first maximal element of a ¥ - last two links as a dyad (left=a; right=m) S - sum(a) > - greater than m? (1 if it is, 0 otherwise) - call this x ¦ - sparse application of: _ - body: subtraction (left=a; right=x)$     -   at indexes: last two links as a monad:
M       -     indexes of maximal elements

ç⁹$ÐLẠȧ$ - Link: list a; number m
ÐL    - loop until the result does not change:
$- last two links as a monad: ⁹ - chain's right argument, m ç - call the last link as a dyad (left=current_a; right=m)$ - last two links as a monad:
Ạ   -   all truthy? (0 if any of the final a's elements are 0)
ȧ  -   logical and (if all were truthy yield the final a, otherwise 0)


# CJam, 30 bytes

{_2$:+<{\__:e>_@#\(t\F}{;}?}:F  This is essentially of a named function, F, that expects a list and a number on the stack and returns a list on the stack. ### Explanation I'll refer to the list as l and the number as n. _ e# Copy n. 2$     e# Copy l.
:+     e# Sum l.
<      e# Check if n < sum(l).
{      e# If it is:
\__   e#  Bring l to the top of stack and make 2 copies of it.
:e>_  e#  Get the maximum number in l and copy it.
@#    e#  Bring l back to the top and find the index of max(l) in l.
\(    e#  Decrement max(l).
t     e#  Set the element of l at the position of max(l) to max(l)-1.
\     e#  Swap, so now the top of the stack has the new l just under n.
F     e#  Call F again on the new l and n.
}{     e# Else:
;     e#  Delete n.
}?     e# (end if)