24
\$\begingroup\$

Write a function which takes in a list of positive integers and returns a list of integers approximating the percent of total for the corresponding integer in the same position.

All integers in the return list must exactly add up to 100. You can assume the sum of integers passed in is greater than 0. How you want to round or truncate decimals is up to you as long as any single resulting integer returned as a percentage is off by no more than 1 in either direction.

p([1,0,2])      ->  [33,0,67] or [34,0,66]
p([1000,1000])  ->  [50,50] or [49,51] or [51,49]
p([1,1,2,4])    ->  [12,12,25,51] or [13,12,25,50] or [12,13,25,50] or [13,13,25,49] or [13,12,26,49] or [12,13,26,49] or [12,12,26,50]
p([0,0,0,5,0])  ->  [0,0,0,100,0]

This is , so shortest code in bytes wins!

\$\endgroup\$
8
  • \$\begingroup\$ Must our algorithm be deterministic? Must it always terminate within a bounded time? \$\endgroup\$
    – lirtosiast
    Oct 8, 2015 at 0:40
  • 1
    \$\begingroup\$ I assume that [13,13,25,49] is also ok for the third example. \$\endgroup\$
    – Titus
    Oct 20, 2017 at 6:27
  • 1
    \$\begingroup\$ I suggest that you add another test case: p([2,2,2,2,2,3]). It has many possible legal answers, but not all 2's can be mapped to the same value. This eliminates many overly-simple algorithms that work on all the previous test cases because the rounding isn't too bad. \$\endgroup\$ May 18, 2018 at 17:12
  • 4
    \$\begingroup\$ Can p([1000,1000]) -> [49,51]? \$\endgroup\$
    – l4m2
    May 18, 2018 at 17:35
  • 1
    \$\begingroup\$ @l4m2 It seems wrong, but both the results are off by 1 and no more, so it follows the spec \$\endgroup\$
    – edc65
    May 19, 2018 at 8:13

22 Answers 22

21
\$\begingroup\$

Dyalog APL, 21 19 16 bytes

+\⍣¯1∘⌊100×+\÷+/

The above is a train equivalent of

{+\⍣¯1⌊100×+\⍵÷+/⍵}

Try it online.

How it works

                 ⍝ Sample input: 1 1 2 4
           +\    ⍝ Cumulative sum of input. (1 2 4 8)
              +/ ⍝ Sum of input. (8)
             ÷   ⍝ Divide the first result by the second. (0.125 0.25 0.5 1)
       100×      ⍝ Multiply each quotient by 100. (12.5 25 50 100)
      ⌊          ⍝ Round the products down to the nearest integer... (12 25 50 100)
     ∘           ⍝ and ...
  ⍣¯1            ⍝ apply the inverse of...
+\               ⍝ the cumulative sum. (12 13 25 50)
\$\endgroup\$
2
  • 11
    \$\begingroup\$ If only Fermat could have taken golf lessons from you. \$\endgroup\$ Oct 8, 2015 at 4:12
  • 1
    \$\begingroup\$ @TessellatingHeckler I see what you did there. Maybe then he'd have enough room in the margins for his proof. :) \$\endgroup\$
    – mbomb007
    Oct 9, 2015 at 20:08
14
\$\begingroup\$

TI-BASIC, 26 23 16 bytes

For TI-83+/84+ series calculators.

ΔList(augment({0},int(cumSum(ᴇ2Ans/sum(Ans

Thanks to @Dennis for a beautiful algorithm! We take the cumulative sum of the list after converting to percents, then floor, tack a 0 onto the front, and take differences. ᴇ2 is one byte shorter than 100.

At the same byte count is:

ΔList(augment({0},int(cumSum(Ans/sum(Ans%

Fun fact: % is a two-byte token that multiplies a number by .01—but there's no way to type it into the calculator! You need to either edit the source outside or use an assembly program.

Old code:

int(ᴇ2Ans/sum(Ans
Ans+(ᴇ2-sum(Ans)≥cumSum(1 or Ans

The first line calculates all floored percents, then the second line adds 1 to the first N elements, where N is the percentage left over. cumSum( stands for "cumulative sum".

Example with {1,1,2,4}:

          sum(Ans                  ; 8
int(ᴇ2Ans/                         ; {12,12,25,50}

                        1 or Ans   ; {1,1,1,1}
                 cumSum(           ; {1,2,3,4}
     ᴇ2-sum(Ans)                   ; 1
                ≥                  ; {1,0,0,0}
Ans+                               ; {13,12,25,50}

We won't have N>dim([list], because no percentage is decreased by more than 1 in flooring.

\$\endgroup\$
6
  • \$\begingroup\$ Not sure how you counting the bytes here, it looks awfully longer than 23 to me \$\endgroup\$ Oct 8, 2015 at 1:51
  • \$\begingroup\$ @DavidArenburg This is just the human-readable form. All tokens (int(, sum(, Ans, etc.) occupy only one byte. \$\endgroup\$
    – Dennis
    Oct 8, 2015 at 1:54
  • 4
    \$\begingroup\$ +1 This is one of the most impressive TI-BASIC golfs I've seen on this site. \$\endgroup\$
    – PhiNotPi
    Oct 8, 2015 at 3:08
  • \$\begingroup\$ Thomas this answer is stunning! \$\endgroup\$
    – DaveAlger
    Oct 8, 2015 at 5:08
  • \$\begingroup\$ Are you sure there's no way to enter the % symbol? I would've thought it could be found in the symbol catalog... Also, I should get out my TI-84+ Silver. I haven't used it in a while. Block Dude is awesome. \$\endgroup\$
    – mbomb007
    Oct 9, 2015 at 18:33
7
\$\begingroup\$

CJam, 25 23 22 bytes

{_:e2\:+f/_:+100-Xb.+}

Thanks to @Sp3000 for 25 → 24.

Try it online.

How it works

_                   e# Push a copy of the input.
 :e2                e# Apply e2 to each integer, i.e., multiply by 100.
    \               e# Swap the result with the original.
     :+             e# Add all integers from input.
       f/           e# Divide the product by the sum. (integer division)
        _:+         e# Push the sum of copy.
           100-     e# Subtract 100. Let's call the result d.
               Xb   e# Convert to base 1, i.e., push an array of |d| 1's.
                 .+ e# Vectorized sum; increment the first |d| integers.
\$\endgroup\$
0
6
\$\begingroup\$

J (8.04 beta), 59 bytes (30 stolen bytes)

30 byte literal J-port of Dennis's APL answer:

    f=.3 :'+/\^:_1<.100*(+/\%+/)y'

    f 1 1 2 4
12 13 25 50

59 bytes answer, best I could do myself:

f=.3 :0
p=.<.100*y%+/y
r=.100-+/p
p+((r$1),(#p-r)$0)/:\:p
)

(Based on the remainder having to go to the highest values, no more than +1 each, split over multiple values in the case of a remainder > 1 or a tie for highest value).

e.g.

   f 1 0 2
33 0 67

   f 1000 1000
50 50

   f 1 1 2 4
12 12 25 51

   f 0 0 0 5 0
0 0 0 100 0

   f 16 16 16 16 16 16
17 17 17 17 16 16

   f 0 100 5 0 7 1
0 89 4 0 7 0

Explanation

  • f=.3 : 0 - 'f' is a variable, which is a verb type (3), defined below (:0):
  • p=. variable 'p', built from:
    • y is a list of numbers 1 0 2
    • +/y is '+' put between each value '/', the sum of the list 3
    • y % (+/y) is original y values divided by the sum: 0.333333 0 0.666667
    • 100 * (y%+/y) is 100x those values: 33.33.. 0 0.66... to get the percentages.
    • <. (100*y%+/y) is the floor operator applied to the percentages: 33 0 66
  • r=. variable 'r', built from:
    • +/p is the sum of the floored percentages: 99
    • 100 - (+/p) is 100 - the sum, or the remaining percentage points needed to make the percentages sum to 100.
  • result, not stored:
    • r $ 1 is a list of 1s, as long as the number of items we need to increment: 1 [1 1 ..]
    • #p is the length of the percentage list
    • (#p - r) is the count of items that won't be incremented
    • (#p-r) $ 0 is a list of 0s as long as that count: 0 0 [0 ..]
    • ((r$1) , (#p-r)$0) is the 1s list followed by the 0s list: 1 0 0
    • \: p is a list of indexes to take from p to put it in descending order.
    • /: (\:p) is a list of indexes to take from \:p to put that in ascending order
    • ((r$1),(#p-r)$0)/:\:p is taking the elements from the 1 1 .. 0 0 .. mask list and sorting so there are 1s in the positions of the biggest percentages, one for each number we need to increment, and 0s for other numbers: 0 0 1.
    • p + ((r$1),(#p-r)$0)/:\:p is the percentages + the mask, to make the result list which sums to 100%, which is the function return value.

e.g.

33 0 66 sums to 99
100 - 99 = 1
1x1 , (3-1)x0 = 1, 0 0
sorted mask   = 0 0 1

33 0 66
 0 0  1
-------
33 0 67

and

  • ) end of definition.

I'm not very experienced with J; I wouldn't be too surprised if there's a "turn list into percentages of the total" operation built in, and a cleaner way to "increment n biggest values" too. (This is 11 bytes less than my first attempt).

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Very cool. I have a python solution but it's a lot longer than this one. Nice work! \$\endgroup\$
    – DaveAlger
    Oct 8, 2015 at 0:30
  • 1
    \$\begingroup\$ If you haven't noticed, the rules have changed, so you should be able to shorten this considerably. \$\endgroup\$
    – lirtosiast
    Oct 8, 2015 at 1:31
  • \$\begingroup\$ @DaveAlger thanks! @ThomasKwa I noticed, I'm not sure it helps me considerably - first attempt I can get -2 characters. I would need to change the list[0:100-n] + list[:-100-n] approach - and I haven't thought of another way to approach it. \$\endgroup\$ Oct 8, 2015 at 1:41
5
\$\begingroup\$

Mathematica, 41 bytes

(s=Floor[100#/Tr@#];s[[;;100-Tr@s]]++;s)&
\$\endgroup\$
2
  • \$\begingroup\$ Wait, what happens here? \$\endgroup\$
    – seequ
    Oct 8, 2015 at 16:06
  • \$\begingroup\$ @Seeq The algorithm is like the old code in the TI-BASIC answer. It calculates all floored percents, then adds 1 to the first N elements, where N is the percentage left over. \$\endgroup\$
    – alephalpha
    Oct 8, 2015 at 16:16
5
\$\begingroup\$

Jelly, 7 bytes

-2 thanks to Dennis, reminding me to use another new feature (Ä) and using : instead of what I initially had.

ŻÄ׳:SI

Try it online!

Jelly, 11 bytes

0;+\÷S×ȷ2ḞI

Try it online!

Done alongside caird coinheringaahing and user202729 in chat.

How it works

0;+\÷S×ȷ2ḞI - Full program.

0;          - Prepend a 0.
  +\        - Cumulative sum.
    ÷S      - Divided by the sum of the input.
      ×ȷ2   - Times 100. Replaced by ׳ in the monadic link version.
         ḞI - Floor each, compute the increments (deltas, differences).
\$\endgroup\$
0
4
\$\begingroup\$

JavaScript (ES6), 81 bytes

a=>(e=0,a.map(c=>((e+=(f=c/a.reduce((c,d)=>c+d)*100)%1),f+(e>.999?(e--,1):0)|0)))

That "must equal 100" condition (rather than rounding and adding up) nearly doubled my code (from 44 to 81). The trick was to add an pot for decimal values that, once it reaches 1, takes 1 from itself and adds it to the current number. Problem then was floating points, which means something like [1,1,1] leaves a remainder of .9999999999999858. So I changed the check to be greater than .999, and decided to call that precise enough.

\$\endgroup\$
4
\$\begingroup\$

Haskell, 42 27 bytes

p a=[div(100*x)$sum a|x<-a]

Pretty much the trivial method in Haskell, with a few spaces removed for golfing.

Console (brackets included to be consistent with example):

*Main> p([1,0,2])
[33,0,66]
*Main> p([1000,1000])
[50,50]
*Main> p([1,1,2,4])
[12,12,25,50]
*Main> p([0,0,0,5,0])
[0,0,0,100,0]

Edit: practised my putting, made some obvious replacements.

Original:

p xs=[div(x*100)tot|x<-xs]where tot=sum xs
\$\endgroup\$
1
  • 1
    \$\begingroup\$ The sum of the list should be 100. In your first example, it is 99 \$\endgroup\$
    – Damien
    Jan 12, 2016 at 12:01
3
\$\begingroup\$

Haskell, 63 56 55 bytes

p l=tail>>=zipWith(-)$[100*x`div`sum l|x<-0:scanl1(+)l]
\$\endgroup\$
3
\$\begingroup\$

Perl, 42 bytes

Based on Dennis's algorithm

Includes +1 for -p

Run with the list of numbers on STDIN, e.g.

perl -p percent.pl <<< "1 0 2"

percent.pl:

s%\d+%-$-+($-=$a+=$&*100/eval y/ /+/r)%eg
\$\endgroup\$
3
\$\begingroup\$

Brain-Flak, 150 bytes

((([]){[{}]({}<>)<>([])}{})[()])<>([]){{}<>([{}()]({}<([()])>)<>(((((({})({})({})){}){}){}{}){}){}(<()>))<>{(({}<({}())>)){({}[()])<>}{}}{}([])}<>{}{}

Try it online!

Starting from the end and working backward, this code ensures at each step that the sum of the output numbers so far is equal to the total percentage encountered, rounded down.

(

  # Compute and push sum of numbers
  (([]){[{}]({}<>)<>([])}{})

# And push sum-1 above it (simulating a zero result from the mod function)
[()])

<>

# While elements remain
([]){{}

  # Finish computation of modulo from previous step
  <>([{}()]({}

    # Push -1 below sum (initial value of quotient in divmod)
    <([()])>

  # Add to 100*current number, and push zero below it
  )<>(((((({})({})({})){}){}){}{}){}){}(<()>))

  # Compute divmod
  <>{(({}<({}())>)){({}[()])<>}{}}{}

([])}

# Move to result stack and remove values left over from mod
<>{}{}
\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6) 60 63 95

Adapted and simplified from my (wrong) answer to another challenge
Thk to @l4m2 for discovering that this was wrong too

Fixed saving 1 byte (and 2 byte less, not counting the name F=)

v=>v.map(x=>(x=r+x*100,r=x%f,x/f|0),f=eval(v.join`+`),r=f/2)

Test running the snippet below in any EcmaScript 6 compliant browser

F=
v=>v.map(x=>(x=r+x*100,r=x%f,x/f|0),f=eval(v.join`+`),r=f/2)

console.log('[1,0,2] (exp [33,0,67] [34,0,66])-> '+F([1,0,2]))
console.log('[1000,1000] (exp [50,50])-> '+F([1000,1000]))
console.log('[1,1,2,4] (exp[12,12,25,51] [13,12,25,50] [12,13,25,50] [12,12,26,50])-> '+F([1,1,2,4]))
console.log('[0,0,0,5,0] (exp [0,0,0,100,0])-> '+F([0,0,0,5,0]))
console.log('[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,980] -> '+F([1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,980]))
console.log('[2,2,2,2,2,3] -> ' + F([2,2,2,2,2,3]))
<pre id=O></pre>

\$\endgroup\$
5
  • \$\begingroup\$ Failed on [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,980] \$\endgroup\$
    – l4m2
    May 18, 2018 at 17:19
  • \$\begingroup\$ @l4m2 failed why? The sum is 100 and any single resulting integer returned as a percentage is off by no more than 1 in either direction. \$\endgroup\$
    – edc65
    May 19, 2018 at 8:09
  • \$\begingroup\$ The last one should be at most one off by 98, but it's 100 \$\endgroup\$
    – l4m2
    May 19, 2018 at 13:42
  • \$\begingroup\$ @l4m2 uh, right, thanks.Time to think again \$\endgroup\$
    – edc65
    May 19, 2018 at 19:34
  • \$\begingroup\$ @l4m2 should be fixed now \$\endgroup\$
    – edc65
    May 19, 2018 at 20:02
3
\$\begingroup\$

Husk, 14 bytes

Ẋ-Θmȯ⌊*100/Σ¹∫

Try it online! or Verify all test cases

Algorithm from Dennis' answer.

Explanation

Ẋ-Θmȯ⌊*100/Σ¹∫
             ∫ cumulative sums
   mȯ          map to the follwing 4 functions
          /Σ¹  divide by sum of input
      *100     times 100
     ⌊         floored
  Θ            prepend a zero
Ẋ-             fold consecutive pairs with subtraction
\$\endgroup\$
1
  • 1
    \$\begingroup\$ @KevinCruijssen think it's correct now. \$\endgroup\$
    – Razetime
    Oct 7, 2020 at 7:43
2
\$\begingroup\$

Octave, 40 bytes

@(x)diff(ceil([0,cumsum(100*x/sum(x))]))
\$\endgroup\$
2
\$\begingroup\$

Python 2, 89 bytes

def f(L):
 p=[int(x/0.01/sum(L))for x in L]
 for i in range(100-sum(p)):p[i]+=1
 return p

print f([16,16,16,16,16,16])
print f([1,0,2])

->

[17, 17, 17, 17, 16, 16]
[34, 0, 66]
\$\endgroup\$
2
\$\begingroup\$

JavaScript, 48 bytes

F=

x=>x.map(t=>s+=t,y=s=0).map(t=>-y+(y=100*t/s|0))

// Test 
console.log=x=>O.innerHTML+=x+'\n';


console.log('[1,0,2] (exp [33,0,67] [34,0,66])-> '+F([1,0,2]))
console.log('[1000,1000] (exp [50,50])-> '+F([1000,1000]))
console.log('[1,1,2,4] (exp[12,12,25,51] [13,12,25,50] [12,13,25,50] [12,12,26,50])-> '+F([1,1,2,4]))
console.log('[0,0,0,5,0] (exp [0,0,0,100,0])-> '+F([0,0,0,5,0]))
<pre id=O></pre>

\$\endgroup\$
2
\$\begingroup\$

05AB1E, 9 bytes

.¥IO/т*ï¥

Try it online!

+3 for a bugfix

\$\endgroup\$
2
  • \$\begingroup\$ You can remove the leading D, because input will be used implicitly. \$\endgroup\$ Oct 7, 2020 at 6:56
  • 1
    \$\begingroup\$ Although I'm not 100% sure it's valid. The challenge states percentages can be off by 1, but must always sum to 100. But an input like [1,1,1] would result in [33,33,33]. Although I'm pretty sure halve the other answers are incorrect for similar reasons. Here a straight-forward fix at the cost of 3 bytes. \$\endgroup\$ Oct 7, 2020 at 6:58
2
\$\begingroup\$

Vyxal, 12 bytes

∑/₁*ṙ:∑₁$-Þ…

Try it Online!

Explained

∑/₁*ṙ:∑₁$-Þ…
∑             # sum(input)
 /            # input ÷ ↑         # get the weight of each number
  ₁*          # ↑ * 100           # and make it a percentage
    ṙ         # map(round, ↑)     # rounding each number
     :∑       # ↑, sum(↑)         # now sum the above
       ₁$-    # 100 - ↑           # and subtract from 100. The result represents any potential round errors that need correction
          Þ…  # distribute(↑, ↑↑) # spread ↑ over the rounded list evenly
\$\endgroup\$
1
\$\begingroup\$

Rust, 85 bytes

This uses vectors instead of arrays because as far as I am aware there is no way to accept arrays of multiple different lengths.

let a=|c:Vec<_>|c.iter().map(|m|m*100/c.iter().fold(0,|a,x|a+x)).collect::<Vec<_>>();
\$\endgroup\$
1
\$\begingroup\$

Japt v2.0a0, 13 bytes

å+ mzUx÷L)änT

Try it

\$\endgroup\$
0
\$\begingroup\$

Jq 1.5, 46 bytes

add as$s|.[1:]|map(100*./$s|floor)|[100-add]+.

Expanded

  add as $s               # compute sum of array elements
| .[1:]                   # \ compute percentage for all elements 
| map(100*./$s|floor)     # / after the first element
| [100-add] + .           # compute first element as remaining percentage

Try it online!

\$\endgroup\$
0
\$\begingroup\$

PHP, 82 bytes

for(;++$i<$argc-1;$s+=$x)echo$x=$argv[$i]/array_sum($argv)*100+.5|0,_;echo 100-$s;

takes input from command line arguments, prints percentages delimited by underscore.

Run with -nr or try it online.

\$\endgroup\$
4
  • \$\begingroup\$ This outputs 15_15_15_15_15_25 when given the input [2,2,2,2,3], which isn't right because 3/13 ~= 23.1% \$\endgroup\$ May 18, 2018 at 17:17
  • \$\begingroup\$ @SophiaLechner Which of the answers does that correctly? \$\endgroup\$
    – Titus
    May 18, 2018 at 18:02
  • \$\begingroup\$ Most do, actually. The correct answers so far seem to be built around one of two algorithms; the first rounds off the percentages of cumulative sums and takes the difference; the second calculates the floors of the percentages and then increments enough distinct percentages to bring the total to 100. \$\endgroup\$ May 18, 2018 at 19:09
  • \$\begingroup\$ @SophiaLechner I didn´t mean I wouldn´t look into it; but I´ll do later. Thanks for noticing. \$\endgroup\$
    – Titus
    May 18, 2018 at 19:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.