Reproportioning a population by adding fixed sized groups

Question

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.

Answer 1

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]);
    }
}

Answer 2

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

Answer 3

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).

Answer 4

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]

Answer 5

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>.