chic-fil-a.py

import copy

fullmenu = {
    "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,
}

visited_solutions = set()

# collate items by price
menu_by_price = {
    price: {"price": price, "items": set()} for price in fullmenu.values()
}  # make unique by price
for item, price in fullmenu.items():
    menu_by_price[price]["items"].add(item)

collated_menu = {}
for price, info in menu_by_price.iteritems():
    item_name = next(iter(info["items"]))
    collated_menu[item_name] = info

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 not solutions:
        return
    single_solution = solutions.pop()
    assert single_solution

    total_price = sum([menu[item]["price"] for item in single_solution])
    if total_price == PRICE_TARGET_ROUNDED:
        solution_strings = [
            "%s ($%.2f)" % ("/".join(menu[i]["items"]), menu[i]["price"])
            for i in single_solution
        ]
        print(", ".join(solution_strings))
    elif (
        sum([menu[x]["price"] for x in single_solution]) < PRICE_TARGET_ROUNDED
    ):
        for item in menu:
            # make a new, unique solution unique
            new_solution = sorted((item,) + copy.deepcopy(single_solution))
            new_solution = tuple(new_solution)
            if new_solution in visited_solutions:
                continue
            visited_solutions.add(new_solution)
            solutions.add(new_solution)
            DFS_helper(menu, solutions)


def DFS(menu):
    solutions = set()
    for item in menu:
        assert item
        solutions.add((item,))
        DFS_helper(menu, solutions)


DFS(collated_menu)