Little Red Solving Hood goes one-stop swapping

Question

Moral of the story:

  Two stored values may be swapped arithmetically with 4 or fewer variable references.

Puzzle of the story:

  Can you exemplify the moral?   (With 10 or fewer symbols in all.)

The story:

  Once upon a puzzle there was a dear little user— affectionately called Little Red Solving Hood by the villagers — who was sent to Grandparent’s house with a basket of goodies that included a couple of real numbers, X and Y, as variables with stored values that could be revised.

The basket was unbalanced, though, so Little Red stopped along the path outside Bit Bad Wolf’s Swapadero to exchange the numbers’ values.   Bit Bad Wolf’s big mouth flashed a big bad smile.

  “Why don’t you step inside and just let me swap those numbers without moving either one.” $\require{begingroup}\begingroup \def \K { \kern-.6em } \def \_ #1{ \kern1em \raise-.5ex{\underline{\kern1em \raise.5ex{#1} \kern1em}} \kern1em } \def \* {{\oplus }} \def \X {{ \sf X}} \def \x {{\sf\normalsize \unicode {120377}}} \def \Y {{ \sf Y}} \def \y {{ \sf\normalsize \unicode{120378}}} \def \= #1{ \rlap{\raise1.3ex{~~~\,{#1}\,}} ~~ \gets ~~ } \def \( { \raise .5ex{ \big( } } \def \) { \raise.5ex{ \big) } } $ $$ \small\sf\begin{array}{c} \sf Action && \sf Variable && \_{\X} &\_{\Y}\\[-1ex] &&\sf\raise-.5ex{references}&& & \\[-1ex] && && \x & \y \\[.2ex] \X \=~ \X\,\*\,\Y && \sf 3 &&\x\,\*\,\y & \y \\[.2ex] \Y \=~ \X\,\*\,\Y && \sf 3 && \x\,\*\,\y & \x \\[.2ex] \X \=~ \X\,\*\,\Y&& \sf \_3 && \y & \x \\ && \sf 9 && & \end{array} \kern-2.5em $$

You see, the wolf had recently digested a computer- related article about using $\small\oplus$ (exclusive-or).

  “And if 9 variable references are too many for sweet little delicious you, how about 6?”

$$ \small\sf\begin{array}{c} \sf Action && \sf Variable && \_{\X} &\_{\Y}\\[-1ex] &&\sf\raise-.5ex{references}&& & \\[-1ex] && && \x & \y \\[.2ex] \X \=\* \Y && \sf 2 &&\x\,\*\,\y & \y \\[.2ex] \Y \=\* \X && \sf 2 && \x\,\*\,\y & \x \\[.2ex] \X \=\* \Y && \sf \_2 && \y & \x \\ && \sf 6 && & \end{array} \kern-4em $$

The wolf thought that $\small\rlap{\raise1.3ex{\,~\oplus}}\gets$  (self-revising augmented assignment) might catch Little Red unawares; each action had exactly the same effect as before, merely with fewer scary symbols and variable references.   But Little Red Solving Hood had a smart little mouth and mind.

  “Eat bits and die, Bad Wolf. That’s for binary numbers, which need only 4 references anyway.”

$$ \small\sf\begin{array}{c} \sf Action && \sf Variable && \_{\X} & \_{\Y} \\[-1ex] &&\sf\raise-.5ex{references}&& & \\[-1ex] && && \x & \y \\[.2ex] \X \=\* \Y \=\* \X \=\* \Y && \sf \_4 && \y & \x \\ && \sf 4 && & \end{array} \kern1.7em $$

Bit Bad Wolf nodded sheepishly. After all, these assignments follow right-associative precedence.

$$ \small\sf \X \=\* \Y \=\* \X \=\* \Y \qquad {\Large \equiv} \qquad \X \=\* \( ~ \Y \=\* \( ~ \X \=\* \Y ~ \) ~ \) \kern3.1em $$

  “Besides, all the goodies I need can be found in the basket.”

$$ \small \= ~ \K \= ~ \K \= ~ ~ \= + \K \= + \K \= + ~ \= - \K \= - \K \= - ~ \=\times \K \=\times \K \=\times ~ \=\div \K \=\div \K \=\div \raise-2ex\strut \kern2.8em \\ \small ~~~ + ~~ + ~~ + ~~~ - ~~ - ~~ - ~~~ \times ~~ \times ~~ \times ~~~ \div ~~ \div ~~ \div \sf ~~~~ 0 ~~ 1 ~~ 2 ~~ 3 ~~ 4 ~~ 5 ~~ 6 ~~ 7 ~~ 8 ~~ 9 \kern3.8em $$

With that, Little Red swapped the values of X and Y by constructing a formula with 4 total variable references (only to X and /or Y, like the wolf’s designs) along with 6 goodies from those just listed.

  “Oh my! What a big frown you have, Wolfie,” jeered our sweet little user before skipping off.

   With what little formula did Little Red Solving Hood swap those values of X and Y?

$\endgroup$

Answer 1

The swap can be done with 4 references using 6 "goodies" as follows:

$\def \= #1{\rlap{\raise1.3ex{~~~#1}} ~~ \gets ~~ }\small\bf X \=- Y \=+ X \=- Y \=\times -1$

Breaking it down:

$$\def \= #1{\rlap{\raise1.3ex{~~~#1}} ~~ \gets ~~ }\small\begin{array}{lllr}\textbf{Original:}&\Space{2em}{0pt}{0pt}&\bf X&\bf Y\\\bf Y \=\times-1&&\bf X&\bf -Y\\\bf X \=-Y&&\bf X+Y&\bf -Y\\\bf Y \=+X&&\bf X+Y&\bf X\\\bf X \=-Y&&\bf Y&\bf X\\\end{array}$$

---

Approach to the problem:

1) With only 4 variable references allowed, the most we can do is three variable-to-variable augmented assignments.
2) The intermediate steps need to have a combination of both original values held in one of the variables, so no information is lost.
3) Reciprocal operations (+ and -, or * and /) can be used to convert to and from "single" to "combination" values and back.

Using the above observations, I started looking for ways to do this, and noticed that:

Using alternating += and -= augmented assignment, the values were appropriately swapped, but one of the values was negated. The same was true for *= and /=, but one value was inverted.

The final step:

So, we need to negate one of the values. With all 4 variable references already used, as well as three augmented assignments, only three goodies are left to play with. And - and 1 both count as goodies, leaving a single operator... it better be another augmented assignment! Since augmented assignment requires an l-value, multiplying by -1 at the "end" of the chain doesn't work, because -1 *= y is illegal. The only legal way is to negate one of the values first, by multiplying or dividing by -1.

Other alternatives would have been possible if the goodie bag contained

An augmented power assignment (^=) so that the first step could take the reciprocal of one of the variables (e.g. X ^= -1). In this case, a multiply-and-divide strategy could work (but if done on a computer instead of by hand, could be less optimal due to precision errors).