15
$\begingroup$

A simple challenge for the mathematically inclined.

Find a function $f\left( {{x_1},{x_2},{x_3},{x_4}} \right)$ such that $$\begin{gathered} f\left( {2,3,4,5} \right) = 1 \hfill \\ f\left( {1,3,4,5} \right) = 2 \hfill \\ f\left( {1,2,4,5} \right) = 3 \hfill \\ f\left( {1,2,3,5} \right) = 4 \hfill \\ f\left( {1,2,3,4} \right) = 5 \hfill \\ \end{gathered}$$ In constructing $f$, you may use the operations:

  • addition, e.g. $x_1 + x_2$
  • multiplication, e.g. $x_1x_2$
  • remainder, e.g. ${x_1}\backslash {x_2}$, which is the non-negative remainder of integer $x_1$ divided by integer $x_2$; this operation has the same precedence as multiplication, hence $x_1x_2 \backslash x_3x_4$ is interpreted as $\left( {\left( {{x_1}{x_2}} \right)\backslash {x_3}} \right){x_4}$

Note that you may not use numeric constants, subtraction, or division.

The function may use as much or as little operation grouping as needed, e.g. $\left( {{x_1} + {x_2}} \right){x_1}$.

The function does not have to be valid for any inputs besides the five cases listed (you may have remainder-of-division-by-zero in extraneous cases).

Your score is the number of operations in $f$. Lower scores are better. The coveted green checkmark will go to the correct solution with the lowest score.

Can you produce a perfectly primitive parameter permuter?

$\endgroup$
4
  • $\begingroup$ Based on a brute force search, at least $5$ operations are necessary. (There are 1161216 possible $4$ operation functions. I have no clue how a best-first search might work) $\endgroup$ Jul 4, 2015 at 2:19
  • $\begingroup$ @Meelo: My solution had 15 operations, so puzzlers have already blown that out of the water. $\endgroup$
    – COTO
    Jul 4, 2015 at 4:34
  • $\begingroup$ What does 1\hfill mean? Is it just an error with the TEX? $\endgroup$
    – Beta Decay
    Jul 4, 2015 at 9:19
  • 1
    $\begingroup$ @BetaDecay: It must be a TeX bug. I don't see it in my browser (FF 39). $\endgroup$
    – COTO
    Jul 4, 2015 at 13:09

4 Answers 4

13
$\begingroup$

6 Operations

The best function I could find satisfying all of the stated constraints is

y=(a+b+c*c)%(a+b+d).

For my research I have been looking into using genetic algorithms to solve the problem of symbolic regression which seeks the best model given a dataset. This differs from ordinary regression (such as least squares) because in ordinary regression you assume the model and look for the best coefficients. In symbolic regression, you search the function space to find the best model.

While looking for the "best" function, you have to have some error metric to measure the "goodness" of a model such as the mean squared error. But in your case, the simplicity of the model also matters. So I used the Akaike Information Criteria (AIC) which combines the goodness of the fit as well as the complexity of the model to tell you how "good" the model is. Your problem was the perfect thing to play with here.

I did several runs using random initial conditions and most kept converging to this solution above with six operations so this may be the global minimum. This solution took about 3000 generations on average to be found.

I also used f'''s solution (with nine operations) as an initial condition and the best I could get was eight operations with

y = (a+b+a*c*c*(c%b))%(c+d)

mentioned here just for giggles.

$\endgroup$
2
  • $\begingroup$ I'm familiar with the AIC from my own work. I'll give you the check since I sincerely doubt there's a 5-or-better solution. I'm actually quite curious about how you set up the GA for symbolic regression. Did you use a commercial package or did you write your own code? In the latter case, if you'd be willing to publish the code/pseudocode in your solution, I'll happily donate 200 rep for your trouble. $\endgroup$
    – COTO
    Jul 4, 2015 at 13:17
  • $\begingroup$ If it interests you, I have a bounty on a similar type of problem on PPCG. $\endgroup$
    – xnor
    Jul 5, 2015 at 23:59
8
$\begingroup$

9 operations

Here's one based on xnor's last line:

(d+d)%(a+b+c)+(c+d)*c%b*c

This works because (c+d)*c%b is 1 in the last case and 0 in all the others. As xnor noted, (d+d)%(a+b+c) gives $(1,2,3,4,2)$, so multiplying (c+d)*c%b by c and adding it produces $(1,2,3,4,5)$. It doesn't matter whether it is added before or after the last modulus, so (d+d+(c+d)*c%b*c)%(a+b+c) works too.

$\endgroup$
2
  • $\begingroup$ Very nice. You've got the outright lead. $\endgroup$
    – COTO
    Jul 4, 2015 at 4:32
  • $\begingroup$ Nicely done, the (c+d)%b is very efficient in eliminating 3 possibilities at once. $\endgroup$
    – xnor
    Jul 4, 2015 at 9:12
6
$\begingroup$

11 operations

(d+d+d+b%a)%(a+b+c+b*b%d+a)

This was a simple idea that got messy. It can probably be made cleaner.

Note that the numbers 1,2,3,4,5 add to 15, so if we could use constants and subtraction, we could do

15-(a+b+c+d)

We can sort-of simulate subtraction using mod because x%y equals x-y whenever $y \in \left(x/2 ,x \right]$. We can ensure this condition holds by instead doing (x+c)%(y+c) for some sufficiently large $c$.

So, the thing that remains is to create the constant $15$. This part is messy and uses surprisingly many operations. After some experimenting, I found that a-b%a always equals $1$, but adding it $15$ times is too costly. Also, b*b%d equals $(4,4,4,4,0)$ for the five cases, while d equals $(5,5,5,5,4)$, so (d+d+d+d)-(b*b%d) equals $(16,16,16,16,16)$. Subtracting the $1$-vector from before gives $(15,15,15,15,15)$.

At this point, we have the expression

(d+d+d+d-b*b%d-a+b%a)-(a+b+c+d)

Moving the minuses to make them plusses gives

(d+d+d+d+b%a)-(a+b+c+d+b*b%d+a)

Finally, cancel a +d from both sides, and change the - to a %, which turns out to works because both sides are large enough to get the solution

(d+d+d+b%a)%(a+b+c+b*b%d+a)

A near-miss is to "estimate" $15$ as d+d+d, which gives $(15,15,15,15,12)$, and then

(d+d+d)%(a+b+c+d)

gives $(1,2,3,4,2)$, as does

(d+d)%(a+b+c)

I still haven't found a short way though to change the $2$ to a $5$ in the last case.

$\endgroup$
1
  • $\begingroup$ Looks like xnor has nailed it again! :-D $\endgroup$ Jul 3, 2015 at 23:49
2
$\begingroup$

Number of operations: 33.

\begin{align*}f(x_1,x_2,x_3,x_4) = \,\,\, &x_2\setminus x_1 +\\ &(x_4\setminus (x_1+x_2)) * (x_2\setminus (x_1+x_1)) * (x_4\setminus x_2) +\\ &((x_2*x_3*x_4)\setminus (x_1+x_2)) * (x_1+x_2) +\\ &(x_4\setminus (x_4\setminus x_3)) * x_2 * x_2 +\\ &(x_4\setminus (x_1+x_2)) * ((x_4\setminus (x_1+x_1+x_1+x_1+x_1))\setminus x_3) * (x_2+x_3) \end{align*}

You can verify that for the $n$th input, all lines expect the $n$th one will be zero, while the $n$th line will equal $n$.

Here is the same function written in Python so it's easier to verify:

def f(a,b,c,d):
return b%a +\
        (d%(a+b))*(b%(a+a))*(d%b) +\
        ((b*c*d)%(a+b))*(a+b) +\
        (d%(d%c))*b*b +\
        (d%(a+b))*((d%(a+a+a+a+a))%c)*(b+c)
print [f(2,3,4,5),f(1,3,4,5),f(1,2,4,5),f(1,2,3,5),f(1,2,3,4)]
$\endgroup$
3
  • $\begingroup$ A worthy first entry. We'll see if the record holds. ;) $\endgroup$
    – COTO
    Jul 3, 2015 at 22:03
  • $\begingroup$ @COTO "A simple challenge"??!! :-o $\endgroup$ Jul 3, 2015 at 22:28
  • $\begingroup$ @randal'thor: Simple...ish. ;) $\endgroup$
    – COTO
    Jul 3, 2015 at 23:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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