Do you consider writing this program a bit of a challenge?

In summary, the conversation discusses the difficulty of writing a program that takes 3 integer inputs and orders them in ascending order, using only if statements. The use of a "sort" function is mentioned, but the difficulty of the task is debated, especially for those with little math background. The book "Programming principles and practice using C++" by Bjarne Stroustrup is referenced, along with the recommendation of the book "Starting out with C++ from control structures to Objects" by Tony Gaddis. The conversation ends with a discussion of the swapping of numbers issue and the challenge of writing the program without using a temporary variable.
  • #1
Hacker Jack
10
14
TL;DR Summary
Write a program that takes 3 integer inputs and orders them in ascending order (accounting for same numbers)
Do you consider writing a program that takes 3 integer inputs and orders them in ascending order (accounting for same numbers) difficult?
You can only use if statements (if, else if, else). I know there is some thing called "sort" that does the tedious work for you but do you find this simple task kind of hard, at least for someone who doesn't have much of a math background and is a beginner programmer.

If you find it easy, write the program down in your preferred language (I would prefer you do it in C++ as that is what I am learning).

It is an exercise from the book "Programming principles and practice using C++" by Bjarne Stroustrup who is the creator of C++. Mixed reviews on the book by others. I found the book by Tony Gaddis "Starting out with C++ from control structures to Objects" and have skimmed through the pages and seems to do better at explaining and simplifying stuff for newbies like me much better.
 
Technology news on Phys.org
  • #2
Closed temporarily for review by the Mentors.

@Hacker Jack -- be prepared to post your own solution to this problem in at least 2 different languages. It would be best if you could compare and contrast your solutions in C and C++ :wink:

(oh, and be sure to use code tags when you post your solutions)

Update -- thread re-opened.
 
Last edited:
  • Like
Likes pbuk
  • #3
Thats great that you learning C++ as its considered a feature rich and hard to learn language.

With respect to your programming challenge its rather like a kindergartener challenging his parents to write the letter Q which requires some motor skills to accomplish while the parent may do it but realizes this is child’s play.

The three number sort brings out the swapping of nunbers issue which often trips up beginning programmers.

Swap x with y

X=1
Y=2

T=X // where T is a temp variable
X=Y // X value is destroyed and replaced by Y
Y=T // now safely replace the Y with the saved X

Its a popular interview question as trivial as it is but nervous programmers even experienced ones might get it wrong.
 
Last edited:
  • Like
  • Informative
Likes Keith_McClary and Klystron
  • #4
Hacker Jack said:
Summary:: Write a program that takes 3 integer inputs and orders them in ascending order (accounting for same numbers)

Do you consider writing a program that takes 3 integer inputs and orders them in ascending order (accounting for same numbers) difficult?
You can only use if statements (if, else if, else). I know there is some thing called "sort" that does the tedious work for you but do you find this simple task kind of hard, at least for someone who doesn't have much of a math background and is a beginner programmer.

If you find it easy, write the program down in your preferred language (I would prefer you do it in C++ as that is what I am learning).

It is an exercise from the book "Programming principles and practice using C++" by Bjarne Stroustrup who is the creator of C++. Mixed reviews on the book by others. I found the book by Tony Gaddis "Starting out with C++ from control structures to Objects" and have skimmed through the pages and seems to do better at explaining and simplifying stuff for newbies like me much better.
I have been suggesting Gaddis book a few times to you before, it's the only easy book for self study out of the few books I have. Make sure you have the CD that comes with the book, you are going to need it later on.

You should actually post the program that you are asking so we can look at the program. The way I do this is typing
C++:
 copy your program here.
. the forum will convert to the format like you have in your compiler. It is not showing like this, just hit reply and you'll see.BTW, I am so glad now I am NOT the GREENEST one here.
 
  • Like
  • Haha
Likes sysprog, Hacker Jack and berkeman
  • #5
jedishrfu said:
Thats great that you learning C++ as its considered a feature rich and hard to learn language.

With respect to your programming challenge its rather like a kindergartener challenging his parents to write the letter Q which requires some motor skills to accomplish while the parent may do it but realizes this is child’s play.

The three number sort brings out the swapping of nunbers issue which often trips up beginning programmers.

Swap x with y

X=1
Y=2

T=X // where T is a temp variable
X=Y // X value is destroyed and replaced by Y
Y=T // now safely replace the Y with the saved X

Its a popular interview question as trivial as it is but nervous programmers even experienced ones might get it wrong.

Followed by “now do it without a Temp variable.”
 
  • Like
Likes jedishrfu
  • #6
DavidSnider said:
Followed by “now do it without a Temp variable.”
Is indirection allowed?
 
  • #7
Sure. Next question, what if it’s not allowed?
 
  • #8
For whatever it's worth. I write notes as I study along the Gaddis book 6th edition BRIEF version. You can find the pdf file on line. I put the page number in my notes so you can refer back to the book where my notes came from. I finished 14 chapters, only chapter 15 is not there.

It's not written for anyone else but me, so you might find it hard to read. But what do you have to lose. You might find it helpful. When I write programs, I literally refer to the notes for the syntax.

If you have questions, also go to youtube and try to find a video for your topic. I find it most useful having a person actually talk to you step by step. I know people here will strongly disagree with me, I don't find googling and read from sites like geektogeek, cplusplus etc. very helpful for very beginners at all. They use a lot of terms that we beginners don't quite get, then a lot of times, they explain things using examples with more advanced function and syntax that a beginner won't understand.

I was struggling so bad reading those sites, then came here and people told me why didn't I go on line to read before asking. They are like RUSSIAN to me the first few months, it's not until I studied to like chapter 12 before I started to find those sites useful.

Hope that give you a starting point. I was in your boat just 5 months ago!
 

Attachments

  • Gaddis notes.docx
    1.2 MB · Views: 247
Last edited:
  • #9
DavidSnider said:
what if it’s not allowed?

Use a language that does it for you, like Python. :wink:

Python:
x, y = y, x
 
  • Like
  • Haha
Likes atyy and jedishrfu
  • #10
PeterDonis said:
Use a language that does it for you, like Python. :wink:

Python:
x, y = y, x

That’s entirely too sensible. Are you sure you’re here for the programming position?
 
  • #11
DavidSnider said:
That’s entirely too sensible. Are you sure you’re here for the programming position?

Programming position? I thought I was interviewing for upper management. :wink:
 
  • #12
DavidSnider said:
Followed by “now do it without a Temp variable.”
std::swap(a,b);
 
  • #13
It's a pity that the following doesn't work. Especially since it is a model of clarity.

a>b?a:{a+=b;b-=a;a-=b};a>c?a:{a+=c;c-=a;a-=c};b>c?b:{b+=c;c-=b;b-=c};
 
  • Haha
Likes DaveC426913, Filip Larsen, pbuk and 1 other person
  • #14
One could always do the Abbott and Costello routine by handing the x value to the interviewer do some hand waving while you move the y value into x and then take back the x value from the interviewer and drop it on y.

Tell them this is Agile programming.
 
  • Haha
Likes harborsparrow and DaveC426913
  • #15
DavidSnider said:
Followed by “now do it without a Temp variable.”

okay okay, I’ll use a different name like Z.
 
  • Haha
Likes harborsparrow
  • #16
DavidSnider said:
Followed by “now do it without a Temp variable.”
As posted previously (#12), you could use
std::swap(a,b);

and if using the 'swap' function isn't allowed, you could do it this way:
if (a != b){a = a ^ b; b = a ^ b; a = a ^ b;}

or similarly:
if (a != b){(a ^= b), (b ^= a), (a ^= b);}

(ensuring inequality before doing the swap is a precaution in case e.g. the variables are pointers that both reference the same location).
 
  • #17
sysprog said:
(ensuring inequality before doing the swap is a precaution in case e.g. the variables are pointers that both reference the same location).
Shouldn't matter what their content is, the xor operations let them end up being the same as before. Bit operations on pointers are questionable in general, however.
 
  • #18
mfb said:
sysprog said:
(ensuring inequality before doing the swap is a precaution in case e.g. the variables are pointers that both reference the same location).
Shouldn't matter what their content is, the xor operations let them end up being the same as before. Bit operations on pointers are questionable in general, however.
From: https://en.wikipedia.org/wiki/XOR_swap_algorithm#The_algorithm
PseudocodeIBM System/370 assemblyx86 assembly
X := X XOR YXR R1,R2xor eax, ebx
Y := Y XOR XXR R2,R1xor ebx, eax
X := X XOR YXR R1,R2xor eax, ebx

However, the algorithm fails if x and y use the same storage location, since the value stored in that location will be zeroed out by the first XOR instruction, and then remain zero; it will not be "swapped with itself". This is not the same as if x and y have the same values. The trouble only comes when x and y use the same storage location, in which case their values must already be equal. That is, if x and y use the same storage location, then the line:

X := X XOR Y

sets x to zero (because x = y so X XOR Y is zero) and sets y to zero (since it uses the same storage location), causing x and y to lose their original values.
I made minor edits to the Wikipedia article ##-## among the edits was insertion of the underlined (not underlined in the Wikipedia article) part below:

However, in the pseudocode or high-level language version or implementation, the algorithm fails if x and y use the same storage location,​
If the two registers have the same content, XR R1,R2 will zero out R1, and will leave R2 unchanged, so the failure denoted does not occur in the illustrated assembly language code.
 
Last edited:
  • #19
Ah, you want to swap the referenced value(s), not the pointers themselves.
 
  • #20
berkeman said:
Closed temporarily for review by the Mentors.
Update -- thread re-opened.
And since the OP (@Hacker Jack) has been on the forum as recently as an hour ago, still without showing any effort or even commenting on the responses, perhaps it's time to close it again?
 
  • #21
Sorry dawg I am reading the answers but don't really like to reply back unless I have a question but the way this thread and others dive into other deeper topics I don't know what they are talking about so another reason I don't reply. My question has been answered I guess but I just let people keep talking about whatever they are talking about. Sorry about that.
 
  • Like
Likes phinds
  • #22
Hacker Jack said:
Sorry dawg I am reading the answers but don't really like to reply back unless I have a question but the way this thread and others dive into other deeper topics I don't know what they are talking about so another reason I don't reply. My question has been answered I guess but I just let people keep talking about whatever they are talking about. Sorry about that.

As far as your question is concerned, nobody's going to help you until you take a shot at it, yourself. Forum rules. It is not a difficult problem, nor one that produces difficulties. Just, take a pen and paper (or the modern equivalent, thereof) and putter about until you have something that works. Then check it.
 
  • #23
mfb said:
Ah, you want to swap the referenced value(s), not the pointers themselves.
When we are specifying a generic swap in C++, and we are not necessarily sure what is being swapped, the prior precaution (ensuring inequality before doing the swap is a precaution in case e.g. the variables are pointers that both reference the same location) is not unreasonable.

In the case of e.g. a tag sort of lengthy records, instead of swapping the records themselves, we create an array of tags/keys/pointers to the records, and swap those instead of the records themselves, and then write the records in sorted order.

In IBM mainframe assembly language, the register swap ##-##

XR R1,R2
XR R2,R1
XR R1,R2

##-## is fine for swapping register-length pointers to records; to swap the records themselves, we would use ##-##

XC A,B
XC B,A
XC A,B

##-## and neither of those would pose a problem if the two XORed objects were to start out with equal values ##-## as you pointed out, if they were to start out equal, then they would wind up equal.

The precaution of ensuring inequality prior to doing the swap was for the HLL case described.
 
Last edited:
  • #24
A further elaboration:

From the IBM System/370 Principles of Operation manual:
1608728403801.png

From the Notes for that section of that manual:
4. A field EXCLUSIVE ORed with itself is cleared to zeros.

The example refers to two different memory locations ##-## if the two operands were to reference the same memory location, the first of the three XC instructions would zero out that location, and so, superfluously, would the second and the third of them, there being only one location referenced to begin with ##-## hence the precaution of ensuring inequality prior to doing the swap ##-## the three-XOR swap technique cannot be used for the purpose of inplace swapping of a value with itself ##-## XORing something against itself always results in a value of zero.
 
Last edited:
  • #25
1608733008706.png

Hacker Jack said:
Sorry dawg
:oldlaugh:
 
  • #26
sysprog said:
if the two operands were to reference the same memory location

I agree that if a and b are two variables sharing one memory address, this algorithm breaks. But it's not peculiar to this: pretty much every algorithm will break if ++a also increments b. So I am not so sure why it's being emphasized here.

Also, while doing an in-memory swap is kind of cute and clever, in real life avoiding a temp variable (for that matter, avoiding std::swap) is kind of silly. It saves 0.00000001% of system memory, provided that the compiler doesn't optimize it away for you. Elsewhere we have someone refusing to use std::string because it uses a few bytes more than a C string. This has caused no end of grief, and saves only a little bit of a resource there is plenty of.
 
  • Like
Likes Merlin3189 and sysprog
  • #27
Vanadium 50 said:
I agree that if a and b are two variables sharing one memory address, this algorithm breaks. But it's not peculiar to this: pretty much every algorithm will break if ++a also increments b. So I am not so sure why it's being emphasized here.

Also, while doing an in-memory swap is kind of cute and clever, in real life avoiding a temp variable (for that matter, avoiding std::swap) is kind of silly. It saves 0.00000001% of system memory, provided that the compiler doesn't optimize it away for you. Elsewhere we have someone refusing to use std::string because it uses a few bytes more than a C string. This has caused no end of grief, and saves only a little bit of a resource there is plenty of.
The challenge “now do it without a Temp variable.” was posed by @DavidSnider, and in a 'you can use three-XOR swap' response, I said why I had included a check for inequality, and a response by @mfb seemed to me to call for further expanation regarding why I thought that the check was appropriate.
 
  • #28
Here is a way to do it without using any temporary variables, or swaps, or if statements. I wonder what it will look like for 4 variables.
C:
    cout <<      
        (a<=b)*(a<=c)*a
      + (b< a)*(b<=c)*b
      + (c< a)*(c< b)*c << ","
     << ((a<=b)+(a<=c))*((a> b)+(a> c))*a
      + ((b< a)+(b<=c))*((b>=a)+(b> c))*b
      + ((c< b)+(c< a))*((c> b)+(c>=a))*c
      + (a>c)*(b==c)*b << ","
     << (a>=b)*(a>=c)*a
      + (b> a)*(b>=c)*b
      + (c> b)*(c> a)*c << endl;
 
  • #29
A similar alternative is

Code:
a = a + b
b = a - b
a = a - b

If you start a = 15 and b = 8, a becomes 23, then b becomes 15. and then a becomes 8.

The advantage of XOR is that it works with the full range of integers without risk of overflow. It, like XOR, fails spectacularly if a and b share the same location in memory.
 
  • Like
Likes phinds, sysprog and hmmm27
  • #30
Vanadium 50 said:
Elsewhere we have someone refusing to use std::string because it uses a few bytes more than a C string. This has caused no end of grief, and saves only a little bit of a resource there is plenty of.
It is the recurring theme of deprecated legacy skills. Who remembers the days of optimizing program overlays via clever use of the linking loader? Who remembers the days of data overlays via different FORTRAN COMMON declarations in different parts of the program? At one point in time, those kinds of tricks were needed to shoehorn big programs into small spaces. But then technology makes the spaces bigger so some skills earned by sweat and tears become deprecated.
Engineering tradition is based on the model that the more experience you have, the more valuable you become. Salary goes up with age. But in software development, deprecated experience can have negative value. That causes deep resentment and resistance to change among senior members, and rebellion if you suggest that their salaries should go down with age.

For example when I started, RAM memory cost $1/bit, and an engineer with a BS degree cost $8K/year. Therefore, if you wrote a program that would sell 100 copies, saving one byte of memory was worth 20 man days of engineering time.

Those economics were IMO, the cause of most of the evil spaghetti code written in that era. If spaghetti code could eliminate one long statement from the program, it was worth a man year's time. But it was fantasy, because many of those spaghetti programs wound up being longer, not shorter.

The only way to survive decades of technical revolution, was to self-deprecate your old skills and ravenously embrace the latest advances. Some did, some moved into management roles, many didn't.
 
  • Like
Likes Merlin3189, atyy, pbuk and 2 others
  • #31
You forgot self-modifying code. That was the best!
 
Last edited:
  • Like
Likes anorlunda
  • #32
Vanadium 50 said:
You forgot self-mofifying code. That was the best!
Wow, @Vanadium 50, that brings back memories ##-## in the mid-'80s I was working as a mainframe systems engineer for a manufacturer of 'IBM mainframe clones' ##-## Gene you-know-who was the founder of the company ##-## we had a problem, in that our otherwise plug-to-plug compatible product, in the running of a particular database product (known as Model nnn ##-## you presumably know the nnn digits) ran fine on the IBM box, but ran extremely slowly on ours ##-## we had a pipelined processor ##-## the Mnnn code called subroutines sometimes hundreds of levels deep ##-## the code was 'optimized' so that a calling routine would modify the STM instruction at the start of the subroutine to save only the registers the contents of which it anticipated would be actually modified in the subroutine ##-## that meant that our machine had to flush the pipeline, etc., and it was a bit of a nightmare ##-## fortunately, the Mnnn vendor had an option to compile/assemble without the STM optimization, and that allowed our customers to carry on well enough . . .
 
  • Like
  • Informative
Likes hmmm27 and anorlunda
  • #33
I actually met Gene Amdahl as a young man. Twice, in fact. Spooky smart.

Never used x204 or whatever you were talking about. Did use DB2 in its early days, before going on to grad school. Even then I could see the writing was on the wall for mainframes as they existed in the 80's. A 3090 or 5060 was ~100x as fast as a single 8087 chip. But it cost a few million dollars and not a few hundred.
 
  • Like
Likes anorlunda and sysprog
  • #35
Vanadium 50 said:
You forgot self-modifying code. That was the best!
Oh yes, I once encountered a page of Cobol dense with the infamous ”alter goto”, which did just what the name suggests. No comments or doc of any kind, of course.
 
  • Wow
  • Like
Likes Vanadium 50 and sysprog

Similar threads

  • Programming and Computer Science
2
Replies
69
Views
5K
  • Programming and Computer Science
2
Replies
54
Views
4K
  • Programming and Computer Science
3
Replies
81
Views
5K
  • Programming and Computer Science
Replies
2
Views
1K
Replies
9
Views
1K
Replies
6
Views
1K
  • Programming and Computer Science
Replies
8
Views
2K
  • Programming and Computer Science
Replies
2
Views
1K
  • Programming and Computer Science
Replies
17
Views
4K
  • Programming and Computer Science
Replies
5
Views
5K
Back
Top