Comparatortionist: The $M_Q$ Functor

Question

The Problem

At the intersection of mathematics, computer science, and insanity, we find the $M_Q$ functor${}^1$.

$${M_Q} = {\Phi _{{s_1},{s_2}}}\left\{ {\begin{array}{*{20}{l}} {E \leftarrow {\Phi _{{c_1},{c_2}}}\left\{ { \Leftarrow \left\{ {\begin{array}{*{20}{l}} 1&{{\text{if }}{c_1} = {c_2}} \\ 0&{{\text{otherwise}}} \end{array}} \right.} \right.} \\ {N \leftarrow {\Re _0}\left[ {{\Phi _{{x_1},{x_2}}} \Leftarrow {x_1} + {x_2}} \right]} \\ {U \leftarrow {\Phi _c} \Leftarrow 60{{\left( {N\left( {\mathcal{L}\xrightarrow{s}N\left( {s\xrightarrow{\chi }E\left( {c,\chi } \right)} \right)} \right) + 1} \right)}^{ - 1}}} \\ {{I_{\text{L}}} \leftarrow {\Phi _s}\left\{ { \Leftarrow \left\{ {\begin{array}{*{20}{l}} 1&{{\text{if }}s \in \left\{ s \right\} \cap \mathcal{L}} \\ 0&{{\text{otherwise}}} \end{array}} \right.} \right.} \\ {\bar S \leftarrow {\Phi _s} \Leftarrow \left( {{2^{\left\{ {i\,|\,i \in \mathbb{N},\,i \leqslant \left| s \right|} \right\}}}\xrightarrow{X}{s^X}} \right)\backslash \left\{ {s,\varepsilon } \right\}} \\ {V \leftarrow {\Phi _s} \Leftarrow N\left( {s\xrightarrow{\chi }U\left( \chi \right)} \right)} \\ {x \leftarrow {\Phi _s} \Leftarrow {\Re _0}\left[ {{\Phi _{{x_1},{x_2}}}\left\{ { \Leftarrow \left\{ {\begin{array}{*{20}{l}} {{x_1}}&{{\text{if }}{x_1} \geqslant {x_2}} \\ {{x_2}}&{{\text{otherwise}}} \end{array}} \right.} \right.} \right]\left( {\bar S\left( s \right)\xrightarrow{{s'}}V\left( {s'} \right) I_{\rm L}\left( s' \right)} \right)} \\ {\Upsilon \leftarrow {\Phi _s} \Leftarrow \frac{{V\left( s \right) - x\left( s \right)}}{{2{I_{\text{L}}}\left( s \right) - 1}}} \\ { \Leftarrow \Upsilon \left( {{s_1}} \right) - \Upsilon \left( {{s_2}} \right)} \end{array}} \right.$$

$M_Q$ is a binary (that is, two-parameter) comparator of strings. As most computer scientists know, a comparator is a special type of functor that imposes a total ordering on a set of objects.

When applied to strings $s_1$ and $s_2$, ${M_Q}\left( {{s_1},{s_2}} \right)$ returns

• a negative value if $s_1$ should come before $s_2$ in a sorted list
• a positive value if $s_1$ should come after $s_2$ in a sorted list
• $0$ if the relative order of $s_1$ and $s_2$ is unimportant

$M_Q$ also relies on a language, $\mathcal{L}$, which is an ordered list of non-empty strings.

For our purposes, let the elements of $\mathcal{L}$ be the strings $\mathsf{a}$, $\mathsf{ae}$, $\mathsf{be}$, $\mathsf{bee}$, $\mathsf{ade}$, $\mathsf{bed}$, $\mathsf{are}$, $\mathsf{bad}$, $\mathsf{bab}$, $\mathsf{baa}$, $\mathsf{abe}$, $\mathsf{bear}$, $\mathsf{barb}$, $\mathsf{bard}$, $\mathsf{bade}$, $\mathsf{beard}$, $\mathsf{bread}$, $\mathsf{badab}$, $\mathsf{bared}$, $\mathsf{barred}$.

$M_Q$ can compare not only strings in $\mathcal{L}$, but also any strings made up of the letters $\mathsf{a}$-$\mathsf{z}$ (for example, $\mathsf{leopard}$).

The Challenge

Your task is threefold:

1. Describe, in plain English, the order that $M_Q$ imposes on strings. In other words, provide a description of what exactly the comparator does.

2. Determine which string will come last if $\mathcal{L}$ is sorted by $M_Q$.

3. Determine a string (not necessarily in $\mathcal{L}$) that will come before the string $\mathsf{babadook}$ in a list sorted by $M_Q$.

This problem can (and ideally should) be solved without programming. In particular, all of the variables, functions, etc. have straightforward behaviours that can be intuited and computed by hand. There should be no heavy lifting or brute forcing involved.

Are you up to the task? Can you master the comparatortionist?

Notes on Syntax

Let $\varepsilon$ be the empty string.

Let $\left| s\right|$ be the length (i.e. number of characters in) string $s$.

Strings may be treated as lists. A string is an ordered list of its characters.

Let ${\Phi _{{{\arg }_1},{{\arg }_2}, \cdots ,{{\arg }_n}}} \Leftarrow f\left( {{{\arg }_1},\,\,{{\arg }_2},\,\, \cdots ,\,\,{{\arg }_n}} \right)$ be a function returning an $n$-ary functor that returns the value of the function $f$ applied to its arguments. (This convention is used since functors may be nested or passed as arguments to other functors.)

Similarly, let $${\Phi _{{{\arg }_1},{{\arg }_2}, \cdots ,{{\arg }_n}}}\left\{ {\begin{array}{*{20}{l}} {{\text{assignment}}} \\ {{\text{assignment}}} \\ {\,\,\,\,\,\,\,\,\, \vdots } \\ {{\text{assignment}}} \\ { \Leftarrow f\left( {{{\arg }_1},\,\,{{\arg }_2},\,\, \cdots ,\,\,{{\arg }_n}} \right)} \end{array}} \right.$$ be a function returning an $n$-ary functor that evaluates assignments from top to bottom and returns the value of the function $f$ applied to its arguments.

Let ${\Re _{{\text{init}}}}\left[ f \right]$ be a function returning a unary functor accepting a list/string as its argument. Call this argument $A$. The functor returned by ${\Re _{{\text{init}}}}\left[ f \right]$ reduces $A$ to a single value, starting with an initial value $\text{init}$ and iteratively applying the reducing binary operator $f$. Note that $f$ is always an associative and commutative functor.

Let $S\xrightarrow{e}f\left( e \right)$ be the ordered list obtained by mapping each element $e$ of $S$ to $f\left( e \right)$, where $f$ is a function.

Finally, given string $s$ and set of natural numbers $X$, let ${s^X}$ be the substring of $s$ whose 1-based character indices are present in $X$. For example, if $s = \mathsf{this}$, then ${s^{\left\{ {1,3} \right\}}} = \mathsf{ti}$ and ${s^{\left\{ {1,2,4} \right\}}} = \mathsf{ths}$.

All remaining operators, symbols, and syntax are standard for mathematical science, computer science, or both, and are left to the reader to infer/deduce. A large part of the challenge is "getting a handle on" the syntax.

---

${}^1$ note that "functor" here refers to "function which can be stored as a variable and passed as an argument". Also commonly known as a "lambda expression" or a "map".

Answer 1

Our first step is to figure out what COTO's notation means. Here are a couple translations for the more obscure forms:

• A "functor" is just another name for an ordinary function (since none of the "functors" given accept functions as arguments), with the following equivalence relationship: $$ \Phi_{x_1,x_2,x_3\ldots}\Leftarrow f(x_1,x_2,x_3\ldots) \equiv x_1,x_2,x_3\ldots\mapsto f(x_1,x_2,x_3\ldots) $$
• He also defines a second type of functor/function with intermediate assignments. However, this notation is only used for $M_Q$ itself, and all but the last line do not depend on the arguments, so they only function as (no pun intended) names for various (otherwise anonymous) functions. We can safely break them out and consider them separately. This essentially gives us: $$ \begin{align} E&:s_1,s_2\mapsto\cdots \\ &\qquad\vdots \\ M_Q&:s_1,s_2\mapsto\cdots \end{align} $$
• The "reducing" functor $\Re$ (a true functor this time) extends a binary function to an $n$-ary function with an initial value: $$ \Re_{a_0}[f](a_1,a_2\ldots a_n)\equiv f(\ldots f(f(a_0,a_1),a_2)\ldots,a_n) $$
• The "mapping" functor $\to$ applies a function to each member of a list: $$ S\xrightarrow{e}f(e)\equiv\{f(e) : e\in S\} $$
• The "substring" notation can be rewritten using a variant of set notation: $$ s^X\equiv\{s_i:i\in X\} $$
• Finally, thanks to Stacey we know that $2^S$ is the power set of $S$, or the set of all its subsets: $$ 2^S\equiv \mathcal P(S) $$ Representing the power set as exponentiation is actually a standard notation, but it confused both me and Stacey, so I'll use $\mathcal P$ just to be unambiguous.

Note that COTO seems to follow the convention that arguments named $s$ are strings, and arguments named $c$ are characters.

---

The first step in $M_Q$ is to assign a functor to $E$, which returns $1$ if its arguments are equal, and $0$ otherwise.

The next step assigns a functor to $N$. This one reduces a list by repeatedly adding its elements to a running total, which starts at zero: that is, it takes the sum of a list. From here on I'll replace $N\to\Sigma$.

$U$ is a crazy beast. Rewriting it using my 'standard' notation (and combining the "total" and "map" constructs into a standard sum):

$$ U:c\mapsto\frac{60}{1+\sum_{s\in\mathcal L,\chi\in s}E(c,\chi)} $$

It counts the number of times $c$ occurs across all the strings in $\mathcal L$ and then applies $\frac{60}{1+\Sigma}$. The result of $U$ therefore is to weight characters according to the following table:

$$ \begin{align} \mathsf a~\text{or}~\mathsf b&\to 3\\ \mathsf d&\to \frac{60}{11}\\ \mathsf e&\to 4\\ \mathsf r&\to 6\\ \text{(all others)}&\to 60\\ \end{align} $$

Next is $I_L$, which simply tests if its argument is a member of $\mathcal L$ (returning $1$ if so and $0$ otherwise).

$\bar S$ is the only function to use the power set notation or the substring notation. We can write it as:

$$ \bar S:s\mapsto\{\sigma:\sigma\subset s,\,\sigma\neq\varepsilon\} $$

Here I define a string $a$ to be a proper substring of $b$ ($a\subset b$) iff you can construct $a$ by removing a nonzero number of characters from $b$.

$$ V:s\mapsto\sum_{\chi\in s}U(\chi) $$

$V$ simply sums the values of all the characters in its input.

With $x$ we begin to put things together. First I'll look at the reducing functor: for each element of its input, if that element is greater than the current value of the functor, it sets its current value to that of the element. That is, it takes the maximum of its inputs. Now we can write:

$$ x:s\mapsto\max_{s'\in\bar S(s)}V(s')I_L(s') $$

We can say a couple of things about $x$:

• Multiplying by $I_L(s')$ only lets $s'\in\mathcal L$ contribute to the result;
• Since $\varepsilon\notin\mathcal L$, that part of the definition of $\bar S$ is implicitly satisfied (and $V(\varepsilon)=0$ anyway).

Thus we can rewrite:

$$ x:s\mapsto\max\{V(\sigma):\sigma\in\mathcal L,\,\sigma\subset s\} $$

That is, $x$ returns the highest value of a string in $\mathcal L$ that is a substring of $s$.

Finally, we define $\Upsilon$:

$$ \Upsilon:s\mapsto\frac{V(s)-x(s)}{2I_L(s) - 1} $$

$I_L$ basically splits this into two cases:

$$ \Upsilon:s\mapsto [V(s)-x(s)]\times\left\{\begin{array}{ll} +1 & s\in\mathcal L\\ -1 & s\notin\mathcal L\\ \end{array}\right. $$

After this, $M_Q$ merely sorts in order of increasing $\Upsilon$.

The Answer

The score of a letter can be determined according to the above table. A string's base score is the sum of its letter's scores. A string's adjusted score is equal to the the highest base score of strings in $\mathcal L$ that are proper substrings of itself, subtracted from its own base score.
Strings are sorted by $M_Q$ into order of decreasing score, except for the strings in $\mathcal L$, which are placed after all other strings in order of increasing score.

The ordering of $\mathcal L$ (and a few extras):

This image shows, for each string, the string's base score, the string with the substring(s) from $\mathcal L$ crossed out and the score that they remove, and the value of $\Upsilon$.

As we can see, the last strings in $\mathcal L$ (which form an equivalence class under $M_Q$) are

$\mathsf{bread}$ and $\mathsf{bear}$.

There are (according to DictionaryLookup) 72 English words in the equivalence class immediately preceding $\mathsf{babadook}$, the longest of which is

$\mathsf{embarrassed}$

and the shortest of which appear in the above table.

Answer 2

This algorithm works as follows:

Calculates a rating for a given string s based on the number of times the letters found in s occur in the dictionary and if s occurs in the dictionary itself.
A negative rating means higher on the list.
If s is in the dictionary, only letters with non-power-of-two locations are taken into account.
If s is not in the directory, all letters are counted and the rating sign is flipped to negative.
As a result, there is a heavy bias toward words not in the dictionary (especially words containing characters not in the dictionary at all) and toward shorter dictionary words (especially 1 or 2 letter words) since the first two places are powers of 2.

The last word if the dictionary were sorted would be

"barred" since it has the most letters in non power of two positions.

A word before babadook would be

any longer, non dictionary word, that contains at least 3 letters not in the dictionary and few dictionary letters. Non dictionary letters count -60, my name (stacey) would be -303 (5x60 + 3)