Calculate optimal game upgrades, v2

Question

This is the second iteration of the code I originally posted here: Calculate optimal game upgrades. Based on the feedback there, I chose to change the code to use a dynamic programming approach with memoization. I also made some general improvements to the code. I'm looking for ways to increase the performance of the code further, as well as general code improvements. I think the get_max_dollars function can be improved, since there's a trivial closed form solution for the case where dollars and gold can be real numbers, although I'm not sure how to apply that knowledge to make the function faster.

(Note: I chose not to use the heuristic solution from @user286929 just because I would like the code to find the provably optimal solution. )

(Note 2: A few people were confused about the strange choice of costs and bonus formula in my last question, the upgrade costs and bonuses are just from a random idle game. )

'''
This program calculates the optimal number of upgrades to purchase
given a certain number of points to spend on upgrades

Upgrades cost:
    - pennies:  1
    - dimes:    3
    - dollars:  6
    - gold:    15

The upgrade bonus can be calculated as:
    pennies + pennies * dimes + pennies * dimes * dollars 
        + pennies * dimes * dollars * gold
or alternatively:
    pennies * (1 + dimes * (1 + dollars * (1 + gold)))
'''

from functools import cache
import time

'''
Input: points is the number of points to spend on pennies, dimes, dollars, and gold combined
Output: returns a nested tuple containing 
    ((pennies, dimes, dollars, gold), total bonus)
'''
def get_max_score(points):
    last_max_score = -1
    last_max_combo = (0, 0, 0, 0)
    # we decrement by 3 instead of 1, because the cost of all 
    # upgrades other than pennies is a multiple of 3.
    # Therefore, the number of upgrades other than pennies that
    # we can buy only changes every 3 pennies.
    for pennies in range(points, -1, -3):
        points_left = points - pennies
        dimes, dollars, gold = get_max_dimes(points_left)
        score = pennies * (1 + dimes * (1 + dollars * (1 + gold)))
        if score >= last_max_score:
            last_max_combo = (pennies, dimes, dollars, gold)
            last_max_score = score
        else:
            # It seems like this function has one global maximum
            # although I haven't proved this
            pass # break
    return last_max_combo, last_max_score

'''
Input: points is the number of points to spend on dimes, dollars, and gold combined
Output: returns a tuple containing 
    (dimes, dollars, gold)
'''
@cache
def get_max_dimes(points):
    # the cost of dimes, dollars, and gold are all divisible by 3
    # hence, the max number of coins with x points will be the same 
    # as the max number of coins with y points, where y is x rounded 
    # to the nearest multiple of 3
    point_remainder = points % 3
    if point_remainder != 0:
        return get_max_dimes(points - point_remainder)
    max_dimes = points // 3
    last_max_score = -1
    last_max_combo = (0, 0, 0)
    for dimes in range(max_dimes, -1, -1):
        points_left = points - dimes * 3
        dollars, gold = get_max_dollars(points_left)
        partial_score = dimes * (1 + dollars * (1 + gold))
        if partial_score >= last_max_score:
            last_max_combo = (dimes, dollars, gold)
            last_max_score = partial_score
    return last_max_combo

'''
Input: points is the number of points to spend on dollars and gold combined
Output: returns a tuple containing 
    (dollars, gold)
'''
@cache
def get_max_dollars(points):
    max_dollars = points // 6
    last_max_score = -1
    last_max_combo = (0, 0)
    for dollars in range(max_dollars, -1, -1):
        points_left = points - dollars * 6
        gold = points_left // 15
        partial_score = dollars * (1 + gold)
        if partial_score >= last_max_score:
            last_max_combo = (dollars, gold)
            last_max_score = partial_score
    return last_max_combo
    

while True:
    start_points = int(input("Start points: "))
    end_points = input("End points (leave blank for single value): ")
    if end_points == '':
        end_points = start_points
    end_points = int(end_points)
    if end_points < start_points:
        start_points, end_points = end_points, start_points
    
    print()
    
    time_start = time.perf_counter()
    
    for y in range(end_points, start_points - 1, -1):
        combo = get_max_score(y)
        print(f"score: {y}, {combo}")
    
    time_end = time.perf_counter()
    
    print(f"\nComputation took {time_end - time_start:.5f}s")
    if input("\nRun again? [y]/[n] ") != "y":
        break
    print()

Answer 1

Performance Improvements

---

Reduced Complexity for get_max_dollars

Currently this tries all possible dollars from max dollars down to 0, this is O(points / 6) in the worst case. A better approach is to invert the logic and iterate over gold instead, since gold changes the floor division pattern more "slowly". This turns the complexity into O(points / 15), which is about a factor of 2.5 improvement in iteration count and often faster in practice.

Improving get_max_dimes

This function is O(points / 3) complexity. If you want to speed it up further, you could consider a similar approach: iterate directly and store the best result. Since you know dimes increments by 1, you can't trivially jump around as you did with dollars and gold, but you can at least rely on the faster get_max_dollars.

If performance is still an issue, consider precomputing get_max_dollars results for all points once, since this is now simple and O(points) for the entire range is feasible. For larger ranges, a one-time pre-computation is often faster than repeatedly calling the function without caching.

Micro-Optimizations

• Remove redundant checks: If you believe the minimum is unimodal (once score starts decreasing, it won't go back up), you could break out of loops early. But only do this if you're sure of the mathematical property.
• Inline computations: Instead of calling multiple functions, directly compute partial scores inline. Function call overhead in Python can be significant.

Code Suggestions

This:

• Uses a bottom-up pre-computation approach for get_max_dollars and get_max_dimes before answering queries.
• Eliminates repeated calls by storing best combinations in arrays.
• Improves get_max_dollars complexity by iterating over gold instead of dollars.
• Speeds up get_max_dimes by looking up precomputed get_max_dollars results in O(1).

import time

def precompute_max_dollars(max_points):
    """
    Precompute the best (dollars, gold) combination for every point value up to max_points.
    For each points value:
      - Iterate over possible gold values
      - Compute the maximum dollars possible
      - Keep track of the combination that yields the highest score dollars*(1+gold).
    Store results in a list for O(1) lookup.
    """
    best_dg = [None] * (max_points + 1)
    for p in range(max_points + 1):
        best_score = -1
        best_combo = (0, 0)
        max_gold = p // 15
        for gold in range(max_gold + 1):
            dollars = (p - 15 * gold) // 6
            # dollars should never be negative if gold <= max_gold
            score = dollars * (1 + gold)
            if score > best_score:
                best_score = score
                best_combo = (dollars, gold)
        best_dg[p] = best_combo
    return best_dg

def precompute_max_dimes(max_points, dollars_gold_best):
    """
    Precompute the best (dimes, dollars, gold) combination for every point value up to max_points.
    Use the precomputed dollars_gold_best for O(1) lookup of the best (dollars, gold).
    """
    best_ddg = [None] * (max_points + 1)
    for p in range(max_points + 1):
        # Round down p to nearest multiple of 3 since costs for these upgrades are multiples of 3
        # If p is not a multiple of 3, just look up p' = p - remainder.
        # But it's simpler to just use a loop from max down to 0.
        max_dimes = p // 3
        best_score = -1
        best_combo = (0, 0, 0)
        for d in range(max_dimes + 1):
            points_left = p - d * 3
            (dol, g) = dollars_gold_best[points_left]
            score = d * (1 + dol * (1 + g))
            if score > best_score:
                best_score = score
                best_combo = (d, dol, g)
        best_ddg[p] = best_combo
    return best_ddg

def get_max_score(points, dimes_dollars_gold_best):
    """
    Compute the best (pennies, dimes, dollars, gold, total_score) for a given point value.
    Since we haven't precomputed pennies (which cost 1), we still do a loop over pennies.
    But this loop is now relatively cheaper compared to previous nested loops.
    """
    last_max_score = -1
    last_max_combo = (0, 0, 0, 0)
    # Iterate over pennies in steps of 3, as original reasoning suggests:
    # if you prefer, you can iterate from 0 to points and still be fine, it's just slightly slower.
    # But we keep it consistent.
    for pennies in range(points, -1, -3):
        points_left = points - pennies
        (dimes, dollars, gold) = dimes_dollars_gold_best[points_left]
        score = pennies * (1 + dimes * (1 + dollars * (1 + gold)))
        if score > last_max_score:
            last_max_score = score
            last_max_combo = (pennies, dimes, dollars, gold)
        else:
            # If you're confident it's unimodal, you could break here.
            # But without proof, we leave it as is.
            pass
    return last_max_combo, last_max_score


if __name__ == "__main__":
    while True:
        start_points = int(input("Start points: "))
        end_points = input("End points (leave blank for single value): ")
        if end_points == '':
            end_points = start_points
        end_points = int(end_points)
        if end_points < start_points:
            start_points, end_points = end_points, start_points

        # Precompute only once for the maximum needed range
        max_points = end_points

        print("\nPrecomputing best combinations...")
        time_precompute_start = time.perf_counter()

        # Precompute best (dollars, gold) for all points
        dollars_gold_best = precompute_max_dollars(max_points)
        # Precompute best (dimes, dollars, gold) for all points
        dimes_dollars_gold_best = precompute_max_dimes(max_points, dollars_gold_best)

        time_precompute_end = time.perf_counter()
        print(f"Precomputation took {time_precompute_end - time_precompute_start:.5f}s")

        print("\nCalculating results:")
        time_start = time.perf_counter()

        for y in range(end_points, start_points - 1, -1):
            combo = get_max_score(y, dimes_dollars_gold_best)
            print(f"score: {y}, {combo}")

        time_end = time.perf_counter()
        print(f"\nComputation took {time_end - time_start:.5f}s")

        if input("\nRun again? [y]/[n] ") != "y":
            break
        print()