Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <assert.h>
- #include <algorithm>
- #include <array>
- #include <iostream>
- #include <optional>
- #include <memory>
- #include <vector>
- // Indexed by level difference.
- std::array<unsigned, 5> BaseRates = { 100, 50, 25, 10, 1 };
- std::array<unsigned, 5> BonusRates = { 0, 16, 8, 3, 0 };
- // How many 0* materials are required to go from level N to level N+1.
- // For example, going from 0* to 1* requires exactly one 0* material.
- std::array<double, 5> MatsRequired = { 1.0, -1.0, -1.0, -1.0, -1.0 };
- // How many 0* items is an N* item equivalent to. For example, a 0*
- // item is equivalent to 1 0* items. A 1* item is equivalent to 2
- // 0* items (one for the base 0*, one to upgrade it). This is easy
- // to compute. The "value" of an N* item is equal to the value of an
- // (N-1)* item plus the number of materials required to go from N->N+1
- std::array<double, 6> MatValue = { 1.0, -1.0, -1.0, -1.0, -1.0 };
- struct MaterialNode;
- struct OutcomeNode {
- explicit OutcomeNode(const MaterialNode &Parent, bool Success);
- double matsRequired() const;
- // How did we get here?
- const MaterialNode &Parent;
- const MaterialNode *cheapestMaterial() const;
- // Whether this node represents a successful attmept or a failed attempt.
- bool Success = false;
- // From this outcome, what materials did we try? Empty if and only if
- // Success == true.
- std::vector<std::unique_ptr<MaterialNode>> MaterialsTried;
- };
- struct MaterialNode {
- explicit MaterialNode(unsigned BaseStars, unsigned InitialFailureBonus = 0);
- explicit MaterialNode(OutcomeNode &Parent, unsigned Stars, unsigned FailureBonus);
- const MaterialNode &root() const;
- unsigned maxMaterial() const;
- double matsRequired() const;
- unsigned successRate() const;
- unsigned accumulatedFailure() const;
- unsigned materialDifference() const;
- // How did we get here?
- OutcomeNode *Parent = nullptr;
- // The star value (0 - 5) of the material used in this attempt.
- unsigned Stars = 0;
- // The sequential number of the attempt this node represents.
- unsigned Attempt = 0;
- // The current failure bonus when this material was used.
- unsigned FailureBonus = 0;
- // The independent probability that we will succeed on this attempt.
- unsigned N_Succ = 0;
- std::optional<double> InfiniteIncrementalCost;
- std::unique_ptr<OutcomeNode> Success;
- std::unique_ptr<OutcomeNode> Failure;
- };
- OutcomeNode::OutcomeNode(const MaterialNode &Parent, bool Success)
- : Parent(Parent), Success(Success) {
- // If this was a success, we don't need to do anything. There's no reason to
- // try any more materials.
- if (Success)
- return;
- const MaterialNode &Root = Parent.root();
- unsigned Diff = Root.Stars - Parent.Stars;
- unsigned MaxMaterial = Parent.maxMaterial();
- for (unsigned M = 0; M <= MaxMaterial; ++M) {
- unsigned B = BonusRates[Diff];
- unsigned NewFailureBonus = std::min(100U, Parent.FailureBonus + B);
- auto Mat = std::make_unique<MaterialNode>(*this, M, NewFailureBonus);
- MaterialsTried.push_back(std::move(Mat));
- }
- }
- const MaterialNode *OutcomeNode::cheapestMaterial() const {
- const MaterialNode *MC = nullptr;
- for (const auto &M : MaterialsTried) {
- if (!MC || M->matsRequired() < MC->matsRequired())
- MC = M.get();
- }
- return MC;
- }
- double OutcomeNode::matsRequired() const {
- if (MaterialsTried.empty())
- return 0.0;
- return cheapestMaterial()->matsRequired();
- }
- MaterialNode::MaterialNode(unsigned BaseStars, unsigned InitialFailureBonus)
- : Stars(BaseStars), Attempt(0), FailureBonus(InitialFailureBonus) {
- // This is just a dummy node to represent the root. Consider this a "failure" node
- // so that it's consistent with only descending into failures.
- Failure = std::make_unique<OutcomeNode>(*this, false);
- }
- MaterialNode::MaterialNode(OutcomeNode &Parent, unsigned Stars, unsigned FailureBonus)
- : Parent(&Parent), Stars(Stars), Attempt(Parent.Parent.Attempt + 1), FailureBonus(FailureBonus) {
- assert(Stars <= Parent.Parent.maxMaterial());
- assert(Stars < root().Stars);
- unsigned Difference = root().Stars - Stars;
- N_Succ = BaseRates[Difference];
- N_Succ = std::min(100U, N_Succ + FailureBonus);
- if (Difference >= 4) {
- // When the difference is too large, there is no failure bonus, so we can't keep recursing
- // through branches of the decision tree because it would be infinite. Instead, we have to
- // use some calculus this explicitly. Specifically, we have the following variables:
- //
- // N - the cost of materials we've used up until this point.
- // P - The base success rate with this material + any accumulated failure bonus
- //
- // With these, we have an infinite set of attempts where the absolute chance of succeeding
- // on attempt k is P*(1-P)^k, where k=0 represents the first attempt where Difference >= 4
- // and ignores any attempts that came prior.
- //
- // Furthermore, if the k'th attempt is the attempt that succeeds, then we would have used
- // k additional materials, all 0* so a cost of 1, for a total cost of N+k, and since this
- // would happen with probability P*(1-P)^k the effective cost of this branch of the tree
- // would be:
- //
- // (N+k)*P*(1-P)^k
- //
- // Thus, we can get the sum of all branches by computing the limit of this sum as K approaches
- // infinity.
- //
- // ∑[k=0, ∞] (N+k)*P*(1-P)^k
- //
- // I leave it as an exercise to the reader that this is equal to N + 1/P - 1, which means
- // that the *incremental* cost from taking this branch is simply equal to 1/P - 1.
- double D_Succ = static_cast<double>(N_Succ) / 100.0;
- InfiniteIncrementalCost = 1.0 / D_Succ - 1.0;
- // Since we're mathematically solving the entire problem henceforth, just say it has a success
- // rate of 100%, and set a special variable indicating the solved answer.
- N_Succ = 100;
- } else {
- Success = std::make_unique<OutcomeNode>(*this, true);
- if (N_Succ < 100U) {
- Failure = std::make_unique<OutcomeNode>(*this, false);
- }
- }
- }
- const MaterialNode &MaterialNode::root() const {
- return (Parent) ? Parent->Parent.root() : *this;
- }
- unsigned MaterialNode::maxMaterial() const {
- return (Parent) ? Stars : Stars - 1;
- }
- double MaterialNode::matsRequired() const {
- double M = 0.0;
- if (Parent)
- M = MatValue[Stars];
- if (InfiniteIncrementalCost.has_value()) {
- // If this is an infinite branch, just add in the computed cost and
- // exit.
- return M + *InfiniteIncrementalCost;
- }
- double P_Succ = static_cast<double>(N_Succ) / 100.0;
- double P_Fail = 1.0 - P_Succ;
- if (Success)
- M += P_Succ * Success->matsRequired();
- if (Failure)
- M += P_Fail * Failure->matsRequired();
- return M;
- }
- unsigned MaterialNode::materialDifference() const {
- return root().Stars - Stars;
- }
- unsigned MaterialNode::successRate() const {
- return BaseRates[materialDifference()];
- }
- unsigned MaterialNode::accumulatedFailure() const {
- unsigned N = 0;
- if (Parent)
- N += Parent->Parent.FailureBonus;
- return N;
- }
- std::array<std::unique_ptr<MaterialNode>, 5> Roots;
- int main()
- {
- for (unsigned I = 0; I < 5; ++I) {
- double M = 1.0;
- if (I > 0) {
- Roots[I] = std::make_unique<MaterialNode>(I);
- M = Roots[I]->matsRequired();
- }
- std::cout << I << "* -> " << (I + 1) << "* : " << M << " 0* item required." << std::endl;
- MatsRequired[I] = M;
- MatValue[I + 1] = MatValue[I] + MatsRequired[I];
- }
- for (unsigned I = 2; I < 5; ++I) {
- for (unsigned FB = 0; FB < 100; ++FB) {
- Roots[I] = std::make_unique<MaterialNode>(I, FB);
- const MaterialNode *Cheapest = Roots[I]->Failure->cheapestMaterial();
- std::cout << I << "*, FB = " << FB << ": Use " << Cheapest->Stars << "* material.\n";
- }
- }
- unsigned Base = 0;
- while (true) {
- std::cout << "Enter a base material star value: ";
- std::cin >> Base;
- if (Base < 5)
- break;
- std::cout << "Cannot upgrade any item which is 5* or higher" << std::endl;
- }
- const MaterialNode *R = Roots[Base].get();
- bool Finished = false;
- double Cost = 0.0;
- double Bonus = 0.0;
- unsigned F = 0;
- std::cout << "Upgrading " << R->Stars << "* base item" << std::endl;
- while (!Finished) {
- std::cout << "Analyzing choices..." << std::endl;
- for (const auto &X : R->Failure->MaterialsTried) {
- std::cout << X->Stars << "* material -> Cost = " << X->matsRequired() << std::endl;
- }
- R = R->Failure->cheapestMaterial();
- F += R->FailureBonus;
- std::cout << "Failure Bonus = " << F << "%" << std::endl;
- std::cout << "Selecting " << R->Stars << "* material" << std::endl;
- unsigned S = R->successRate();
- std::cout << "Attempt " << R->Attempt << "[" << (S + F) << "%]: " << S << "% + " << F << "%" << std::endl;
- std::cout << "Did this attempt (S)ucceed or (F)ail? Or do you want to go (B)ack?";
- char CH;
- std::cin >> CH;
- CH = toupper(CH);
- assert(CH == 'S' || CH == 'F' || CH == 'B');
- if (CH == 'B') {
- F -= R->FailureBonus;
- R = &R->Parent->Parent;
- Cost -= MatsRequired[R->Stars];
- continue;
- }
- Cost += MatsRequired[R->Stars];
- Bonus += static_cast<double>(R->FailureBonus) / 100.0;
- if (CH == 'S') {
- std::cout << "Done! Steps = " << R->Attempt << ", Total material cost = " << Cost << std::endl;
- break;
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement