Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <array>
- #include <cstdio>
- #include <cmath>
- std::array<int,4> stars_bars(std::array<int,4> parts, int stars, int bars);
- void print_parts(std::array<int,4> parts);
- int slice_sum(int start, int delta, std::array<int,26> freqs);
- int score(std::array<int,4>);
- std::array<int,26> freqs = {16, 4, 17, 10, 15, 4, 4, 6, 7, 14, 9, 17, 27, 6, 1, 9, 0, 12, 20, 8, 0, 3, 4, 0, 3, 4};
- int main(int argc, char* argv[]){
- std::array<int,4> parts;
- parts.fill(0);
- //std::cout << slice_sum(4, 6, freqs);
- //std::array<int,4> test = {26, 0, 0, 0};
- print_parts(stars_bars(parts, 26, 4));
- return 0;
- }
- void print_parts(std::array<int,4> parts){
- for (int i = 0; i < 4; i++){
- std::cout << parts[i] << " ";
- }
- std::cout << std::endl;
- }
- int score(std::array<int,4> parts){
- int score = 0;
- int place = 0;
- for(int i = 0; i < 4; i++){
- score += abs(slice_sum(place, parts[i], freqs) - 55);
- place += parts[i];
- }
- return score;
- }
- int slice_sum(int start, int delta, std::array<int,26> freqs){
- int sum = 0;
- for(int i = 0; i < delta; i++){
- sum += freqs[i + start];
- }
- return sum;
- }
- /* our recursion function */
- std::array<int,4> stars_bars(std::array<int,4> parts, int stars, int bars){
- //declare these static
- //so they persist in spite of recursion
- static int min_score = 330;
- static std::array<int,4> min_volumes = {26,0,0,0};
- /* exit case 1, last bar. */
- //std::cout << stars << "\t" << bars << std::endl;
- if (bars == 1) {
- parts[0] = stars;
- int sc = score(parts);
- if (sc <= min_score){
- //print_parts(parts);
- min_score = sc;
- min_volumes = parts;
- }
- return min_volumes;
- }
- // /* exit case 2, no more stars. */
- // if (stars == 0){
- // //std::cout << "exit 2" << std::endl;
- // //fill the remaining cells with 0
- // for(int i = 1; i < bars; i++) {
- // parts[i] = 0;
- // }
- // print_parts(parts);
- // return parts;
- // }
- //main case
- for(int i = 0; i <= stars; i++) {
- //std::cout << "main case" << std::endl;;
- parts[bars-1] = i;
- stars_bars(parts, stars-i, bars-1);
- }
- //print_parts(min_volumes);
- return min_volumes;
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement