diff options
Diffstat (limited to 'index.html')
| -rw-r--r-- | index.html | 131 |
1 files changed, 67 insertions, 64 deletions
@@ -3,72 +3,22 @@ <head> <title>Well-Ordered</title> <meta charset="utf-8"> - <style> -body { - background: #fdf3f3; - color: DarkSlateGrey; - font-family: EBGaramond, serif; - font-size: large; -} - -a { - color: #1a97bf; -} - -a:hover { - color: #075d77; -} - -.container { - margin: 1em; - max-width: 40em; -} - -.row { - margin-bottom: 1em; -} - -.title { - letter-spacing: -0.5px; -} - -div { - margin-bottom: 10px; -} - - -form { - border: 1px DarkSlateGrey solid; - padding: 10px; - padding-left: 25px; -} - -.sep { - margin-left: 6px; - margin-right: 6px; -} - -.nonbreaking { - white-space: nowrap; -} - .ingredient { - display: inline-block; - margin-right: 5px; - margin-bottom: 5px; - } - button { - margin-right: 10px; - } - </style> + <meta name="viewport" content="width=device-width, initial-scale=1.0"> + <link rel="stylesheet" type="text/css" href="/static/styles.css"> + <link rel="shortcut icon" type="image/x-icon" href="/static/favicon.ico"> </head> <body> <div class="container"> - <h3>Well-Ordered</h3> + <div> + <a href="/" class="title">Well-Ordered</a><span>@</span><a href="https://cyfraeviolae.org">cyfraeviolae.org</a> + <span class="sep">|</span> + <a href="https://git.cyfraeviolae.org/well-ordered">source code</a> + </div> <p> 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? </p> <noscript>Sorry, JavaScript is required to run Well-Ordered.</noscript> <div id="form"> @@ -357,9 +307,62 @@ form { </div> <div id="waiting"></div> <div id="solution"></div> + <details> + <summary>Explain.</summary> + <p> + 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} \] + </p> + <p> + 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: + </p> + <p> + \[ + \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} + \] + </p> + <p> + \(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}\). + </p> + <p> + The system is solved in-browser using <a href="https://github.com/jvail/glpk.js">jvail's port</a> of + <a href="https://www.gnu.org/software/glpk/">GLPK</a> to WebAssembly. Alternatively, COIN-OR's + <a href="https://projects.coin-or.org/Cbc">cbc</a> can find the optimal solution in under thirty seconds on + a desktop computer. Recipes adapted from + <a href="https://github.com/teijo/iba-cocktails">teijo/iba-cocktails</a>. + </p> + </details> </div> - <script src="./node_modules/glpk.js/glpk.js"></script> - <script src="./recipes.js"></script> - <script src="./script.js"></script> + <script id="MathJax-script" async src="/static/mathjax.js"></script> + <script src="/static/glpk.js"></script> + <script src="/static/recipes.js"></script> + <script src="/static/script.js"></script> </body> </html> |