21
\$\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]
p([1,1,2,4])    ->  [12,12,25,51] or [13,12,25,50] or [12,13,25,50] 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\$
  • \$\begingroup\$ Must our algorithm be deterministic? Must it always terminate within a bounded time? \$\endgroup\$ – lirtosiast Oct 8 '15 at 0:40
  • \$\begingroup\$ We already had some rounding problem similar but more general \$\endgroup\$ – edc65 Oct 10 '15 at 16:11
  • 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\$ – Sophia Lechner May 18 '18 at 17:12
  • 4
    \$\begingroup\$ Can p([1000,1000]) -> [49,51]? \$\endgroup\$ – l4m2 May 18 '18 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 '18 at 8:13

18 Answers 18

20
\$\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\$
  • 9
    \$\begingroup\$ If only Fermat could have taken golf lessons from you. \$\endgroup\$ – TessellatingHeckler Oct 8 '15 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 '15 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\$
  • \$\begingroup\$ Not sure how you counting the bytes here, it looks awfully longer than 23 to me \$\endgroup\$ – David Arenburg Oct 8 '15 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 '15 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 '15 at 3:08
  • \$\begingroup\$ Thomas this answer is stunning! \$\endgroup\$ – DaveAlger Oct 8 '15 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 '15 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\$
5
\$\begingroup\$

Mathematica, 41 bytes

(s=Floor[100#/Tr@#];s[[;;100-Tr@s]]++;s)&
\$\endgroup\$
  • \$\begingroup\$ Wait, what happens here? \$\endgroup\$ – seequ Oct 8 '15 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 '15 at 16:16
5
\$\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\$
  • 1
    \$\begingroup\$ Very cool. I have a python solution but it's a lot longer than this one. Nice work! \$\endgroup\$ – DaveAlger Oct 8 '15 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 '15 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\$ – TessellatingHeckler Oct 8 '15 at 1:41
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
    \$\begingroup\$ The sum of the list should be 100. In your first example, it is 99 \$\endgroup\$ – Damien Jan 12 '16 at 12:01
4
\$\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\$
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\$
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\$

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\$
2
\$\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\$
  • \$\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 '18 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 '18 at 8:09
  • \$\begingroup\$ The last one should be at most one off by 98, but it's 100 \$\endgroup\$ – l4m2 May 19 '18 at 13:42
  • \$\begingroup\$ @l4m2 uh, right, thanks.Time to think again \$\endgroup\$ – edc65 May 19 '18 at 19:34
  • \$\begingroup\$ @l4m2 should be fixed now \$\endgroup\$ – edc65 May 19 '18 at 20:02
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\$

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\$
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\$
  • \$\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\$ – Sophia Lechner May 18 '18 at 17:17
  • \$\begingroup\$ @SophiaLechner Which of the answers does that correctly? \$\endgroup\$ – Titus May 18 '18 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\$ – Sophia Lechner May 18 '18 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 '18 at 19:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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