2
\$\begingroup\$

The data I'm using is summoning rates from a gacha game, One Piece Treasure Cruise. The game provides the probability of getting a certain character in percents rounded to the nearest thousandth. However, the data does not sum to 100%, so I want to find the original fractions used to calculate those decimals.

I've programmed a brute force approach to find these ratios. It iterates through potential numerators for each sub-category of data. If the results match all given in-game output, it gets displayed. The problem is that it takes a long time to run, so I need help optimizing it. I'm certain that there are better ways to do what I'm attempting.

In the game, characters in this particular dataset are divided into three rarity categories: 5 Star, 4 Star, and 3 Star. Each character also has one of six types (STR, DEX, QCK, PSY, or INT). Within the 5 Star and 4 Star categories, there are 4 subgroups, each with different probabilities. I added some comments to clarify parts of the code.

double round5places(double input);

int main() {

double given5rate = 0.07089; // The in-game rate for summoning a 5 star char
double given4rate = 0.72911;
double given3rate = 0.2;

double givenSTR = 0.19934; // The in-game rate for summoning a STR char
double givenDEX = 0.13355;
double givenQCK = 0.25456;
double givenPSY = 0.2124;
double givenINT = 0.20014;

double denom = 1;  // The denominator of the fractions (iterates to 1,000,000)

double given5_1 = 0.00182; // The in-game rate for a sub-group of the 5 star characters
double cat5_1 = 0; // The category's numerator that will be iterated
double num5_1 = 1; // The number of characters in this subset

double given5_2 = 0.00016;
double cat5_2 = 0;
double num5_2 = 12;

double given5_3 = 0.00222;
double cat5_3 = 0;
double num5_3 = 5;

double given5_4 = 0.00043;
double cat5_4 = 0;
double num5_4 = 129;

double given4_1 = 0.01818;
double cat4_1 = 0;
double num4_1 = 1;

double given4_2 = 0.00156;
double cat4_2 = 0;
double num4_2 = 11;

double given4_3 = 0.02218;
double cat4_3 = 0;
double num4_3 = 5;

double given4_4 = 0.00435;
double cat4_4 = 0;
double num4_4 = 134;

double given3_1 = 0.02222;
double cat3_1 = 0;
double num3_1 = 9;

double sum5 = 0;
double sum4 = 0;
double sum3 = 0;

double sumSTR = 0;
double sumDEX = 0;
double sumQCK = 0;
double sumPSY = 0;
double sumINT = 0;

for (denom = 1; denom <= 1000000; ++denom) {
    for (cat5_1 = 1; cat5_1 < denom; ++cat5_1) {
        if (given5_1 == round5places(cat5_1 / denom)) {              
        // If the fraction for the first sub-category of 5 stars matches the posted in-game rate, start working on the next sub-category
            for (cat5_2 = 1; cat5_2 < denom - cat5_1; ++cat5_2) {
                if (given5_2 == round5places(cat5_2 / denom)) {
                    for (cat5_3 = 1; cat5_3 < denom - cat5_1 - cat5_2; ++cat5_3) {
                        if (given5_3 == round5places(cat5_3 / denom)) {
                            for (cat5_4 = 1; cat5_4 < denom - cat5_1 - cat5_2 - cat5_3; ++cat5_4) {
                                if (given5_4 == round5places(cat5_4 / denom)) {
                                    sum5 = num5_1 * (cat5_1 / denom) + num5_2 * (cat5_2 / denom) + num5_3 * (cat5_3 / denom) + num5_4 * (cat5_4 / denom);
                                    if (given5rate == round5places(sum5)) {
                                        for (cat4_1 = 1; cat4_1 < denom - cat5_1 - cat5_2 - cat5_3 - cat5_4; ++cat4_1) {
                                            if (given4_1 == round5places(cat4_1 / denom)) {
                                                for (cat4_2 = 1; cat4_2 < denom - cat5_1 - cat5_2 - cat5_3 - cat5_4 - cat4_1; ++cat4_2) {
                                                    if (given4_2 == round5places(cat4_2 / denom)) {
                                                        for (cat4_3 = 1; cat4_3 < denom - cat5_1 - cat5_2 - cat5_3 - cat5_4 - cat4_1 - cat4_2; ++cat4_3) {
                                                            if (given4_3 == round5places(cat4_3 / denom)) {
                                                                for (cat4_4 = 1; cat4_4 < denom - cat5_1 - cat5_2 - cat5_3 - cat5_4 - cat4_1 - cat4_2 - cat4_3; ++cat4_4) {
                                                                    if (given4_4 == round5places(cat4_4 / denom)) {
                                                                        sum4 = num4_1 * (cat4_1 / denom) + num4_2 * (cat4_2 / denom) + num4_3 * (cat4_3 / denom) + num4_4 * (cat4_4 / denom);
                                                                        if (given4rate == round5places(sum4)) {
                                                                            for (cat3_1 = 1; cat3_1 < denom - cat5_1 - cat5_2 - cat5_3 - cat5_4 - cat4_1 - cat4_2 - cat4_3 - cat4_4; ++cat3_1) {
                                                                                if (given3_1 == round5places(cat3_1 / denom)) {
                                                                                    sum3 = num3_1 * (cat3_1 / denom);
                                                                                    if (given3rate == round5places(sum3)) {
                                                                                        if ((sum5 + sum4 + sum3) == 1.0) {
                                                                                            sumSTR = 1.0 * (cat3_1 / denom) + 3.0 * (cat4_2 / denom) + 37.0 * (cat4_4 / denom) + 4.0 * (cat5_2 / denom) + 35.0 * (cat5_4 / denom);
                                                                                            if (givenSTR == round5places(sumSTR)) {
                                                                                                sumDEX = 1.0 * (cat3_1 / denom) + 1.0 * (cat4_2 / denom) + 23.0 * (cat4_4 / denom) + 1.0 * (cat5_2 / denom) + 23.0 * (cat5_4 / denom);
                                                                                                if (givenDEX == round5places(sumDEX)) {
                                                                                                    sumQCK = 2.0 * (cat3_1 / denom) + 2.0 * (cat4_2 / denom) + 29.0 * (cat4_4 / denom) + 2.0 * (cat4_3 / denom) + 1.0 * (cat4_1 / denom) + 2.0 * (cat5_2 / denom) + 26.0 * (cat5_4 / denom) + 2.0 * (cat5_3 / denom) + 1.0 * (cat5_1 / denom);
                                                                                                    if (givenQCK == round5places(sumQCK)) {
                                                                                                        sumPSY = 3.0 * (cat3_1 / denom) + 1.0 * (cat4_2 / denom) + 24.0 * (cat4_4 / denom) + 1.0 * (cat4_3 / denom) + 1.0 * (cat5_2 / denom) + 25.0 * (cat5_4 / denom) + 1.0 * (cat5_3 / denom);
                                                                                                        if (givenPSY == round5places(sumPSY)) {
                                                                                                            sumINT = 2.0 * (cat3_1 / denom) + 4.0 * (cat4_2 / denom) + 21.0 * (cat4_4 / denom) + 2.0 * (cat4_3 / denom) + 4.0 * (cat5_2 / denom) + 20.0 * (cat5_4 / denom) + 2.0 * (cat5_3 / denom);
                                                                                                            if (givenINT == round5places(sumINT)) {
                                                                                                                std::cout << "Denominator: " << denom << "\n5-1: " << cat5_1 << "\n5-2: " << cat5_2 << "\n5-3: " << cat5_3 << "\n5-4: " << cat5_4 << "\n4-1: " << cat4_1 << "\n4-2: " << cat4_2 << "\n4-3: " << cat4_3 << "\n4-4: " << cat4_4 << "\n3-1: " << cat3_1;
                                                                                                            }                                                                                                               
                                                                                                        }                                                                                                           
                                                                                                    }                                                                                                           
                                                                                                }
                                                                                            }
                                                                                        }
                                                                                    }
                                                                                }
                                                                            }
                                                                        }
                                                                    }
                                                                }
                                                            }
                                                        }
                                                    }
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

return 0;

}

double round5places(double input) {
    return (round(input * 100000.0) / 100000.0);
}

If something is unclear, please let me know. Thanks in advance for your help!

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

If I'm not mistaken, the question stated in the title isn't the question you ask in your post's body. Finding the nearest rational approximation of a double-precision number is one thing, mirroring the character selection of a game another.

As to the first one, a fairly good answer is based on the Farey sequence, which will converge quicker than brute-force in most cases. It works on numbers between 0 and 1, thus it is well adapted to probabilities. Here's a fairly basic adaptation:

struct Farey_fraction {
    unsigned numerator, denominator;
    Farey_fraction(unsigned n, unsigned d) : numerator(n), denominator(d) {}
    operator double() const { return numerator / static_cast<double>(denominator); }
};

Farey_fraction mediant(Farey_fraction lhs, const Farey_fraction& rhs) {
    return Farey_fraction(lhs.numerator + rhs.numerator, lhs.denominator + rhs.denominator);
}

Farey_fraction nearest_rational(double target, std::size_t maximum_denominator) {
    Farey_fraction min{0, 1}, max{1, 1};
    // unless you can find a rational representation of the target
    // return the neighboring fraction with the greatest allowed denominator
    while (min.denominator <= maximum_denominator && max.denominator <= maximum_denominator) {
        auto guess = mediant(min, max);
        if (guess == target) {
            if (min.denominator + max.denominator <= maximum_denominator) return guess;
            else if (max.denominator > min.denominator) return max;
            else return min;
        }
        // update the bounds to converge
        else if (target > guess) min = guess;
        else                     max = guess;
    }
    if (min.denominator > maximum_denominator) return max;
    return min;
}

Once you have solved this problem, you have a quite direct solution to the second one: you only need to distribute the difference between 1 and the sum of the rational approximations between the approximations to reconstitute the 100% total. There's a little bit of work here, since you might have to simplify fractions. I you use C++17 you can rely on std::gcd to make the task easier.

Now onto your code

  1. constants should be const. To the very least; you can constexpr them also (for instance: constexpr double given5rate = 0.07089;. It expresses your intent better, and will trigger a compilation error if you modify it by mistake.

  2. nested loops and nested if-clauses often are a sign of bad code, especially when there are so many layers. They're very difficult to read and debug, not only because the variables' states are difficult to follow, but even very simply because lines will overflow unless you have a very wide screen. Moreover, they generally aren't the most efficient solution -or if they are, the problem can't be solved quickly, because nested loops are by essence slow.

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