From f09e3205cffadcde1753e09a148a27f1cb8c6264 Mon Sep 17 00:00:00 2001 From: cyfraeviolae Date: Sun, 4 Jul 2021 23:58:55 -0400 Subject: static --- index.html | 131 +++++++++++++++++++++++++++++++------------------------------ 1 file changed, 67 insertions(+), 64 deletions(-) (limited to 'index.html') diff --git a/index.html b/index.html index 088eba7..079723f 100644 --- a/index.html +++ b/index.html @@ -3,72 +3,22 @@ Well-Ordered - + + +
-

Well-Ordered

+
+ Well-Ordered@cyfraeviolae.org + | + source code +

The bibulous sorcerer Roseacrucis has depleted our distilled reserves. You must journey to obtain the - hallowed ingredients necessary to recreate the seventy-seven official IBA cocktails—but your wallet runs - light, and your thirst grows stronger. In what order do you obtain the ingredients in order to create the - most recipes for the fewest stater? + 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 with the fewest drachma?

@@ -357,9 +307,62 @@ form {
+
+ 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. +

+
- - - + + + + -- cgit v1.2.3