chic-fil-a.py

import copy

menu = {"4 chick-n-minis": 3.35,
        "egg white grill": 3.79,
        "bacon/sausage egg cheese biscuit": 2.95,
        "buttered biscuit": 0.99,
        "sunflower multigrain bagel": 1.95,
        "hash browns": 1.15,
        "greek yogurt parfait": 3.35,
        "fruit cup": 3.09,
        "chicken egg cheese bagel": 3.79,
        "hash brown scramble burrito/bowl": 3.85,
        "bacon, egg cheese muffin": 3.15,
        "chicken biscuit": 2.49,
        "chicken sandwich": 3.69,
        "deluxe sandwich": 4.29,
        "spicy chicken sandwich": 3.99,
        "spicy deluxe sandwich": 4.59,
        "grilled chicken sandwich": 4.99,
        "grilled chicken club sandwich": 6.35,
        "nuggets": 3.75,
        "chicken strips": 4.09,
        "grilled chicken cool wrap": 5.99,
        "grilled nuggets": 4.49,
        "spicy southwest salad": 8.25,
        "cobb salad": 8.25,
        "market salad": 8.25,
        "waffle fries": 1.85,
        "side salad": 3.25,
        "chicken noodle soup": 2.99,
        "superfood side": 2.99,
        "buddy's apple sauce": 1.89,
        "nuggets kids meal": 4.95,
        "chicken strips kids meal": 4.85,
        "grilled nuggets kids meal": 5.49,
        "frosted lemonade/coffee/sunrise/milkshake": 3.39,
        "icedream cone": 1.35,
        "chocolate chunk cookie": 1.29,
        "peach milkshake": 3.69,
        "lemonade": 1.99,
        "ice tea/soda/bottled water": 1.75,
        "apple juice": 1.35,
        "orange juice": 2.45,
        "chocolate milk/milk": 1.35,
        "coffee": 1.79,
        "iced coffee": 2.65,
        "gallon beverage": 5.75,
        "white peach tea lemonade": 2.05
        }

TARGET = 6.66
SALES_TAX = 0.05
PRICE_TARGET_UNROUNDED = TARGET / (1 + SALES_TAX) 
PRICE_TARGET_ROUNDED = PRICE_TARGET_UNROUNDED - (PRICE_TARGET_UNROUNDED % 0.01)

def DFS_helper(menu, solutions):
    if len(solutions) == 0:
        return
    single_solution = solutions.pop()
    if sum([menu[x] for x in single_solution]) == PRICE_TARGET_ROUNDED:
        print single_solution
    elif sum([menu[x] for x in single_solution]) < PRICE_TARGET_ROUNDED:
        for item in menu:
            new_solution = copy.deepcopy(single_solution)
            new_solution.append(item)
            solutions.append(new_solution)
            DFS_helper(menu, solutions)

def DFS(menu):
    solutions = []
    for item in menu:
        solutions.append([item])
        DFS_helper(menu, solutions)

DFS(menu)

Thanks for this, nice use of DFS.

I've made some updates to your script on my fork. It outputs:

deluxe sandwich ($4.29), white peach tea lemonade ($2.05)
bacon/sausage egg cheese biscuit ($2.95), frosted lemonade/coffee/sunrise/milkshake ($3.39)
chocolate chunk cookie ($1.29), hash browns ($1.15), sunflower multigrain bagel ($1.95), sunflower multigrain bagel ($1.95)
buttered biscuit ($0.99), chocolate milk/milk/icedream cone/apple juice ($1.35), sunflower multigrain bagel ($1.95), white peach tea lemonade ($2.05)
hash browns ($1.15), hash browns ($1.15), lemonade ($1.99), white peach tea lemonade ($2.05)
chocolate milk/milk/icedream cone/apple juice ($1.35), hash browns ($1.15), lemonade ($1.99), waffle fries ($1.85)
buddy's apple sauce ($1.89), chocolate milk/milk/icedream cone/apple juice ($1.35), chocolate milk/milk/icedream cone/apple juice ($1.35), ice tea/soda/bottled water ($1.75)
chocolate chunk cookie ($1.29), hash browns ($1.15), waffle fries ($1.85), white peach tea lemonade ($2.05)
buttered biscuit ($0.99), hash browns ($1.15), ice tea/soda/bottled water ($1.75), orange juice ($2.45)
chicken biscuit ($2.49), chocolate milk/milk/icedream cone/apple juice ($1.35), chocolate milk/milk/icedream cone/apple juice ($1.35), hash browns ($1.15)
chocolate milk/milk/icedream cone/apple juice ($1.35), coffee ($1.79), hash browns ($1.15), white peach tea lemonade ($2.05)
grilled nuggets ($4.49), waffle fries ($1.85)
chocolate chunk cookie ($1.29), chocolate milk/milk/icedream cone/apple juice ($1.35), waffle fries ($1.85), waffle fries ($1.85)
iced coffee ($2.65), peach milkshake/chicken sandwich ($3.69)
ice tea/soda/bottled water ($1.75), spicy deluxe sandwich ($4.59)
buttered biscuit ($0.99), chocolate milk/milk/icedream cone/apple juice ($1.35), chocolate milk/milk/icedream cone/apple juice ($1.35), iced coffee ($2.65)
buttered biscuit ($0.99), ice tea/soda/bottled water ($1.75), ice tea/soda/bottled water ($1.75), waffle fries ($1.85)
4 chick-n-minis/greek yogurt parfait ($3.35), superfood side/chicken noodle soup ($2.99)
chicken biscuit ($2.49), hash brown scramble burrito/bowl ($3.85)
chocolate milk/milk/icedream cone/apple juice ($1.35), chocolate milk/milk/icedream cone/apple juice ($1.35), coffee ($1.79), waffle fries ($1.85)
fruit cup ($3.09), side salad ($3.25)
chocolate milk/milk/icedream cone/apple juice ($1.35), grilled chicken sandwich ($4.99)