12
$\begingroup$

You are given a task to write a program to switch values between variables, but you are not allowed to use any extra variable or any function to exchange values between the other variables as shown below:

int a,b,c,d;

a=A;
b=B;
c=C;
d=D;

.......//only fill this part.

Write(a+" "+b+" "+c+" "+d);

---------------------------- Output -----------------------------

C D B A

while $a,b,c$ and $d$ are integer variable, $A$,$B$,$C$ and $D$ are some random integer values. Your task is to exchange values between these variables without using any extra variable or any function but just fill the blank part with the least amount of lines

putting all operations next to each other as a line is invalid line means

a=a+b+c; a=a/b/c*d;

is two lines, not one line.

Note: You are not even supposed to be programmer to solve this.

Note 2: I forgot to change the value of $b$ since it was intended and for simplicity I have change the letters.

$\endgroup$
  • $\begingroup$ you might want to replace "extra variable" with "any temporary storage". because technically I can write the values to 2 separate files and read from them. $\endgroup$ – Marius Aug 8 '17 at 11:57
  • 1
    $\begingroup$ "(putting all operations next to each other as a line is invalid line)" Is that to say that each line should have only one operation, or that each line should have only one assignment? For example, is the line a=b+c+d; permitted? $\endgroup$ – Apep Aug 8 '17 at 12:16
  • 3
    $\begingroup$ Smart a** answer: a = C; b = D; c = B; d = A. $\endgroup$ – Marius Aug 8 '17 at 14:07
  • 2
    $\begingroup$ Where do we draw the line for what counts as a "function" for exclusion? I don't think of tuple assignment as a function, so I can do it in one line: (a,b,c,d)=(c,d,b,a) $\endgroup$ – Sabre Aug 8 '17 at 15:13
  • 1
    $\begingroup$ RIP immutable data $\endgroup$ – Henry Aug 8 '17 at 18:04
26
$\begingroup$

The shortest number of lines should be

5

This can be done:

// Initial state: a=A; b=B; c=C; d=D a=a+b+c+d; // a = A+B+C+D d=a-b-c-d; // d = (A+B+C+D)-B-C-D = A b=a-b-c-d; // b = (A+B+C+D)-B-C-A = D c=a-b-c-d; // c = (A+B+C+D)-D-C-A = B a=a-b-c-d; // a = (A+B+C+D)-D-B-A = C

$\endgroup$
  • $\begingroup$ Multiplication and division work too as long as none of the entries is zero. Great answer though! $\endgroup$ – user76646 Aug 10 '17 at 0:22
9
$\begingroup$

a = a ^ c
c = a ^ c
a = a ^ c
//the 3 lines above switch a with c and now the order is Z T X Y.
c = c ^ d
d = c ^ d
c = c ^ d
//the 3 lines above switch c with d and now the order is Z T Y X.
b = b ^ c
c = b ^ c
b = b ^ c
//the 3 lines above switch b with c and now the order is Z Y T X.
// ^ is the XOR operator.

Why it works.

XOR is an associative operation
XOR has the identity 0.
a XOR a = 0
based on these rules ... the first a = a ^ c does not do much, but calling it the second time it's like doing (with the initial values)
c = a ^ c ^ c and the 2 c cancel each other and you get c = a (using the initial values).
it works the same for the other associations.

Sneaky approach

at least in PHP you can do this and technically there is no other variable involved and the values are switched.
list($a, $b) = array_reverse([$a, $b]);

$\endgroup$
  • 2
    $\begingroup$ arent list and array_reverse functions? $\endgroup$ – Oray Aug 8 '17 at 12:01
  • $\begingroup$ @Oray Yeah, (@Marius) in other languages like python/js/ruby a, b = b, a or something like that (depends on language) is allowed $\endgroup$ – somebody Aug 8 '17 at 12:51
  • 1
    $\begingroup$ also +1 for XORing, this means the numbers don't overflow/underflow :P $\endgroup$ – somebody Aug 8 '17 at 12:51
  • $\begingroup$ @Oray. Yes, they are. that's why it's not my main answer. $\endgroup$ – Marius Aug 8 '17 at 13:51
3
$\begingroup$

In addition to the classic answer to this puzzle that Marius provided, you could also do this:

Instead of swapping two variables using XOR, you can use subtraction

               // start with  a=A         c=C
 a=c-a         // results in  a=C-A       c=C
 c=c-a         // results in  a=C-A       c=C-(C-A)=A
 a=c+a         // results in  a=C-A+A=C   c=A
You can then do three of these swaps to get the particular permutation needed, as in Marius's answer. Barring rounding errors and overflows, this also works for floating point variables. There are lots of ways to vary the order of additions and subtractions.

The question however asks for the minimum number of lines to do all the rearranging. Here is my answer:

                 // start with  a=A        b=B       c=C      d=D
  a=a-c          // results in  a=A-C      b=B       c=C      d=D
  c=c-b          // results in  a=A-C      b=B       c=C-B    d=D
  b=b-d          // results in  a=A-C      b=B-D     c=C-B    d=D
  d=d+b+c+a      // results in  a=A-C      b=B-D     c=C-B    d=A
  a=d-a          // results in  a=C        b=B-D     c=C-B    d=A
  c=a-c          // results in  a=C        b=B-D     c=B      d=A
  b=c-b          // results in  a=C        b=D       c=B      d=A

$\endgroup$
  • $\begingroup$ I suspect that this is the intended answer, as the core operation of the technique used in @Marius 's answer isn't generally known to non-programmers. $\endgroup$ – Jeff Zeitlin Aug 8 '17 at 12:04
  • $\begingroup$ good start, though for the intended answer, total of lines are less than 9. $\endgroup$ – Oray Aug 8 '17 at 12:10
2
$\begingroup$

I am unable to comment.

Apep's Example also works with XORs.

a = A
b = B
c = C
d = D

a = a^b^c^d

a = ABCD
b = B
c = C
d = D

d = a^b^c^d = (ABCD)^(B)^(C)^(D) = A

a = ABCD
b = B
c = C
d = A

b = a^b^c^d = (ABCD)^(B)^(C)^(A) = D

a = ABCD
b = D
c = C
d = A

c = a^b^c^d = (ABCD)^(D)^(C)^(A) = B

a = ABCD
b = D
c = B
d = A

a = a^b^c^d = (ABCD)^(D)^(B)^(A) = C

a = C
b = D
c = B
d = A

$\endgroup$
0
$\begingroup$

Well, based on Jaap S...s's answer,

Other possibilities arise based on multiplication and divison.

For example, int a,b,c,d;

a=X;
b=T;
c=Z;
d=Y;

a = (a*c) / a and so on for others.

$\endgroup$
  • 4
    $\begingroup$ with this, you will lose the value of a. $\endgroup$ – Oray Aug 8 '17 at 12:15
  • 1
    $\begingroup$ Oray is right, This is just a more complicated way of saying a=c, which means both a and c will equal the same thing. The original value of a disappears, never to be seen again, which makes the required output impossible. $\endgroup$ – Ryan Aug 8 '17 at 19:17
0
$\begingroup$

Lua makes this quite easy...

a,b,c,d = C,D,B,A

$\endgroup$
0
$\begingroup$

The minimum number of lines is 3 (works in Java):

a = c + ( c = a ) - a;
b = d + ( d = b ) - b;
c = d + ( d = c ) - c;
$\endgroup$
0
$\begingroup$

You could always hack your way around this into one line with ternary operators. These little buggers are so useful, that you can get a score of 0 lines. I based this upon the fact that you can do all of this during write time. Of course, you can also say It's 1 line, if separation is a must.

0- Line Solution:

Write( a = a+b+c+d > a ? 0 : d=a-b-c-d > d ? 0 : b=a-b-c-d > b ? 0 : c=a-b-c-d > c ? 0 : a=a-b-c-d > a ? 0 : a+" "+b+" "+c+" "+d);

1-Line Solution:

a = (a = a+b+c+d > a) ? 0 : d=a-b-c-d > d ? 0 : b=a-b-c-d > b ? 0 : c=a-b-c-d > c ? 0 : a-b-c-d;

Explanation:

a = (a equals)    
  a=a+b+c+d (set a equal to a+b+c+d)
  >a? (test if a > a (returns false)) 
    0: (what it returns if true)
    d=a-b-c-d > d ? 0 :  b=a-b-c-d > b ? 0 : c=a-b-c-d > c ? 0 : a-b-c-d; (what it returns if false)

So you can see that it cascades until you hit

c > c ? 0 : a-b-c-d;

In which case it returns a-b-c-d, which gets passed up to a and sets a equal to a-b-c-d

$\endgroup$

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.