3
\$\begingroup\$

Introduction

Say you have a population of people. This population is made up of 100 Alices and 25 Bobs. So, 80% of the population are Alices and 20% are Bobs. We want to change the proportional makeup of the population to be 62% Alices and 38% Bobs.

Rules

  1. You can only add to the population. You cannot take any away from the starting population.

  2. You can only add in multiples of the original subpopulation size. So following the above example, you can only add batches of 100 Alices to the group; likewise, you can only add batches of 25 Bobs to the group.

  3. You have a pool of unlimited Alices and Bobs that are not in the population yet.

  4. The algorithm must be able to handle N different name groups (e.g. N=4: Alice, Bob, Carol, David).

Pseudocode framework

# 100 Alices, 25 Bobs, 35 Carols, 60 Davids
starting_population = (100, 25, 35, 60)

# Goal percentages, must sum to 100
reproportion_goal = (10, 20, 30, 40)

# Reproportion the population to meet the goal percentages, following the rules
new_population = reproportion_population(starting_population, reproportion_goal)

Winner

Create an algorithm to re-proportion the population following the rules with an arbitrary starting_population and reproportion_goal.

The winning algorithm will solve the above-quoted problem in the fastest time on a single-core single-CPU i686 system with fixed clock speed. The algorithm must also solve other reasonable cases through the same code-path. That is, do not special-case for the example data.

I will use many thousands of iterations to test the timing of the approach. VM/runtime startup times will not be counted. The algorithm will be warmed up before timing starts. You can specify the specific version of framework you would like me to run your code under, and if I can reasonably set it up, I will.

Introduction

Say you have a population of people. This population is made up of 100 Alices and 25 Bobs. So, 80% of the population are Alices and 20% are Bobs. We want to change the proportional makeup of the population to be 62% Alices and 38% Bobs.

Rules

  1. You can only add to the population. You cannot take any away from the starting population.

  2. You can only add in multiples of the original subpopulation size. So following the above example, you can only add batches of 100 Alices to the group; likewise, you can only add batches of 25 Bobs to the group.

  3. You have a pool of unlimited Alices and Bobs that are not in the population yet.

  4. The algorithm must be able to handle N different name groups (e.g. N=4: Alice, Bob, Carol, David).

Pseudocode framework

# 100 Alices, 25 Bobs, 35 Carols, 60 Davids
starting_population = (100, 25, 35, 60)

# Goal percentages, must sum to 100
reproportion_goal = (10, 20, 30, 40)

# Reproportion the population to meet the goal percentages, following the rules
new_population = reproportion_population(starting_population, reproportion_goal)

Winner

Create an algorithm to re-proportion the population following the rules with an arbitrary starting_population and reproportion_goal.

The winning algorithm will solve the above-quoted problem in the fastest time on a single-core single-CPU i686 system with fixed clock speed. The algorithm must also solve other reasonable cases through the same code-path. That is, do not special-case for the example data.

I will use many thousands of iterations to test the timing of the approach. VM/runtime startup times will not be counted. The algorithm will be warmed up before timing starts. You can specify the specific version of framework you would like me to run your code under, and if I can reasonably set it up, I will.

Dates (deadline and winner)

Deadline for submissions is before March 14, 2016. I will post benchmarks by March 20. Feel free to answer after these dates, but I can't commit to re-benchmarking submissions after March 14.

\$\endgroup\$
  • 3
    \$\begingroup\$ I have no idea why you are getting close votes. This challenge (even in its revision history) is quite clear in my opinion, and its nice to see a fastest-code around here :) That said, I'd definitely add some more test cases that you will use to test the speed. \$\endgroup\$ – Nathan Merrill Mar 3 '16 at 18:18
  • 2
    \$\begingroup\$ Will the percentages always be integers? \$\endgroup\$ – Alex A. Mar 3 '16 at 18:34
  • 9
    \$\begingroup\$ The amount of computation needed to solve this is too low for a fastest-code question. The time to solve won't be measurable. \$\endgroup\$ – feersum Mar 3 '16 at 18:48
  • 1
    \$\begingroup\$ Also, will he download compiliers for each language submitted? Install nodejs to ensure there's less overhead than a browser? He could run 1000 cases per language to get a measurable timeframe \$\endgroup\$ – Charlie Wynn Mar 3 '16 at 19:14
  • 1
    \$\begingroup\$ @MrPublic I wanted the minimal solution, but I forgot to specify that. Being a newbie, I didn't know about the sandbox! I left the question as is: any solution is valid, since it is bad manners to change the rules after the question has been posted. \$\endgroup\$ – Mike Clark Mar 4 '16 at 22:16
7
\$\begingroup\$

C

void reproportion(
        const unsigned int n,
        const unsigned int *const starting_population,
        const unsigned int *const reproportion_goal,
        unsigned int *const new_population)
{
    unsigned int unit = 1U;

    for(unsigned int i = 0U; i != n; ++i) {
        unit *= starting_population[i];
    }

    for(unsigned int i = 0U; i != n; ++i) {
        new_population[i] = reproportion_goal[i] * unit;
    }
}

This assumes that the original subpopulation sizes are greater than zero. starting_population = { 0, 1, 2 } and reproportion_goal = { 0, 50, 50 } would give the incorrect result of new_population = { 0, 0, 0 }. If the original subpopulation size can be zero, unit *= starting_population[i]; should be preceded by if(starting_population[i] != 0U).

Call this function from within your program like so:

#include <stdio.h>

int main(void)
{
    unsigned int starting_population[] = { 1, 2, 31, 4 };
    unsigned int reproportion_goal[] = { 25, 25, 40, 10 };
    unsigned int new_population[4];

    reproportion(4, starting_population, reproportion_goal, new_population);

    for(int i = 0; i < 4; ++i) {
        printf("%d ", new_population[i]);
    }
}
\$\endgroup\$
  • 2
    \$\begingroup\$ Welcome to Programming Puzzles & Code Golf! This is a nice first answer. :) \$\endgroup\$ – Alex A. Mar 3 '16 at 19:29
  • \$\begingroup\$ With large N, this should vectorize well with SIMD. (e.g. x86 SSE / AVX). In that case, you'd actually get faster results from float than from 32-bit integers, since vector-integer 32-bit multiply requires SSE4.1, but vector-float multiply only requires SSE1. vector-int _mm_mullo_epi32 also has worse performance than _mm_mul_ps. (See agner.org/optimize) \$\endgroup\$ – Peter Cordes Dec 17 '16 at 18:57
1
\$\begingroup\$

Javascript ES6

I'm not really sure how you time these things but here's what I have

(p,g)=>g.map(_=>_*m,m=p.reduce((l,o)=>o*l))

the instinct to use

(p,g)=>g.map(_=>_*p.reduce((l,o)=>o*l))

to save a few bytes is overwhelming, but I suspect js isn't smart enough to reuse the p.reduce for each iteration

[I know this gives back larger than necessary solutions, but I don't think that a minimal solution was a requirement :) ]

Usage

f=(p,g)=>g.map(_=>_*m,m=p.reduce((l,o)=>o*l))


f([100, 25],[62, 38])
//outputs [155000, 95000]
//sum of those is 250000

//155000/250000 = 0.62

f([100, 25, 35, 60] ,[10, 20, 30, 40])
//outputs [52500000, 105000000, 157500000, 210000000]
//sum of those is 525000000
\$\endgroup\$
  • \$\begingroup\$ Indeed, I didn't ask for the minimal solution and perhaps I should have. But I'm going to leave it as I wrote it. I didn't make it clear, but the algorithm needs to generalize to N subpopulations. For 3 subpopulations, would you do (p,g,t)=>g.map(_=>_*p.reduce((l,o,m)=>o*l*m))? \$\endgroup\$ – Mike Clark Mar 3 '16 at 18:19
  • \$\begingroup\$ I'm expecting p to be an array of current population, and g to be an array of desired percentages, so it should work for any pop size :) I'll add usage to my answer \$\endgroup\$ – Charlie Wynn Mar 3 '16 at 18:20
  • \$\begingroup\$ I am unfamiliar with some of these ES6 lambda and mapping constructs, so usage would be appreciated. Thanks! \$\endgroup\$ – Mike Clark Mar 3 '16 at 18:21
  • \$\begingroup\$ For a fastest-code competition I like non-efficient answers. Like how for smallest-code terribly inefficient algorithms often win :) \$\endgroup\$ – Charlie Wynn Mar 3 '16 at 18:23
  • 2
    \$\begingroup\$ In real life, this can be expanded (probably already has been) to draw the boundaries of election districts. Make one district 100% alice and the others 49% alice and 51% bob; bob wins all of the districts but one, with fewer voters in all. \$\endgroup\$ – Glenn Randers-Pehrson Mar 3 '16 at 22:48
1
\$\begingroup\$

Matlab

This function is very fast, but doesn't return the minimal solution

function s=reproportion_population(a,T)
s=prod(lcm(a,T)).*T;

This version returns the minimal solution.

function s=reproportion_population(a,T)
L=lcm(a,T);
g=prod(L)./a;
r=g(1);
rt=T(1);
for i=1:numel(g)-1
    r=gcd(r,g(i+1));
    rt=gcd(rt,T(i+1));
end
s=g./r.*a.*T/rt;

Usage is, for both versions, new_population = reproportion_population(starting_population, reproportion_goal), for example,

reproportion_population([100 25],[62 38])

which returns [182590000 111910000] (first version) or [3100 1900] (second version), or

reproportion_population([100 25 35 60],[10 20 30 40])

which returns [2520000000 5040000000 7560000000 10080000000] (first version) [2100 4200 6300 8400] (second version).

If you don't have Matlab, it should work as-is in Octave, although you need to need to add endfunction at the end of the file (I think---I don't have Octave).

\$\endgroup\$
1
\$\begingroup\$

Rust

To change the cases, simply change the numbers in the vectors (if you want commandline arguments instead, I can do that). On my computer I ran

time for i in {1..1000}; do target/release/population > /dev/null; done;

and got the output

real    0m4.202s
user    0m0.748s
sys 0m3.613s

I'm not sure how much actual optimization there is to be done, and how much will even show because its so fast.

fn reproportion_population( starting_population:&Vec<usize>, reproportion_goal: &Vec<usize> ) -> Vec<usize> {

    let mut prod: usize = 1;
    let mut size: usize = 0;


    for i in starting_population {
        size +=1;
        prod *= *i;
    }

    let mut answers: Vec<usize> = vec![0; size];

    for i in 0..size {
        answers[i] = reproportion_goal[i]*prod;
    }

    answers

}


fn main() {
    let starting_population: Vec<usize> = vec![100, 25, 35, 60,100];

    let reproportion_goal: Vec<usize> = vec![10,20,30,30,10];

    let answers: Vec<usize> = reproportion_population(&starting_population, &reproportion_goal);


    /*
    // the following prints out POPULATION: PERCENT with a newline for each pop.
    // the percent is given as a decimal. 

    let mut total: usize = 0;
    for i in 0..reproportion_goal.len() {
        total += answers[i];
    }
    for i in 0..reproportion_goal.len() {
        println!("{}: {}", answers[i], (answers[i] as f64)/(total as f64));
    }
    */

}

To compile (after rust+cargo are installed) run cargo build --release. To run ./target/release/<binary_name>.

\$\endgroup\$
1
\$\begingroup\$

Python

Assuming that any valid solution is acceptable, and not the minimal solution...

def reproportion_pop(start_pop, pop_goal):
 import operator
 reduced = reduce(operator.mul, start_pop)
 new_pop = []
 for x in range(len(start_pop)):
  new_pop.append(reduced*pop_goal[x])
 return new_pop

This can be put in a .py file, pasted into an interpreter, or run Here, whichever you prefer.

Function call is in the form of reproportion_pop(list_of_start_pop, list_of_pop_goal)

Examples:

> reproportion_pop([100,25],[62,38])
[155000, 95000]

> reproportion_pop([100,25,35,60],[10,20,30,40])
[52500000, 105000000, 157500000, 210000000]
\$\endgroup\$

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.