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()

• Justin Chang: I'm fairly sure get_max_score does not have 1 global maximum. Consider x = 6; either do 6 pennies or 3 pennies and 1 dime. The code above seems to run >5x faster than my previous answer - I'm quite impressed with what you've done with it.
• ayaan098: @JustinChang Thanks! Your first point is a good point, I think a better phrasing would be that get_max_score either has one global maximum, or it has several local maximums with equivalent values (so once we've found a local maximum, we've found the final solution). Of course this is just speculation based on plotting the values and graphing in Desmos.
• Justin Chang: I stand corrected - I'm fairly sure the function is not concave either. Unfortunately exploring all the local maxima is likely required because we must have integer solutions.
• ayaan098: @JustinChang Do you think there might be any way to speed up the get_max_dollars function? It seems like the simplest function to optimize, and it feels like there should be a faster algorithm to find the optimal value than looping over all possible values.
• Justin Chang: You could probably compute the optimum real solution and then test the values rounding up / down.

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()