13
$\begingroup$

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$

$\endgroup$
2
  • $\begingroup$ Are functions-as-parameters permitted? If not, are you absolutely certain this is solvable? It would be difficult even with them, but it doesn't look solvable to me without them. There's too much complexity to dig through, and not enough resources to do the digging. $\endgroup$ – Ben Barden Sep 8 '20 at 19:46
  • $\begingroup$ The puzzle statement is now more clear about using only numbers as arguments, @Ben Barden, though we could certainly use some (more? i don't recall any) puzzles with functional parameters. If you have an approach that breaks any of this puzzle's conditions, please post nonetheless! I do have working code that follows these conditions straightforwardly and have added to the statement a link to what motivated this puzzle. Incidentally, some MathJax puzzles' solutions actually create functions (\macros) on the fly. $\endgroup$ – humn Sep 8 '20 at 22:14
4
+100
$\begingroup$

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))
$\endgroup$
3
  • 1
    $\begingroup$ @humn Done, I think. Please check. $\endgroup$ – Paul Panzer Sep 10 '20 at 4:56
  • $\begingroup$ Yes, @Paul Panzer! Thank you for spelling out the functions just as hoped. Mechanical though that is, it's meant to avert less efficient solutions and make testing easy. Your partitions happen to exactly match the intended solution, which would not even be necessary, and they lay out very nicely on the 3-dimensional grid. Thank you also for sharing your Python basket of goodies, all the way from creating the partitions (in a way that accomplishes $\rm mod\,3$ by array wrapping?) to producing $\rm M\raise.5ex{\scriptsize ATH\,}J\scriptsize AX$! Tributes are on the way. $\endgroup$ – humn Sep 10 '20 at 7:04
  • 1
    $\begingroup$ @humn Yes, the three easy splittings can be done by axis trickery. You just have to note that if you reinterpret linear indexed data as being b x b x b x ... dimensional in the standard layout, then the new coordinates will be the digits of the linear index in base b. By moving a given axis n to the front and reinterpreting as linear we can group and split by the nth digit. The other splits require more work and do use an explicit %3 somewhere. Btw. as I type this I noticed that by using moveaxis instead of swapaxes we could save the subsequent sort for the first three splits. $\endgroup$ – Paul Panzer Sep 10 '20 at 8:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.