Win a War (or at least a few battles)
You have an army of size $n$ that you need to split up to fight $k$ battles simultaneously against an opposing army $A$. In each battle, the army with the most troops present wins - no one wins a tie. Your scouts have just reported back with the enemy troops' movements - how can you divide your army to win the most battles? What's more, if 2 different arrangements win the same number of battles, you prefer the arrangement that beats the most enemy soldiers.
Input
The integers $n, k$ and an array $A$ that contains the number of enemy troops at each battle location.
Output
An array corresponding to A that represents the number of your own troops you will send to that location. There are most likely be multiple solutions - you may return any possible solution that maximizes the amount of battles won while also maximizing the numbers of soldiers beaten within the maximum amount of battles won.
Example
$n = 100, k = 5, A = [20, 20, 20, 20, 20]$
The enemy has split their army evenly - to win the maximum amount of battles, 4, we can simply ignore battle 1 and distribute evenly among the other 4, for example $[0, 25, 25, 25, 25]$.
$n = 50, k = 5, A = [40, 30, 20, 10, 0]$
We're outnumbered, but we can still win 3 battles. $[0, 0, 25, 15, 10]$ would win 3 battles, but remember, we want to win against larger enemy forces if possible, so a correct optimal answer could be $[0, 35, 0, 14, 1]$
More Input/Output Examples
Only one of many possible outputs is shown.
n, k, A -> Output
1, 1, [0] -> [1]
2, 2, [1,1] -> [2, 0]
10, 3, [4, 3, 3] -> [5, 0, 5]
100, 3, [50, 25, 25] -> [60, 40, 0]
100, 5, [33, 34, 33, 0, 0] -> [0, 50, 40, 5, 5]
This is code-golf, so shortest solution in each language wins.
2 answers
You are accessing this answer with a direct link, so it's being shown above all other answers regardless of its score. You can return to the normal view.
BQN, 44 bytesSBCS
+´{(≠↑𝕨-𝔽)⊸+2↓⊑∨(≍×𝕨≥⊢)○𝔽˜⟜×⊸∾¨(<1+𝕩)×⥊↕2¨𝕩}
The solution is a function that takes n as the left argument (𝕨) and A as the right argument (𝕩). k is just the length of A, so it's not used as an argument. The function builds a list of all possible combinations, then calculates a score for each one: the number of battles won followed by the number of troops required, but reduced to 0 if it requires more troops than are available. It gives a wrong answer if no battles can be won since all scores are 0 (could be fixed by incrementing the not-impossible scores). Note that the number of troops required is always one more than the number of enemy troops.
Range (↕) makes the list of combinations. When given a shape argument, it returns an array of that shape where each element's value is its own index. With a list of 2s, the possible indices for each axis are 0 and 1, and the result contains every combination of choices. But it's an array, so Deshape (⥊) is needed to turn it into a list that can be sorted.
Combinators and trains are used several times.
The function consists of a block 1-modifier (inside {}) applied to the operand +´ (Plus Fold, that is, sum) to give a derived function. Inside the modifier 𝔽 is the operand (sum) 𝕨 is the left argument A, and 𝕩 is the right argument n. Explanation for the three sections:
(<1+𝕩)×⥊↕2¨𝕩 # Create list of combinations
2¨𝕩 # List with each element of 𝕩 replaced with 2
↕ # Range: array of index lists with that shape
⥊ # Flatten from 2×2×2… array to list
(<1+𝕩) # Enclose 1+𝕩, giving a 0-axis array
× # Multiply: turn 1s in ⥊↕2¨𝕩 into entries of 1+𝕩
2↓⊑∨(≍×𝕨≥⊢)○𝔽˜⟜×⊸∾¨ # Select the best list
¨ # On each list:
⟜× # Use sign (1 if some, 0 if none) as right argument
˜ # No wait, left argument
○𝔽 # Sum both arguments (values and signs)
≍ # Pair sums: ⟨battles won, troops required⟩
𝕨≥⊢ # Do we have the troops? ⊢ is right argument
( × ) # Multiply: set score list to 0 if impossible
⊸∾ # Prepend to original list
∨ # Sort descending
⊑ # First—highest—entry
2↓ # Remove score, leaving required troop counts
(≠↑𝕨-𝔽)⊸+ # Add in remaining troops
𝕨-𝔽 # Troops left over
≠ # Length of result list
( ↑ ) # Take, padding leftovers with 0
⊸+ # And add to troop counts
0 comment threads
JavaScript, 227 bytes
(n,k,A,C=(a,b)=>a?[...C(--a,b),b(a)]:[],f=m=>m?C(n+1,i=>f(m-1).map(([p,s])=>
[[...p,i],s+i])).flat():[[[],0]])=>f(k).map(([b,s])=>a=s-n?a:b.map((a,b)=>(q
=A[b])<a&&(e++,f+=q),e=f=0,[,c,d]=a)&&e<c|e==c&f<d?a:[b,e,f],a=[,-1])&&a[0]
Explanation: recursively generates all possible troop arrangements of length $k$ whose sum is $n$ and picks the one with the maximum score.
Try it online! (229 bytes, because TIO uses an old version of Node.js that has a parsing issue when an arrow function appears inside a call)
0 comment threads
1 comment thread