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

Question

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.

Answer 1

Python 3, 70 77 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!

Answer 2

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

Answer 3

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

Answer 4

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.

Answer 5

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!

Answer 6

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
  Ḣ      -     head

ç⁹$Ð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)

Answer 7

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.

Answer 8

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.

Try it online! or run a test suite

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)