3
1
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
You can only add to the population. You cannot take any away from the starting population.
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.
You have a pool of unlimited Alices and Bobs that are not in the population yet.
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
You can only add to the population. You cannot take any away from the starting population.
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.
You have a pool of unlimited Alices and Bobs that are not in the population yet.
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.
3I 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 [tag:fastest-code] around here :) That said, I'd definitely add some more test cases that you will use to test the speed. – Nathan Merrill – 2016-03-03T18:18:30.890
I'm guessing he didn't put test cases because the same input can have multiple valid outputs – Charlie Wynn – 2016-03-03T18:29:42.273
2Will the percentages always be integers? – Alex A. – 2016-03-03T18:34:42.623
9The amount of computation needed to solve this is too low for a fastest-code question. The time to solve won't be measurable. – feersum – 2016-03-03T18:48:23.833
1Also, 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 – Charlie Wynn – 2016-03-03T19:14:19.220
Sorry for the unclear instructions guys. I'll use the sandbox next time. Yes, I will use multiple iterations to test the timing of the approach. You can specify the framework you would like me to run your code under. I added more clarification to the question details. – Mike Clark – 2016-03-03T20:03:19.080
@MikeClark Does the solution need to be the minimal solution, or any solution that works? – Mr Public – 2016-03-04T13:07:27.207
1@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. – Mike Clark – 2016-03-04T22:16:19.960
Is there another version of this question with the minimal-solution requirement? – Peter Cordes – 2016-12-17T19:03:07.153