Programming Puzzle

[Julie]

The only foolish assumption is that bits behave like water...


If you can do it with unsigned integer types, you can do it with all kinds
of objects, by aliasing them with arrays of unsigned char.

Please describe (in code) a situation where two variables share the same memory
location.

 

[Julie]

You can't really "remove" an element from an array, so this is poorly
defined. If it was a C++ vector (for example) std::sort and
std::unique would render it trivial, as would inserting the elements
into an std::set, and then copying them back out. Doing it quickly
while retaining the original order is a little more challenging.

How can you _not_ remove an element from an array?

Here is a trivial case:

size_t count = 2;
int * array = (int *)malloc(sizeof(int) * count);
array[0] = 42;
array[1] = 9000;
array = (int *)realloc(array, sizeof(int) * (--count));

Are you saying that an element hasn't been removed?

 

[Julie]

int &value, another;
value = another = 9;
value^another = ??;

jive

Sorry, 'value" is not a variable, but an alias (or reference), you only have
one variable there in 'another', even if it did compile.

 

[Howard]

You can't really "remove" an element from an array, so this is poorly
defined. If it was a C++ vector (for example) std::sort and
std::unique would render it trivial, as would inserting the elements
into an std::set, and then copying them back out. Doing it quickly
while retaining the original order is a little more challenging.

How can you _not_ remove an element from an array?

Here is a trivial case:

size_t count = 2;
int * array = (int *)malloc(sizeof(int) * count);
array[0] = 42;
array[1] = 9000;
array = (int *)realloc(array, sizeof(int) * (--count));

Are you saying that an element hasn't been removed?

Well, that's not *really* removing an element from the array, it's simply
reallocating data storage. How would your example look if you wanted to
remove an element from other than the last position? You'd have to write
code to shift the other elements to the front of the array, not just resize
the memory allocation.

-Howard

 

[Julie]

Q7 Remove duplicates in array

You can't really "remove" an element from an array, so this is poorly
defined. If it was a C++ vector (for example) std::sort and
std::unique would render it trivial, as would inserting the elements
into an std::set, and then copying them back out. Doing it quickly
while retaining the original order is a little more challenging.

How can you _not_ remove an element from an array?

Here is a trivial case:

size_t count = 2;
int * array = (int *)malloc(sizeof(int) * count);
array[0] = 42;
array[1] = 9000;
array = (int *)realloc(array, sizeof(int) * (--count));

Are you saying that an element hasn't been removed?

Well, that's not *really* removing an element from the array, it's simply
reallocating data storage.

Well, if that isn't removing, then I don't know what is... Reallocation is
merely an implementation detail, net result is that an element has been
removed.

How would your example look if you wanted to
remove an element from other than the last position? You'd have to write
code to shift the other elements to the front of the array, not just resize
the memory allocation.

Exactly. I started w/ the trivial case of removing the last element. Removing
any other position would merely involve calling memmove or similar to shift the
contents down and then reallocating.

Still sounds like removing an element from an array to me...

 

[Howard]

Please describe (in code) a situation where two variables share the same memory
location.

Just like described, using pointers. (References can also be used.)

void pswap( int* px, int* py )
{
*px = *px ^ ^py;
*py = *py ^ *px;
*px = *px ^ *py;
}

....calling code:...
int x = 3;
int* px = &x;
int* py = &x;
pswap( px, py );


-Howard

 

[Dan Pop]

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Please describe (in code) a situation where two variables share the same memory
location.

Since you seem to be unable to understand plain English:

#include <stdio.h>

void swap(int *p, int *q) { ... }

int main()
{
int i = 10;
swap(&i, &i);
printf("%d\n", i);
return 0;
}

Try this code for different implementations of the swap function, using
a temp var and using in-place swapping. Compare the results.

This example is trivial, but the situation can realistically arise in more
complex algorithms.

Dan

 

[Branimir Maksimovic]

Q10 Write a program whose printed output is an exact copy of the
source. Needless to say, merely echoing the actual source file is not
allowed.

#include <cstdio>
using namespace std;int main(){const char* s="#include <cstdio>%cusing
namespace std;int main(){const char*
s=%c%s%c;printf(s,10,34,s,34,10);}%c";printf(s,10,34,s,34,10);}

Greetings, Bane.

 

[Prateek R Karandikar]

Programming Puzzles

Q3 (the same as the other you mentioned, basically) took me less than
a minute to solve, and I'm only 16:

/* vim:ts=4
*/

#include <stdio.h>

int main(void) {
int foo = 87;
int bar = 56;

foo += bar;
bar = foo - bar;
foo = foo - bar;

fprintf(stdout, "%i, %i\n", foo, bar);
}

Try other values for foo & bar, even negatives and zero.

You mentioned MS often use these sorts of puzzles to test their
programmers. I got an even better one to stump even the best MS
programmers:

/* vim:ts=4
*/

#include <stdio.h>

int main(void) {
int *foo = NULL;

fprintf(stdout, "%i\n", *foo);
}

What will happen if I compile and run this program??

Don't you know that dereferencing the null pointer results in undefined behaviour???

-- --
Abstraction is selective ignorance.
-Andrew Koenig
-- --

 

[Julie]

Just like described, using pointers. (References can also be used.)

void pswap( int* px, int* py )
{
*px = *px ^ ^py;
*py = *py ^ *px;
*px = *px ^ *py;
}

...calling code:...
int x = 3;
int* px = &x;
int* py = &x;
pswap( px, py );

-Howard

Yes, but the two variables are pointers, and they do not share the same memory
location -- they may *point* to the same location.

So, I still haven't seen two variables that share the same memory location. I
think that you can probably do it w/ placement new (C++ only!), but using (C++)
references or pointers, you can't have two variables that share the same memory
location.

 

[Howard]

Yes, but the two variables are pointers, and they do not share the same memory
location -- they may *point* to the same location.

So, I still haven't seen two variables that share the same memory location. I
think that you can probably do it w/ placement new (C++ only!), but using (C++)
references or pointers, you can't have two variables that share the same memory
location.

Geez, give me a break! What I've shown exhibits *exactly* the kind of
problem that can happen when trying to swap two integers using the xor
technique. Just because someone used terminology that suggested the two
variables themselves had the same memory location, surely you knew what was
meant! The problem is when both memory locations are the same, which can
happen if using pointers or references. That's all that was meant, not that
there were two *different* variables occupying the *same* memory.
-Howard

 

[Prateek R Karandikar]

int &value, another;

Not allowed. References must be initialized.

value = another = 9;
value^another = ??;

Not allowed. value^another is an rvalue, not an lvalue.

jive

To the OP:

#include<iostream>
int main()
{
int a;
int &x=a;
std::cout<<std::boolalpha<<((&a)==(&x));
}

-- --
Abstraction is selective ignorance.
-Andrew Koenig
-- --

 

[Julie]

Since you seem to be unable to understand plain English:

#include <stdio.h>

void swap(int *p, int *q) { ... }

int main()
{
int i = 10;
swap(&i, &i);
printf("%d\n", i);
return 0;
}

Try this code for different implementations of the swap function, using
a temp var and using in-place swapping. Compare the results.

This example is trivial, but the situation can realistically arise in more
complex algorithms.

No, I do not understand your version of plain English.

Just because you have two pointers that _point_ to the same address, this
doesn't mean that they (the variables here which are still the **pointers**)
share the same memory location.

Your definition of swap doesn't take to variables, it takes two addresses.
Even in your example in main, you are passing in the same pointer.

Show me a case of two separate variables that share the same memory location,
without using placement new. You can even use your version of 'plain English'.

Here is the point in my version of 'plain English': you can't have two
variables that share the same memory address (excluding placement new). So, if
the precondition for swap is that it operates on two variables, then it will
always work provided the precondition is met.

 

[Tak-Shing Chan]

JKop <[email protected]> scribbled the following

Am I the only person here that thinks it's complete bullshit to think you
can swap the values of two variables without a temporary variable?! It ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
[snip]

And the only good reason I can imagine is the failure to allocate memory
for a temporary object (some objects can be greater than others, some

^^^^^^^^^^^^^^^^^^

Your answer is completely irrelevant. ;-)

Tak-Shing

 

[Howard]

Here is the point in my version of 'plain English': you can't have two
variables that share the same memory address (excluding placement new). So, if
the precondition for swap is that it operates on two variables, then it will
always work provided the precondition is met.

So who ever sid the procondition was that you were swapping two non-pointer,
non-reference variables? If you're writing the swap as a function, you have
to use references or pointers, or else you'll only be swapping local copies.
That's what makes this an important consideration, because those pointer or
references parameters could be referring to the same memory location. The
swap function need to contain a check to handle that specific case.

-Howard

 

[Ioannis Vranos]

How can you _not_ remove an element from an array?

Here is a trivial case:

Since you use the malloc() family and this is cross posted to clc, I
assume you use C.

size_t count = 2;
int * array = (int *)malloc(sizeof(int) * count);

In C this casting is not needed.

array[0] = 42;
array[1] = 9000;
array = (int *)realloc(array, sizeof(int) * (--count));

In C this casting is not needed.






Regards,

Ioannis Vranos

 

[Tak-Shing Chan]

JKop <[email protected]> scribbled the following
on comp.lang.c:
Am I the only person here that thinks it's complete bullshit to think you
can swap the values of two variables without a temporary variable?! It ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
[snip]

And the only good reason I can imagine is the failure to allocate memory
for a temporary object (some objects can be greater than others, some

^^^^^^^^^^^^^^^^^^

Your answer is completely irrelevant. ;-)

To comp.lang.c++: sorry I didn't notice the cross-post at
the beginning. You can safely ignore my out-of-context reply.
What my post really amounts to is a (rather subtle) critique of
Dan Pop's lack of clarity in the replied-to post. [It took me
three to four readings to get his logic!]

Tak-Shing

 

[josh]

Please describe (in code) a situation where two variables share the same memory
location.

union
{
int x;
int y;
} a;

&a.x == &a.y

-josh

 

[Ioannis Vranos]

C99 answer:

4 Some operators (the unary operator ~, and the binary operators
<<, >>, &, ^, and |, collectively described as bitwise
operators) are required to have operands that have integer
type. These operators return values that depend on the internal
representations of integers, and have implementation-defined
and undefined aspects for signed types.

Consider, for example, 0 ^ 0, whose result (an int with all bits set) is
a trap representation, as explicitly allowed by C99 for one's complement.

It's hard to find an example for two's complement using the ^ operator,
but it can be done with ~INT_MAX, if the representation with the sign
bit set and all the value bits reset is a trap representation (again,
explicitly allowed by C99 for two's complement and sign-magnitude).

Whether real world implementations have such trap representations is a
completely different story...

However in C++98 I did not find anything else than this:


5.12 Bitwise exclusive OR operator

exclusive-or-expression:
and-expression
exclusive-or-expression ^ and-expression

The usual arithmetic conversions are performed; the result is the
bitwise exclusive OR function of the operands. The operator applies only
to integral or enumeration operands."






Regards,

Ioannis Vranos

 

[Ioannis Vranos]

Since you seem to be unable to understand plain English:

#include <stdio.h>

void swap(int *p, int *q) { ... }

int main()
{
int i = 10;
swap(&i, &i);
printf("%d\n", i);
return 0;
}

Try this code for different implementations of the swap function, using
a temp var and using in-place swapping. Compare the results.

This example is trivial, but the situation can realistically arise in more
complex algorithms.

You are right about that, however in reality a decent swap
implementation would check if the passed arguments have the same value
so as to avoid unneeded operations.






Regards,

Ioannis Vranos