Quantcast

Maximum PC

It is currently Wed Jul 30, 2014 5:52 am

All times are UTC - 8 hours




Post new topic Reply to topic  [ 16 posts ] 
Author Message
 Post subject: Swapping Doubles
PostPosted: Thu Oct 14, 2004 12:50 am 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
So you have two doubles, d1 and d2, that are initialized to the values of PI and E, respectively. Your program needs to swap the values so that d1 is E and d2 is PI. Simple enough right?

Oh, almost forgot, there's a bit of a catch. These are the only two variables that you can declare in your program. Yep, d1 and d2. That's it. Feel free to use any language. I'd love to see solutions in languages other than C++ and Java, especially C#, Python, Perl, VB and PHP.

BTW, a 'harder' solution does not use a pointer or reference of any kind either. A 'simple' solution does - I'll let others quible over whether a pointer or refernce should be considered a variable. If you don't get the hard solution, go ahead and post the simple one. I'll post both in a couple of days.

Backstory: Our local ACM chapter is preparing for the ACM Regional contest and one of my teammates thought he could stump me this morning with this problem. He is Chineese w/ an accent and crazy laugh.... "Larry, I can do this in C++, but you could never do this in Java. <smiles>Cause it is impossible to do it in Java!<crazy loud laugh - 2 minutes, 110 db, I'm not kidding>." I sat down for a minute and the simple solution took me about 3 minutes to which he carried on about the use of a reference. I had to take care of some business today, and while I was at the bank of all places, the answer occured to me and I implemented the 'hard' solution in 2 working lines of code (1 for declarations and one for the swapping). I taped the solution on the 'Problem of the Day' whiteboard. I can't wait to see his face in the morning. :D

Good luck and, if stumped, try going to the bank. ;)


Top
  Profile  
 
 Post subject:
PostPosted: Thu Oct 14, 2004 9:52 am 
Java Junkie
Java Junkie
User avatar

Joined: Mon Jun 14, 2004 10:23 am
Posts: 24222
Location: Granite Heaven
The simple solution is to swap the pointers from one to another ... if you are allowed to create a temporary pointer for the swap. Right?

The harder solution ... pass the variables (by value) to a method and swap them there. Since the method will create local variables to contain the passed arguments (ie., you don't declare these variables ... they are created by the method) ... you can swap them using the two local variables and calls to the original global variables d1 and d2.

I haven't had much coffee yet ... I could be wrong. :) And I realise I am taking some license with the 'don't declare more than 2 variables' rule. ;)

Pseudocode:

Code:
...
double d1 = pi, d2 = e;
swap (d1, d2);

void swap (double a, double b) {

   d1 = b;  d2 = a;
   // the syntax of this 'swap' will depend on the language chosen and how
   // it deals with passing values to and from methods.
}


The most intuitive way to perform that swap would be to swap the pointers of the global variables .. again, this depends on the language chosen.

This feels like cheating, though ... 'cause I do use two more variables ... I just don't declare them. ;)


Top
  Profile  
 
 Post subject:
PostPosted: Thu Oct 14, 2004 1:08 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Jipstyle wrote:
The simple solution is to swap the pointers from one to another ... if you are allowed to create a temporary pointer for the swap. Right?

That could be a bit of a trap. Remember, the idea is to swap the values, not pointers. You should only need one. I did the simple using a Double reference.

Jipstyle wrote:
The harder solution ... pass the variables (by value) to a method and swap them there. Since the method will create local variables to contain the passed arguments (ie., you don't declare these variables ... they are created by the method) ... you can swap them using the two local variables and calls to the original global variables d1 and d2.

Nope. Two variables total. The entire program. ;)

Jipstyle wrote:
And I realise I am taking some license with the 'don't declare more than 2 variables' rule. ;)

Some?! :D :shock:


Top
  Profile  
 
 Post subject:
PostPosted: Thu Oct 14, 2004 6:22 pm 
Team Member Top 100
Team Member Top 100

Joined: Fri Sep 17, 2004 5:35 pm
Posts: 1176
I came up with two easy methods, one really cheap and not really suitable and one realistic, and another one that only takes one line but is hard to read:
Code:
#include <iostream> //function definition

#define PI 3.14159
#define EULER 2.71828
//we need to know the values of Pi and e
//I prefer #defines to const ints, but whatever

void cheap_swap(double& d1, double& d2)
{
   //d1 MUST BE pi, d2 is e

   d2*=d1;//e * pi
   d1=d2;//both have the same value
   d2/=EULER;//now d2 is pi
   d1/=PI;//now d1 is e
}

void hard_swap(double& d1, double& d2)
{
   //we don't know which is which and we don't even know the values of each
   d1*=d2;//d1 is product, d2 is 2nd number
   d2=d1 / d2;//now d1 is product, d2 is the swap
   d1/=d2;//now we have swapped
}

void obfuscated_swap(double& d1, double& d2)
{
   //this name has a meaning!
   d1 = d1 / (d2 = (d1 = (d1*d2))/d2);
   //step by step:
   //1.) d1 is assigned the product of the two numbers
   //2.) d2 equals the product of the two numbers divided by the second number; therefore d2 is now the first number
   //3.) d1 is reassigned as the product of the numbers divided by the first number; therefore d1 is now the second number.
}

int main()
{

   double d1=PI, d2=EULER;

   cheap_swap(d1, d2);
   std::cout << "d1: " << d1 << " d2: " << d2 << std::endl;
   //do the cheap swap

   d1=PI, d2=EULER;//reassign
   
   hard_swap(d1, d2);
   std::cout << "d1: " << d1 << " d2: " << d2 << std::endl;
   //do the hard swap

   d1=PI, d2=EULER;//reassign
   
   obfuscated_swap(d1, d2);
   std::cout << "d1: " << d1 << " d2: " << d2 << std::endl;
   //do the obfuscated swap

   std::cin.get();//pause for us
}

Sorry it's in C++ though.


Last edited by Kybo_Ren on Thu Oct 14, 2004 8:41 pm, edited 1 time in total.

Top
  Profile  
 
 Post subject:
PostPosted: Thu Oct 14, 2004 7:34 pm 
Java Junkie
Java Junkie
User avatar

Joined: Mon Jun 14, 2004 10:23 am
Posts: 24222
Location: Granite Heaven
Gadget wrote:
Jipstyle wrote:
And I realise I am taking some license with the 'don't declare more than 2 variables' rule. ;)

Some?! :D :shock:


:lol: Hey ... *I* didn't declare a new variable. I blame the method! :P


Top
  Profile  
 
 Post subject:
PostPosted: Fri Oct 15, 2004 9:03 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Kybo_Ren wrote:
Code:
void cheap_swap(double& d1, double& d2)
{
   //d1 MUST BE pi, d2 is e

   d2*=d1;//e * pi
   d1=d2;//both have the same value
   d2/=EULER;//now d2 is pi
   d1/=PI;//now d1 is e
}

Haha... nice one, and yes, cheap seems like an appropriate term. :)

BTW, if you're going to use defines, why not just do a d1 = pi and d2 = e directly instead?!

Kybo_Ren wrote:
Code:
void hard_swap(double& d1, double& d2)
{
   //we don't know which is which and we don't even know the values of each
   d1*=d2;//d1 is product, d2 is 2nd number                 
   d2=d1 / d2;//now d1 is product, d2 is the swap         
   d1/=d2;//now we have swapped                               
}

Hmm.... I actually hadn't thought of this method which works if you're willing to throw away some rounding errors. Nice. A new method is added to the list.

Here's a big hint for the 'hard' solution....

Code:
1110    #d1
1001    #d2
0111
1110
1001


Top
  Profile  
 
 Post subject:
PostPosted: Fri Oct 15, 2004 9:45 pm 
Bitchin' Fast 3D Z8000
Bitchin' Fast 3D Z8000
User avatar

Joined: Mon Jun 14, 2004 4:04 pm
Posts: 985
Location: Earth
Gadget wrote:
Here's a big hint for the 'hard' solution....

Code:
1110    #d1
1001    #d2
0111
1110
1001


So did you XOR'ed d1 and d2:

Code:

  void hard_swap(int &d1, int &d2) {

      d1 = d1 ^ d2;
      d2 = d2 ^ d1;
      d1 = d1 ^ d2;
   }



Is this right?


Top
  Profile  
 
 Post subject:
PostPosted: Sat Oct 16, 2004 3:39 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
DJSPIN80 wrote:
Gadget wrote:
Here's a big hint for the 'hard' solution....

Code:
1110    #d1
1001    #d2
0111
1110
1001


So did you XOR'ed d1 and d2:

Code:

  void hard_swap(int &d1, int &d2) {

      d1 = d1 ^ d2;
      d2 = d2 ^ d1;
      d1 = d1 ^ d2;
   }



Is this right?

That is close.... you have a couple of issues to deal with still though. The ^ operator isn't going to like doubles for one thing. ;)


Top
  Profile  
 
 Post subject:
PostPosted: Sat Oct 16, 2004 5:43 pm 
I judge you GUILTY!
I judge you GUILTY!
User avatar

Joined: Tue May 25, 2004 4:38 pm
Posts: 162
Location: New York City
What's the point?
Unless you're limited in memory and space, (like embedded programming) resorting to such tricks is pointless with today's optimising compilers.
Err, I am not british-- optimizing


Top
  Profile  
 
 Post subject:
PostPosted: Thu Oct 21, 2004 8:45 am 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Dude-X wrote:
What's the point?
Unless you're limited in memory and space, (like embedded programming) resorting to such tricks is pointless with today's optimising compilers.
Err, I am not british-- optimizing

True. But isn't that a little like asking, what is the point of learning assembly language, ISA's or anything but high-level languages because an optimizing compiler will handle these details anyways? Of course, someone has to write these automagick compilers and libs that we take for granted.

Just a little puzzle problem to keep the brain sharp.... if not, we'll eventually become VB programmers. Horror. :)


Top
  Profile  
 
 Post subject:
PostPosted: Thu Oct 21, 2004 5:38 pm 
I judge you GUILTY!
I judge you GUILTY!
User avatar

Joined: Tue May 25, 2004 4:38 pm
Posts: 162
Location: New York City
Really, I am just frustrated that I can't solve it.
:p


Top
  Profile  
 
 Post subject:
PostPosted: Thu Oct 21, 2004 6:40 pm 
Bitchin' Fast 3D Z8000
Bitchin' Fast 3D Z8000
User avatar

Joined: Mon Jun 14, 2004 4:04 pm
Posts: 985
Location: Earth
Gadget wrote:
void hard_swap(int &d1, int &d2) {

d1 = d1 ^ d2;
d2 = d2 ^ d1;
d1 = d1 ^ d2;
}

[/code]

Is this right?

That is close.... you have a couple of issues to deal with still though. The ^ operator isn't going to like doubles for one thing. ;)[/quote]


Code:
void hard_swap(double &d1, double &d2) {

      d1 = d1 ^ d2;
      d2 = d2 ^ d1;
      d1 = d1 ^ d2;
   }



There, solved it!!! :? ;) :lol:


Top
  Profile  
 
 Post subject:
PostPosted: Fri Oct 22, 2004 12:22 am 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Dude-X wrote:
Really, I am just frustrated that I can't solve it.
:p

Dude, what's up with the crazy voodoo looking avatar?!


Top
  Profile  
 
 Post subject:
PostPosted: Sat Oct 23, 2004 12:34 pm 
I judge you GUILTY!
I judge you GUILTY!
User avatar

Joined: Tue May 25, 2004 4:38 pm
Posts: 162
Location: New York City
My avatar is a Quintessons from The Transformers.
They are the Enforcers and they enslave both Autobots and Decepticons.
The face that you see is of DEATH.


Top
  Profile  
 
 Post subject:
PostPosted: Sat Oct 23, 2004 7:28 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Dude-X wrote:
My avatar is a Quintessons from The Transformers.
They are the Enforcers and they enslave both Autobots and Decepticons.
The face that you see is of DEATH.

lol... you need to cut back on something. :)


Top
  Profile  
 
 Post subject:
PostPosted: Sun Oct 24, 2004 4:10 pm 
8086
8086

Joined: Mon Aug 02, 2004 10:59 am
Posts: 50
Dang, I wouldn't even have SEEN it without the hint (although the hint did give it away).


Top
  Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 16 posts ] 

All times are UTC - 8 hours


Who is online

Users browsing this forum: No registered users and 3 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group