sets.md

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!

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

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)

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.

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