Well-Ordered@cyfraeviolae.org | source code

The bibulous sorcerer Roseacrucis has depleted our distilled reserves. You must journey to obtain the myriad ingredients necessary to recreate the seventy-seven official IBA cocktails—but your wallet runs light, and your thirst grows deep. In what order do you obtain ingredients to make the most drinks for the fewest drachma?

Select any ingredients already owned or of negligible cost.

The sample solution given the pre-selected ingredients:

  1. On-hand
  2. Vodka
    • Sea Breeze, Screwdriver, Bloody Mary, Moscow Mule
  3. White rum
    • Mojito, Cuba Libre, Pina Colada, Daiquiri
  4. Triple Sec
    • Lemon Drop Martini, Cosmopolitan, Kamikaze
  5. Tequila
    • Margarita, Tommy's Margarita, Vampiro
  6. Gin
    • Long Island Iced Tea, Gin Fizz, John Collins, White Lady
  7. Cognac
    • Horse's Neck, Sidecar, Between the Sheets
  8. Galliano
    • Yellow Bird, Golden Dream, Harvey Wallbanger
  9. Grenadine
    • Bacardi, Tequila Sunrise
  10. Cherry liqueur
    • Aviation, Mary Pickford, Hemingway Special
  11. Bourbon
    • Whiskey Sour, Mint Julep
  12. Dry vermouth
    • Dirty Martini, Dry Martini
  13. Champagne
    • Mimosa, French 75
  14. Angostura bitters
    • Old Fashioned, Champagne Cocktail
  15. Dark rum
    • Planter's Punch, Dark 'n' Stormy
  16. Coffee liqueur
    • Espresso Martini, Black Russian
  17. DiSaronno
    • God Mother, French Connection
  18. Créme de Cacao
    • Alexander
  19. Créme de Menthe
    • Grasshopper, Stinger
  20. Lillet Blonde
    • Vesper
  21. Absinthe
    • Monkey Gland
  22. Apricot brandy
    • Paradise
  23. Pisco
    • Pisco Sour
  24. Raspberry syrup
    • Clover Club
  25. Orange bitters
    • Casino
  26. Maraschino
    • Tuxedo
  27. Red Port
    • Porto Flip
  28. Scotch
    • God Father
  29. Drambuie
    • Rusty Nail
  30. Calvados
    • Angel Face
  31. Prosecco
    • Barracuda
  32. Peach puree
    • Bellini
  33. Peach schnapps
    • Sex on the Beach
  34. Cream liqueur
    • B52
  35. Cachaca
    • Caipirinha
  36. Raspberry liqueur
    • French Martini
  37. Peach bitters
    • Derby
  38. Aperol
    • Spritz Veneziano
  39. Blackberry liqueur
    • Bramble
  40. Sweet vermouth
  41. Campari
    • Negroni, Americano
  42. Rye
    • Manhattan
  43. Orgeat
    • Mai-tai
  44. Irish whiskey
    • Irish Coffee
  45. DOM Bénédictine
    • Singapore Sling
  46. Créme de Cassis
    • Russian Spring Punch
  47. Peychaud's bitters
    • Sazerac
  48. Orange flower water
    • Ramos Fizz
  49. Dry white wine
    • Kir
  50. Kirsch
  51. Strawberry syrup
    • Rose
Explain.

A recipe is a set of ingredients. The well-ordering problem: given a set of recipes \(r_1\ldots{}r_m\) comprised of ingredients \(y_1\ldots{}y_n\), find an ordering \(\sigma\) of the ingredients that maximizes \[ \large\sum_{i=1}^{n}\sum_{j=1}^{m} p_\sigma(i, j) \] where \[ \large p_\sigma(i, j) = \begin{cases} 1 & r_j \subseteq \{y_{\sigma^{-1}(k)} \mid 1 \leq k \leq i\} \\ 0 & \mathrm{otherwise.} \end{cases} \]

In other words, we assign one point to each recipe in each round it is satisfiable by the already-collected ingredients. We reduce the well-ordering problem to integer linear programming:

\[ \large \begin{equation} \begin{split} \text{maximize } & \sum_{k=1}^n\sum_{j=1}^m v_{k,j} \\ \text{subject to } & \begin{aligned}[t] \sum_{i=0}^{n}c_{k, i} &= k & k \in [1, n] \\ c_{k,i} &\le c_{k+1, i} & i \in [1, n], k \in [1, n-1] \\ v_{k,j} &\ge -\lvert{}r_j\rvert + 1 + \sum_{i \in r_j}c_{k,i} & k \in [1, n], j \in [1, m] \\ v_{k,j} &\le c_{k,i} & k \in [1, n], j \in [1, m], i \in r_j \\ \end{aligned} \\ \text{binary } & \begin{aligned}[t] v_{k,j} & & k \in [1, n], j \in [1, m] \\ c_{k,i} & & k \in [1, n], i \in [1, n] \\ \end{aligned} \\ \end{split} \end{equation} \]

\(c_{k,i}\) is set when \(y_i\) is collected in rounds 1 through \(k\). \(v_{k,j}\) is set if \(r_j\) is satisfiable in round \(k\). The first and second constraints ensure exactly one ingredient is added in each round. The third and fourth constraints model that \(v_{k,j} = \bigwedge\limits_{i \in r_j} c_{k,i}\).

The system is solved in-browser using jvail's port of GLPK to WebAssembly. Alternatively, COIN-OR's cbc can find the optimal solution in under thirty seconds on a desktop computer. Recipes adapted from teijo/iba-cocktails.