Is $~\let\r\raise\text{3rd.3}\r.6ex{\small3}\r1.1ex{\scriptsize3}\!\:\r1.6ex{\tiny3}\!\;\r2.2ex.\!\r2.5ex.\!\r2.8ex.\!\!\!\!\!\!(~)~$ too much to ask?

Question

You will not be asked to devise a function to find the third-least of $ 3 \raise .6ex {\small 3} \raise 1.1ex { \scriptsize 3}\!\: \raise 1.6ex { \tiny 3} \!\; \raise 2.2ex . \! \raise 2.5ex . \! \raise 2.8ex . \!\!\!\!\!\! $ numbers today, rather to merely show that you could. $ \begingroup \def \= { \mathop{\normalsize\,\raise-.2ex\triangleq\,} } \def \yellow { \color {#aaaa00} } \def \red { \color{#990044} } \def \t #1{ \small \text{#1} } \def \blunderline #1{{ #1 \rlap{ \, \llap {\red {\raise -.33ex{\underline {\hphantom {\, #1\, }}}}} \llap{ \yellow{ \raise-.55ex{ \underline{ \hphantom{ \,#1 \,}}}}} } }} \def \strikeline #1{{ #1 \rlap{ \, \llap { \red {\raise 1.18ex{\underline {\hphantom {\, #1\, }}}}} } }} $

• What definitions of $\t{3rd.27}(a,b,c,\dots,x,y,z,zz)$ and 4 other simple functions of your choice can work together to find the third-least of any 27 different numbers regardless of input order?

Devising 5 simple functions to find the third-least of only $27$ (${\small =}\, 3\small\raise.6ex 3$) numbers would surely convince anyone that 9 simple functions could cover 7625597484987 ($ {\small =}\, 3 \raise .6ex {\small 3} \raise 1.1ex { \scriptsize 3} $) input numbers and so on. A “simple function” has a fixed number of numeric inputs, like these sample simple functions.

$$\small\begin{align} \t{Max.3}(a,b,c) & \= \t {Max.2} ( \, \t{Max.2}(a,b) , c \, ) \\[1.5ex] \t{Median.3}(a,b,c) & \= \t {Max.3} ( \, \t {Min.2}(a,b) , \, \t {Min.2}(b,c) , \, \t{Min.2}(a,c) \, ) \end{align}$$

(“$\! \= \!$” means “is defined as.”)  A simple function simply calls one other function, passing inputs that may each contain an additional level of function call. This amounts to a two-deep function call with no variables, conditionals, loops, other operations, . . .  And the definition of a truly simple function does not include any larger functions (those with more inputs than the function being defined).

$$\small\begin{align} \t{TwoDeepIsOkay.4}(a,b,c,d) & \= \t {Max.2} ( \, \t {Max.2}(a,b) , \, \t{Max.2}(c,d) \, ) \\[1.5ex] \strikeline { \t {ThreeDeepIsTooDeep.4}(a,b,c,d) } & \= \strikeline{ \t {Max.2} ( \, \t {Max.2} ( \, \blunderline{ \t{Max.2}(a,b) } , \, c \, ) , \, d \, ) } \\[1.5ex] \strikeline { \t {ShouldNotCallLargerFunctions.}\blunderline{2}(a,b) } & \= \strikeline{ \t {Median.}\blunderline{3} ( \, a , \, b , \, \t{Mmm.}\blunderline{3}(a,b,a) \, ) } \end{align}$$

Just two functions are available to build upon, providing the lesser and greater of their two inputs:  $ \t {Min.2}(a,b) $ and $ \t{Max.2}(a,b) $.  These are not counted among the 5 functions to be defined but all other utilized functions are, including any of those mentioned above.

If all goes well, for example, $ \small \t{3rd.27} \, ( 70,71,72,73,74, \! $ $ \small 75,76,77,78,79, \! $ $ \small 80,81,82,83,84, \! $ $ \small 85,86,87, \! $ $ \small 11,12,13,14,15, \! $ $ \small 16,17,18,19 ) = 13 $.  To further appreciate Paul Panzer’s solution notice how nicely its components lay out on this 3-dimensional grid of inputs to $ \small \t{3rd.27} \, ( a,b,c,d,e,f,g,h,i, \! $ $ \small j,k,l,m,n,o,p,q,r, \! $ $ \small s,t,u,v,w,x,y,z,zz ) $.

   

(This puzzle was motivated by Misha Lavrov’s solution to I don’t want the smallest one, I want the second-smallest one. Interesting answers that stray from stated conditions are welcome.) $\endgroup$

Answer 1

For building an answer along the lines of the linked solution by Misha Lavrov, the key ingredient is

Finding a hopefully small set of three-way splits of the 27 inputs such that each triplet of inputs is separated into three different subsets at least once. Without the "hopefully small" constraint the task would be easy: Just use $\mathrm{Min}.2925(\mathrm{Max}.3(a,b,c),\mathrm{Max}.3(a,b,d),...)$ i.e. generate all 2925 triplets, take the maximum for each and then take the minimum of the maxima.

As demonstrated in the linked solution the number of terms can be drastically reduced by intelligent grouping which leads us back to my initial statement. If we had a family of splits $A_i\dot\cup B_i \dot\cup C_i = \{a,...,zz\}$ with the stated properties then there would be at least one $i$ such that the three smallest elements were distributed one in $A_i$, one in $B_i$ and one in $C_i$ and could be recovered taking the minima over $A_i$, $B_i$ and $C_i$, respectively. The smallest but two element then is $\mathrm{Max}.3(\mathrm{Min}.9(A_i),\mathrm{Min}.9(B_i),\mathrm{Min}.9(C_i))$ (I've made the three subsets the same size 9 for simplicity.) As we don't know which $i$ is the one we as the last step take the minimum over all splits $i$.

So how to split? Let's encode variable identity in base 3, so each id has three places taking values $0,1,2$. There are two cases: Case 1. There is a single place $\gamma$ where the three smallest (let's call them $x,y,z$ without stating which is which) differ: $x_\gamma\ne y_\gamma\ne z_\gamma \ne x_\gamma$. This case we can cover by simply splitting on that place creating three splits in total. Case 2. Otherwise there are two places $\delta\ne\gamma$ separating $x$ from $y$ and $z$, respectively. One can check that these can be chosen such that $y_\delta \ne z_\gamma,x_\delta=z_\delta,x_\gamma=y_\gamma$. We now split based on the sum $\gamma+\delta \mod 3$ and the difference $\gamma-\delta \mod 3$ adding another $2\times 3$ splits (because there are three possible pairs $\gamma,\delta$). It is clear that id $x$ will fall into a separate subset. As the other two differ in both places these differences can cancel in the sum or the difference but not both because 3 is odd. And with that we have successfully created a family of $9$ even threeway splits with the desired properties. In summary: $3\mathrm{rd}.27(a,...,zz) = \mathrm{Min}.9(\mathrm{Max}.3(\mathrm{Min}.9(A_1),\mathrm{Min}.9(B_1),\mathrm{Min}.9(C_1)),...,\mathrm{Max}.3(\mathrm{Min}.9(A_9),\mathrm{Min}.9(B_9),\mathrm{Min}.9(C_9))$

Full expression as exported by SymPy (code is at end of post):

$$\begin{gather} \operatorname{Max.3}{\left (a,b,c \right )}=\operatorname{Max.2}{\left (\operatorname{Max.2}{\left (a,b \right )},c \right )}\\ \operatorname{Min.3}{\left (a,b,c \right )}=\operatorname{Min.2}{\left (\operatorname{Min.2}{\left (a,b \right )},c \right )}\\ \operatorname{Min.9}{\left (a,b,c,d,e,f,g,h,i \right )}=\operatorname{Min.3}{\left (\operatorname{Min.3}{\left (a,b,c \right )},\operatorname{Min.3}{\left (d,e,f \right )},\operatorname{Min.3}{\left (g,h,i \right )} \right )}\\ \operatorname{Aux.27}{\left (a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,zz \right )}=\operatorname{Max.3}{\left (\operatorname{Min.9}{\left (a,b,c,d,e,f,g,h,i \right )},\operatorname{Min.9}{\left (j,k,l,m,n,o,p,q,r \right )},\operatorname{Min.9}{\left (s,t,u,v,w,x,y,z,zz \right )} \right )}\\ \operatorname{3rd.27}{\left (a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,zz \right )}=\operatorname{Min.9}{\left (\operatorname{Aux.27}{\left (a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,zz \right )},\operatorname{Aux.27}{\left (a,b,c,j,k,l,s,t,u,d,e,f,m,n,o,v,w,x,g,h,i,p,q,r,y,z,zz \right )},\operatorname{Aux.27}{\left (a,d,g,j,m,p,s,v,y,b,e,h,k,n,q,t,w,z,c,f,i,l,o,r,u,x,zz \right )},\operatorname{Aux.27}{\left (a,b,c,p,q,r,v,w,x,d,e,f,j,k,l,y,z,zz,g,h,i,m,n,o,s,t,u \right )},\operatorname{Aux.27}{\left (a,b,c,m,n,o,y,z,zz,d,e,f,p,q,r,s,t,u,g,h,i,j,k,l,v,w,x \right )},\operatorname{Aux.27}{\left (a,f,h,j,o,q,s,x,z,b,d,i,k,m,r,t,v,zz,c,e,g,l,n,p,u,w,y \right )},\operatorname{Aux.27}{\left (a,e,i,j,n,r,s,w,zz,b,f,g,k,o,p,t,x,y,c,d,h,l,m,q,u,v,z \right )},\operatorname{Aux.27}{\left (a,d,g,l,o,r,t,w,z,b,e,h,j,m,p,u,x,zz,c,f,i,k,n,q,s,v,y \right )},\operatorname{Aux.27}{\left (a,d,g,k,n,q,u,x,zz,c,f,i,j,m,p,t,w,z,b,e,h,l,o,r,s,v,y \right )} \right )} \end{gather}$$

Python implementation:

from operator import itemgetter as ig,sub
from itertools import product,combinations
from numpy import array,r_,c_,ogrid,count_nonzero,searchsorted,sort

b3 = r_[:27].reshape(3,3,3)

coords = array(ogrid[:3,:3,:3],object)

mix = c_[[1,0,1],-1:2][sub(*ogrid[:3,:3])].transpose(0,2,1).reshape(6,1,3)

mixed = [mm.ravel().argsort(kind="stable")
         for mm in ((mix@coords)%3).ravel()]

splits = [*(sort(b3.swapaxes(0,i).reshape(3,9),axis=1) for i in range(3)),
          *(sort(mm.reshape(3,9),axis=1) for mm in mixed)]

# done
# everything below is validation and "visualizstion"

# check:
for t in combinations(range(27),3):
    for S in splits:
        for s in S:
            tc = t[:searchsorted(t,s[-1],"right")]
            if count_nonzero(s[s.searchsorted(tc)]==tc) != 1:
                break
        else:
            break
    else:
        raise ValueError(f"triplet {t} not split")
print("Success: all triplets split.")
    
# sympy code (works but very slow)
# you probably want to interrupt as soon as the equations have been printed

from sympy import symbols,Min,Max,latex,Function
from string import ascii_lowercase

all_ = symbols([*ascii_lowercase,"zz"])
for S in all_:    
    exec(f"{S}=S")

Min9 = Function("Min.9")
Min3 = Function("Min.3")
Max3 = Function("Max.3")
Min2 = Function("Min.2")
Max2 = Function("Max.2")
Aux27 = Function("Aux.27")
_3rd27 = Function("3rd.27")

fe1 = Min9(*(Aux27(*ig(*S.ravel())(all_)) for S in splits))
fe2 = Max3(*(Min9(*S) for S in zip(*9*(iter(all_),))))
fe3 = Max2(Max2(a,b),c)
fe4 = Min3(Min3(a,b,c),Min3(d,e,f),Min3(g,h,i))
fe5 = Min2(Min2(a,b),c)
print("$$\\begin{gather}")
print("\\\\\n".join([
    latex(Max3(a,b,c)) + "=" + latex(fe3),
    latex(Min3(a,b,c)) + "=" + latex(fe5),
    latex(Min9(*all_[:9])) + "=" + latex(fe4),
    latex(Aux27(*all_)) + "=" + latex(fe2),
    latex(_3rd27(*all_)) + "=" + latex(fe1)
]))
print("\\end{gather}$$")
print()

_3rd = Min(*(Max(*(Min(*ig(*ss)(all_)) for ss in S)) for S in splits))

for i in combinations(range(27),3):
    sb = dict.fromkeys(all_,100)
    sb.update(zip(ig(*i)(all_),(1,2,3)))
    print(_3rd.subs(sb))