{{ message }}

Instantly share code, notes, and snippets.

tmcw/sets.md

Created Jun 27, 2020

Here's a sort of unsolved logic/programming problem.

I made this site, Old Fashioned, for cocktail recipes. It has structured data for ingredients and recipes for cocktails. And one of its neat features is that, given certain ingredients, it shows you what's possible or what's nearly possible.

I've been thinking about the opposite angle: from which set of 5 ingredients can you make the highest number of different cocktails? How does one correctly solve this problem.

If formal descriptions are your jam: let's say:

• You have 100 different ingredients
• You have 20 cocktails, each of which use 2-6 ingredients
• Which 5 ingredients maximize the cocktail-making possibilities? What about 10 ingredients?

I think one approach is iterative:

1. Assume you have all ingredients, and can make all cocktails.
2. For each ingredient, count how many cocktails it is included in.
3. Sort the list of ingredients by # of cocktails included in, remove all ingredients with the lowest number of added 'tails'.
4. Recalculate the list of usage patterns, and repeat.

However, this misses what I think might be an important corner: families. Like, there may be a bunch of cocktails that require whiskey, sugar, water, and… and a bunch that include gin, tonic, and…, and this greedy approach will only find one 'family': but ideally I'd be able to split off and efficiently find if there are multiple winners or near-winners.

I'm not obsessed with performance in this case, though a naïve implementation does seem pretty catastrophic, as soon as I start thinking about, for example, finding "all combinations of 5 ingredients", the factorials start looking scary. So the fully naive "compute it all" solution probably isn't the right one.

🤷‍♂️ I'm not sure how to solve this problem! Going to have fun with it, and see if there's a solution, though. Let me know if you have any thoughts!

tmcw commented Jun 27, 2020

 Here's the data from old fashioned, with th erecipe as the first column and the recipes as the following columns in (roughly CSV), based on Data.elm Vodka martini,Vodka,Dry vermouth,Lemon,Olive Mimosa,Champagne,Orange juice,Orange Martini,Gin,Dry vermouth,Lemon Margarita,Tequila,Triple sec,Lime juice,Salt Grasshopper,White crème de cacao,Green crème de menthe,Cream,Mint Ve.n.to,Grappa,Lemon juice,Honey syrup,Chamomile syrup,Honey syrup,Egg white,Lemon,White grape Boulevardier,Bourbon whiskey,Sweet red vermouth,Campari,Orange,Lemon Bee’s nees,London dry gin,Honey syrup,Lemon juice,Orange juice,Orange Southside,London dry gin,Lemon juice,Simple syrup,Mint,Egg white Whiskey sour,Bourbon whiskey,Lemon juice,Simple syrup,Egg white,Cherry,Orange Champagne cocktail,Champagne,Cognac,Angostura bitters,Sugar,Grand Marnier,Orange,Cherry Suffering bastard,Brandy,Gin,Lime juice,Angostura bitters,Ginger beer,Mint,Orange Illegal,Mezcal,Overproof white rum,Lime juice,Falernum,Simple syrup,Maraschino,Egg white Toronto,Canadian whiskey,Fernet Branca,Sugar,Angostura bitters,Orange French 75,Gin,Simple syrup,Lemon juice,Champagne Cuba Libre,Cola,White rum,Lime juice,Lime Moscow mule,Vodka,Ginger beer,Lime juice,Lime Bellini,Prosecco,Peach purée Black russian,Vodka,Coffee liqueur Caipirinha,Cachaça,Lime,Cane sugar Mojito,White rum,Lime juice,Mint,Cane sugar,Lemon,Soda water Dark ’n’ Stormy,Dark rum,Ginger beer,Lime Bramble,Gin,Lemon juice,Simple syrup,Crème de mure,Lemon,Blackberry French martini,Vodka,Raspberry liqueur,Pineapple juice,Lemon Kamikaze,Vodka,Triple sec,Lime juice,Lime Lemon drop martini,Vodka,Triple sec,Lemon juice,Sugar,Lime Vesper,Gin,Vodka,Lillet blanc,Lemon Alexander,Cognac,Brown crème de cacao,Light cream,Nutmeg Americano,Campari,Sweet red vermouth,Soda water,Orange,Lemon Angel face,Gin,Apricot brandy,Calvados Aviation,Gin,Lemon juice,Maraschino,Crème de violette,Cherry Bacardi cocktail,White rum,Lime juice,Grenadine Between the sheets,White rum,Cognac,Triple sec,Lemon juice Casino,Old tom gin,Maraschino,Orange bitters,Lemon juice,Lemon,Cherry Clover club,Gin,Lemon juice,Raspberry syrup,Egg white,Raspberry Daiquiri,White rum,Lemon juice,Simple syrup Derby,Gin,Peach bitters,Mint Dry martini,Gin,Dry vermouth,Lemon,Olive Gin fizz,Gin,Lemon juice,Simple syrup,Soda water,Lemon John collins,Gin,Lemon juice,Simple syrup,Soda water,Angostura bitters,Lemon,Cherry Manhattan,Rye whiskey,Sweet red vermouth,Angostura bitters,Cherry Mary pickford,White rum,Pineapple juice,Grenadine,Maraschino Monkey gland,Gin,Orange juice,Absinthe,Grenadine Negroni,Gin,Sweet red vermouth,Campari,Orange Old fashioned,Whiskey,Angostura bitters,Sugar,Water,Orange,Cherry Paradise,Gin,Apricot brandy,Orange juice Planter’s punch,Dark rum,Orange juice,Pineapple juice,Lemon juice,Grenadine,Simple syrup,Angostura bitters,Cherry,Pineapple Porto flip,Brandy,Port,Egg yolk,Nutmeg Ramos fizz,Gin,Cream,Simple syrup,Lime juice,Lemon juice,Egg white,Orange flower water,Vanilla extract,Soda water Rusty nail,Scotch whiskey,Drambuie,Lemon Sazerac,Cognac,Absinthe,Sugar,Peychaud’s bitters,Lemon Screwdriver,Vodka,Orange juice,Orange Sidecar,Cognac,Triple sec,Lemon juice Stinger,Cognac,White crème de menthe Tuxedo,Old tom gin,Dry vermouth,Maraschino,Absinthe,Orange bitters,Cherry,Lemon White lady,Gin,Triple sec,Lemon juice French connection,Cognac,Amaretto Mint julep,Bourbon whiskey,Mint,Water,Powdered sugar White russian,Vodka,Coffee liqueur,Cream Bloody Mary,Vodka,Tomato juice,Lemon juice,Worcestershire sauce,Tabasco,Celery salt,Pepper,Celery,Lemon Kir,Dry white wine,Crème de cassis Kir royal,Champagne,Crème de cassis Long island iced tea,Vodka,Tequila,White rum,Gin,Cointreau,Lemon juice,Simple syrup,Cola,Lemon Mai-tai,White rum,Dark rum,Curaçao,Orgeat (almond) syrup,Lime juice,Simple syrup,Pineapple,Mint,Lime Tommy’s margarita,Tequila,Lime juice,Agave nectar B52,Coffee liqueur,Triple sec,Irish cream liqueur Barracuda,Gold rum,Galliano,Pineapple juice,Lime juice,Prosecco Corpse reviver #2,Gin,Cointreau,Lillet blanc,Lemon juice,Absinthe,Orange Cosmopolitan,Vodka,Cointreau,Lime juice,Cranberry juice,Lemon Dirty martini,Vodka,Dry vermouth,Olive juice,Olive Espresso martini,Vodka,Coffee liqueur,Simple syrup,Espresso Golden dream,Triple sec,Galliano,Orange juice,Cream Hemingway special,White rum,Grapefruit juice,Maraschino,Lime juice Horse’s neck,Cognac,Ginger ale,Angostura bitters,Lemon Irish coffee,Irish whiskey,Coffee,Cream,Sugar Tom collins,Old tom gin,Lemon juice,Simple syrup,Soda water,Angostura bitters,Lemon,Cherry Pina Colada,White rum,Coconut cream,Pineapple juice,Pineapple,Cherry Pisco Sour,Pisco,Simple syrup,Lemon juice,Egg white,Angostura bitters Russian spring punch,Vodka,Lemon juice,Crème de cassis,Simple syrup,Sparkling wine,Lemon,Blackberry Sea breeze,Vodka,Cranberry juice,Grapefruit juice,Orange,Cherry Sex on the beach,Vodka,Peach schnapps,Orange juice,Cranberry juice,Grapefruit juice,Orange Singapore sling,Gin,Cherry liqueur,Cointreau,DOM Bénédictine,Pineapple juice,Lime juice,Grenadine,Angostura bitters,Cherry,Pineapple Tequila sunrise,Tequila,Orange juice,Grenadine,Orange Yellow bird,White rum,Galliano,Triple sec,Lime juice Zombie,Dark rum,Gold rum,Demerara rum,Lime juice,Falernum,Grapefruit juice,Cinnamon syrup,Grenadine,Angostura bitters,Absinthe,Mint Brandy crusta,Brandy,Lemon juice,Maraschino,Curaçao,Simple syrup,Aromatic bitters,Orange,Powdered sugar Hanky panky,London dry gin,Sweet red vermouth,Fernet Branca,Orange Last word,Gin,Green Chartreuse,Maraschino,Lime juice Martinez,London dry gin,Sweet red vermouth,Maraschino,Orange bitters,Lemon Vieux carré,Rye whiskey,Cognac,Sweet red vermouth,DOM Bénédictine,Peychaud’s bitters,Orange,Cherry Cachanchara,Cuban aguardiente,Lemon juice,Honey,Water,Lime Fernandito,Fernet Branca,Cola Old cuban,Rum,Sparkling wine,Lime juice,Simple syrup,Angostura bitters,Mint Paloma,Tequila,Grapefruit soda,Lime juice,Salt,Lime Paper plane,Bourbon whiskey,Amaro Nonino,Aperol,Lemon juice Penicillin,Blended Scotch whiskey,Islay Single Malt Scotch whiskey,Lemon juice,Honey syrup,Ginger,Candied ginger Spicy fifty,Vodka,Elderflower syrup,Lemon juice,Honey syrup,Vanilla extract,Red chili pepper Tipperary,Irish whiskey,Sweet red vermouth,Green Chartreuse,Angostura bitters,Orange Trinidad sour,Angostura bitters,Orgeat (almond) syrup,Lemon juice,Rye whiskey Naked and famous,Mezcal,Yellow Chartreuse,Aperol,Lime juice New York sour,Rye whiskey,Lemon juice,Egg white,Simple syrup,Red wine,Lemon,Cherry Spritz,Prosecco,Aperol,Soda water,Orange Gimlet,Lime juice,Simple syrup,Gin 20th century,Gin,Lemon juice,White crème de cacao,Kina lillet,Lemon 

bcardiff commented Jun 27, 2020

 The following is a Z3 program that can be used in https://rise4fun.com/Z3 I need to encode the whole recipe list and see if it's solvable in a reasonable amount of time. ;; cock_i = 1 <=> the cocktail can be made (declare-const cock1 Int) (declare-const cock2 Int) (declare-const cock3 Int) ;; r_i extra variables that means you only made a part of the cocktail i (declare-const r1 Real) (declare-const r2 Real) (declare-const r3 Real) ;; ing_i = 1 <=> the ingredient is picked (declare-const ing1 Int) (declare-const ing2 Int) (declare-const ing3 Int) (declare-const ing4 Int) ;; "boolean" constraints for cocktails (assert (and (>= cock1 0) (>= cock2 0) (>= cock3 0))) (assert (and (<= cock1 1) (<= cock2 1) (<= cock3 1))) ;; constraints to represent *part* of the drink. (assert (and (>= r1 0) (>= r2 0) (>= r3 0))) (assert (and (< r1 1) (< r2 1) (< r3 1))) ;; "boolean" constraints for ingredients (assert (and (>= ing1 0) (>= ing2 0) (>= ing3 0) (>= ing4 0))) (assert (and (<= ing1 1) (<= ing2 1) (<= ing3 1) (<= ing4 1))) ;; The recipes ;; if cock1 is made of ing1 & ing2 ;; we want to say floor((ing1 + ing2) / 2) = cock1 ;; since 0 <= r1 < 1 and cock1 \in {1, 0} ;; the formula ing1 + ing2 = 2 * (cock1 + r1) will do the trick (assert (= (+ ing1 ing2) (* 2 (+ cock1 r1)))) (assert (= (+ ing2 ing3) (* 2 (+ cock2 r2)))) (assert (= (+ ing2 ing3 ing4) (* 3 (+ cock3 r3)))) ;; The question: give 2 ingredientes, what is the maximum amount of cocktails we can make? (assert (= (+ ing1 ing2 ing3 ing4) 2)) (maximize (+ cock1 cock2 cock3)) ;; Or, if I want to have 2 cocktails menu, how small can be my grocery list ;-) ;; (assert (= (+ cock1 cock2 cock3) 2)) ;; (minimize (+ ing1 ing2 ing3 ing4)) (check-sat) ;; Give me the answer! (get-model) 

bcardiff commented Jun 27, 2020

 I needed to change a bit the csv, the expanded program is in https://gist.github.com/bcardiff/462ddcae5b8e886e6d69975d9830d77e . Now I need to tweak the timeout... maybe tomorrow! This was fun.

fgregg commented Jun 28, 2020 • edited

 Here's a branch and bound solution. pretty fast! import random from typing import AbstractSet, Set, FrozenSet, Optional Cocktail = FrozenSet[str] Cocktails = AbstractSet[Cocktail] Ingredients = Set[str] class BranchBound(object): def __init__(self, max_calls: int, max_size: int) -> None: self.calls: int = max_calls self.max_size: int = max_size self.highest_score: int = 0 self.highest: Cocktails = set() def search(self, candidates: Cocktails, partial: Optional[Cocktails] = None) -> Cocktails: if partial is None: partial = set() if self.calls <= 0: print('early stop') return self.highest self.calls -= 1 score = len(partial) if score > self.highest_score: self.highest = partial self.highest_score = score print(self.highest_score) # what cocktails could be added without going over our # ingredient budget? partial_ingredients: Ingredients partial_ingredients = set().union(*partial) candidates = {cocktail for cocktail in candidates if len(cocktail | partial_ingredients) <= self.max_size} possible_increment = len(candidates) # if adding all the associated ingredients of the candidates # takes us over the ingredient budget, then not all the # candidates can feasibly be added to our partial # solution. So, if there will be excess ingredients, we'll # reduce the upper bound of how many cocktails we might be # able to cover (possible_increment). candidate_ingredients: Ingredients candidate_ingredients = set().union(*candidates) excess_ingredients = (len(candidate_ingredients | partial_ingredients) - self.max_size) if excess_ingredients > 0: # best case is that excess ingredients are concentrated in # some cocktails. if we are in this best case, then if we # remove the cocktails that add the most new ingredients # we'll be back under the ingredient budget # # note that we are just updating the bound. it could actually # be that we want to add one of these cocktails that add # a lot of ingredients ingredient_increases = sorted((len(cocktail - partial_ingredients) for cocktail in candidates), reverse=True) for ingredient_increase in ingredient_increases: possible_increment -= 1 excess_ingredients -= ingredient_increase if excess_ingredients <= 0: break threshold = self.highest_score - score if candidates and possible_increment > threshold: # i've tried a few heuristics like "next smallest # cocktail," and a random choice seems to be best so far best = min(candidates, key=lambda x: random.random()) new_partial_ingredients = partial_ingredients | best covered_candidates = {cocktail for cocktail in candidates if cocktail <= new_partial_ingredients} self.search(candidates - covered_candidates, partial | covered_candidates) # if a cocktail is not part of the optimum set than then # the optimum set cannot have the cocktail as a subset remaining = {cocktail for cocktail in candidates - set(best) if not (best <= (cocktail | partial_ingredients))} self.search(remaining, partial) return self.highest if __name__ == '__main__': import csv cocktails = {} with open('ingredients.csv') as f: reader = csv.reader(f) for row in reader: name, *ingredients = row cocktails[frozenset(ingredients)] = name bb = BranchBound(8000000, 16) best = bb.search(cocktails.keys()) print(sorted(set().union(*best))) print(sorted(cocktails[k] for k in best))