Cannot figure out why my code will not output the correct results of the itertools.combinations_with_replacement if for certain small values.
from itertools import combinations_with_replacement
menu = []
with open("menu.txt") as f:
for line in f:
budget = float(line.split("$")[-1]) # extract the budget
break
for line in f:
itemName = line.split(",")[0]
itemPrice = float(line.split("$")[-1])
menu.append([itemName,itemPrice])
def shorten_list(menu): # function to filter out items where price > budget
i=0;
for item in menu:
if item[-1] > budget:
del menu[i]
i = i + 1
return menu
shorten_list(menu) #call to shorten_list function
for item in menu:
item[-1] = int(item[-1]*100) # cast to int to avoid floating point imprecision errors
budget = int(budget *100) # cast to int to avoid floating point imprecision errors
flag = 0 # set a flag = 0 to check if solutions will be found
num_comb = 1
comb = [c for i in range(len(menu)+1) for c in combinations_with_replacement(menu, i)] # outputs iterator with all possible combinations
print("\n")
for e in comb:
if sum(l[1] for l in e) == budget: # filters out only the combinations that == our budget
print ("Combination_with_R number " + str(num_comb) + " is:")
print ([l[0] for l in e]) # print only the item name
print ("\n")
num_comb += 1
flag = 1 # if an solutions found we set flag = 1
if flag == 0: # if no solutions found, flag = 0 has not changed
print ("There is no combination of dishes that will equal your budget... Leave the change as tip! \n\n ")
The problem that I am having with the code is mostly when I need a combination to repeat a certain menu item to create a meal. For example if we have the menu item bread,$1.00 and the budget = 18
there should be a combination ['bread', 'bread','bread','bread'..... n=18]
so essentially 18 breads. Or if the item is ketchup_packet,$0.10 and budget = 18
there should also be a combination of ['ketchup_packet',............ n = 180]
. Assume that menu.txt
is in this format:
$18.00
mixed fruit,$2.15
french fries,$2.75
side salad,$3.35
hot wings,$3.55
mozzarella sticks,$4.20
sampler plate,$5.80
pasta3,$5.05
salad,$3.25
pasta10,$10.10
pasta1,$2.65
TESTER,$1.20
For some reason with this menu.txt it won't output a combination of ['TESTER', 'TESTER',..... N =15]
But if the menu.txt
is:
$12.00
mixed fruit,$2.15
french fries,$2.75
side salad,$3.35
hot wings,$3.55
mozzarella sticks,$4.20
sampler plate,$5.80
pasta3,$5.05
salad,$3.25
pasta10,$10.10
pasta1,$2.65
TESTER,$1.20
It will correctly output all combinations including ['TESTER','TESTER',..... n = 12]
It should also work with
$12.00
mixed fruit,$2.15
french fries,$2.75
side salad,$3.35
hot wings,$3.55
mozzarella sticks,$4.20
sampler plate,$5.80
pasta3,$5.05
salad,$3.25
pasta10,$10.10
pasta1,$2.65
TESTER,$0.01
But does not! Cannot understand why.
I cleaned up the code formatting, factored out a bunch of utility functions, and converted it to a linear programming problem. See what you think:
from decimal import Decimal
def get_name(s):
return s.split(',')[0]
def get_price(s):
return Decimal(s.split('$')[-1])
def get_menu(fname):
with open(fname) as inf:
budget = get_price(inf.next())
items = [(get_name(line), get_price(line)) for line in inf]
return budget, items
def integer_linear_solver(coefficients, total, index=None):
"""
Given coefficients [c0, c1, ... cN] and total,
generate all integer solutions to the equation
s0*c0 + s1*c1 + ... + sN*cN == total
and return as [s0, s1, ... sN]
"""
if index is None:
# Start at the end and work back
# (this avoids having to repeatedly slice coefficients)
index = len(coefficients) - 1
c = coefficients[index]
max_s = total // c
if index: # more coefficients available - recurse
for s in range(max_s + 1): # [0 .. max_s]
for sol in integer_linear_solver(coefficients, total - s*c, index-1):
yield sol + [s]
else: # last coefficient
if not(total % c):
# no remainder -> exact solution found
yield [max_s]
def print_sol(coeffs, labels):
items = ('{0} {1}'.format(c, l) for c,l in zip(coeffs, labels) if c > 0)
print(', '.join(items))
def main():
budget,items = get_menu('menu.txt')
names,prices = zip(*items)
solutions = 0
for sol in integer_linear_solver(prices, budget):
print_sol(sol, names)
solutions += 1
if solutions:
print('{} solutions found'.format(solutions))
else:
print("There is no combination of dishes that will equal your budget.")
if __name__=="__main__":
main()
Run against your first example menu, it gives
2 side salad, 2 hot wings, 1 mozzarella sticks
2 french fries, 2 side salad, 1 sampler plate
1 mixed fruit, 3 side salad, 1 sampler plate
...
1 mixed fruit, 1 pasta1, 11 TESTER
15 TESTER
109 solutions found