sorting an array of three kinds of stones

[meital]

There are three kinds of stones: red,green and blue.
Each cell of the array contains one stone.
The array needs to be sorted so that all the red
stones will come first, then the blue ones and
then all the green ones.
There are N stones, as the number of cells in the array.

switch(i,j)- switch the stone in the i-th place with the
one in the j-th place.
color(i)- reveals the color of the stone in the i-th place.

These functions can be used only N times.

please help me,I tried to reach a proper solution but with
no success.

[Eric Sosman]

meital wrote:

There are three kinds of stones: red,green and blue.
Each cell of the array contains one stone.
The array needs to be sorted so that all the red
stones will come first, then the blue ones and
then all the green ones.
There are N stones, as the number of cells in the array.

switch(i,j)- switch the stone in the i-th place with the
one in the j-th place.
color(i)- reveals the color of the stone in the i-th place.

These functions can be used only N times.

please help me,I tried to reach a proper solution but with
no success.

If the homework is supposed to be done in C, then
your instructor has given you a trick question. The
correct answer is not to attempt to implement a solution,
but to demonstrate your knowledge of C by explaining why
no solution is possible. Hint: Is there anything strange
about the names of the functions you are supposed to use?

The trick question has a long tradition, going back
at least as far as Socrates and probably further. There
was an examination for a driving license which posed the
question "You are approaching a four-way intersection at
forty miles per hour when a truck pulls out from the
right; what do you do?" The correct answer was not "Step
on the brakes" or "Steer to the left," but "I do not drive
at forty miles per hour when approaching intersections."
Your instructor is apparently an enthusiast of this sort
of pedagogical technique; perhaps he is a Zen master, too.
You are to be envied for the quality of the education you
are receiving -- and, it appears, ignoring ...

--
Er*********@sun.com

[meital]

It wasn't my instructor who gave me the
question. This question was given to me
in my last interview, so I figured that
there must be an appropriate solution.
I was supposed to give the answer, using C,
but it was also possible to give a written algorithm.

[Arthur J. O'Dwyer]

[This puzzle is better suited to comp.programming and/or
rec.puzzles; xposted and followups set accordingly.]

On Thu, 28 Oct 2004, meital wrote:

There are three kinds of stones: red,green and blue.
Each cell of the array contains one stone.
The array needs to be sorted so that all the red
stones will come first, then the blue ones and
then all the green ones.
There are N stones, as the number of cells in the array.

switch(i,j)- switch the stone in the i-th place with the
one in the j-th place.
color(i)- reveals the color of the stone in the i-th place.

These functions can be used only N times.

You mean, you can call 'color' N times, and then call 'switch'
N times? Then the problem is trivial (though a complete working
solution may require some thought).
If you mean that you can only make N function calls in total,
to both 'color' and 'switch' combined, then I think there is no
solution possible.

Bonus puzzle: What is the minimum number of bits of temporary
storage you need for a solution, if you can call each function
N times?
How many calls to 'switch' do you need, in the minimum case?
What is the minimum big-Oh expecting running time of the fastest
solution?

(I'm sure all three puzzles have been solved already somewhere
in TAOCP...;)

-Arthur

[Dave Vandervies]

In article <67******************************@localhost.talkab outprogramming.com>,
meital <me*******@hotmail.co.il> wrote:

There are three kinds of stones: red,green and blue.
Each cell of the array contains one stone.
The array needs to be sorted so that all the red
stones will come first, then the blue ones and
then all the green ones.
There are N stones, as the number of cells in the array.
Algorithms like this are beyond the scope of the C langauge and therefore
inappropriate for comp.lang.c . comp.programming is probably a good
place to start.
(They're likely to suggest trying a bucket sort; Google will be able to
point you at details.)

switch(i,j)- switch the stone in the i-th place with the
one in the j-th place.
color(i)- reveals the color of the stone in the i-th place.

These functions can be used only N times.

Odd constraints. Homework? You're more likely to get a few good hints
and solutions that you would never be able to hand in than completely
worked answers.
(Try moving appropriately colored stones to the ends of the array.
Will need some refinement to match the constraints on number of calls
to the access functions.)
dave

--
Dave Vandervies dj******@csclub.uwaterloo.ca
The perfect tool when you want output in a rigid column format at the
possible expense of the data integrity.
--Kaz Kylheku in comp.lang.c

[CBFalconer]

Eric Sosman wrote:

meital wrote:

There are three kinds of stones: red,green and blue.
Each cell of the array contains one stone.
The array needs to be sorted so that all the red
stones will come first, then the blue ones and
then all the green ones.
There are N stones, as the number of cells in the array.

switch(i,j)- switch the stone in the i-th place with the
one in the j-th place.
color(i)- reveals the color of the stone in the i-th place.

These functions can be used only N times.

please help me,I tried to reach a proper solution but with
no success.

If the homework is supposed to be done in C, then
your instructor has given you a trick question. The
correct answer is not to attempt to implement a solution,
but to demonstrate your knowledge of C by explaining why
no solution is possible. Hint: Is there anything strange
about the names of the functions you are supposed to use?

This is not the classical sorting problem because there are only
three item classes. I can show it to be of O(N). The rub is the
"used only", which I think has to be multiplied by 2.

This is OT here on c.l.c, so I have cross-posted to
comp.programming and set follow-ups.

--
Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!

[Flash Gordon]

On Thu, 28 Oct 2004 13:53:32 -0400
"meital" <me*******@hotmail.co.il> wrote:

There are three kinds of stones: red,green and blue.
<snip problem description with no algorithm or code>
please help me,I tried to reach a proper solution but with
no success.

If you need help in C coding, post the code you have and say what your
problem is. If you need help developing an algorithm then this is the
wrong group, but possible comp.programming or your tutor might help. If
you want someone to do your homework for you then slip a brown envelope
containing 100UKP in used bills under my door together with your tutors
address.

This group is for discussing the C language, not algorithms.
--
Flash Gordon
Sometimes I think shooting would be far too good for some people.
Although my email address says spam, it is real and I read it.

[CBFalconer]

meital wrote:

It wasn't my instructor who gave me the
question. This question was given to me
in my last interview, so I figured that
there must be an appropriate solution.
I was supposed to give the answer, using C,
but it was also possible to give a written algorithm.

What are you talking about? That is why orienting quotes are
normally included.

--
Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!

[Richard Harter]

On Thu, 28 Oct 2004 13:53:32 -0400, "meital" <me*******@hotmail.co.il>
wrote:

[snip]

Google on "dutch flag algorithm".

[TJ]

On Thu, 28 Oct 2004 13:53:32 -0400, meital wrote:

There are three kinds of stones: red,green and blue.
Each cell of the array contains one stone.
The array needs to be sorted so that all the red
stones will come first, then the blue ones and
then all the green ones.
There are N stones, as the number of cells in the array.

switch(i,j)- switch the stone in the i-th place with the
one in the j-th place.
color(i)- reveals the color of the stone in the i-th place.

These functions can be used only N times.

please help me,I tried to reach a proper solution but with
no success.

One crude solution:

Assumptions:
1) Not a trick question ... 'switch' is a reserved word in C, so your
function switch(i, j) is invalid. Let's assume you meant Switch(i, j).

2) _EACH_ function can be used N times ... makes sense, otherwise you
are required to use all N function calls on color to obtain the color of
the N stones and thus have no more calls left for Switch(i,j) ...

Below is the code ... again crude and not very efficient, but it fits
your requirements. Switch(i,j) and Color(i) are each called exactly N
times. A more efficient algorithm would call Switch(i, j) a _maximum_ of N
times. For example, if all the stones are one color, switch is never
needed.

Sincerely,
TJ Walls
Ph.D. Candidate - Stony Brook University

----------------- <snip> -------------------------
#include <stdio.h>
#include <stdlib.h>

#define N 2000

void Switch(char *list, int pos1, int pos2) {
char c;

c = list[pos1];
list[pos1] = list[pos2];
list[pos2] = c;
}

char Color(char *list, int pos) {
return list[pos];
}

int Sort(char *list) {
int i;
int last_r = 0, last_g = N-1;
int calls = 1;

for (i = 0; i < last_g; i++) {
switch (Color(list, i)) {
case 'r':
if (i != last_r++) {
Switch(list, last_r-1, i);
}
break;
case 'b': Switch(list, i, i); break;
case 'g':
if (i != last_g--) {
Switch(list, last_g+1, i--);
}
break;
default: fprintf(stderr, "Invalid Color\n"); exit(7); break;
}
calls++;
}
return calls;
}

int main(void) {
char *list;
int i, tmp;
int calls;

if ((list = malloc(N*sizeof(char))) == NULL) {
fprintf(stderr, "Out of memory\n");
exit(5);
}

srand(1);

fprintf(stdout, "Original List:\n");
for (i = 0; i < N; i++) {
tmp = 1+(int)(3.0*rand()/(RAND_MAX+1.0));
switch (tmp) {
case 1: list[i] = 'r'; break;
case 2: list[i] = 'b'; break;
case 3: list[i] = 'g'; break;
default: fprintf(stderr, "Invalid Color\n"); exit(6); break;
}
fprintf(stdout, "%c", list[i]);
}

calls = Sort(list);
fprintf(stdout, "\nSorted List:\n");
for (i = 0; i < N; i++) {
fprintf(stdout, "%c", list[i]);
}
fprintf(stdout, "\nCalls: %d\n", calls);

return 0;
}
----------------- <snip> -------------------------

[meital]

Thanks. Your assumptions were correct.
I am trying to understand your code.
You have been a big help to me.

[meital]

It's nice to know it is a well knowm problem.

Thank you.

[Dag Viken]

"TJ" <tj*****@mindspring.nospam.com> wrote in message
news:pa****************************@mindspring.nos pam.com...

On Thu, 28 Oct 2004 13:53:32 -0400, meital wrote:

There are three kinds of stones: red,green and blue.
Each cell of the array contains one stone.
The array needs to be sorted so that all the red
stones will come first, then the blue ones and
then all the green ones.
There are N stones, as the number of cells in the array.

switch(i,j)- switch the stone in the i-th place with the
one in the j-th place.
color(i)- reveals the color of the stone in the i-th place.

These functions can be used only N times.

please help me,I tried to reach a proper solution but with
no success.
One crude solution:

Assumptions:
1) Not a trick question ... 'switch' is a reserved word in C, so your
function switch(i, j) is invalid. Let's assume you meant Switch(i, j).

2) _EACH_ function can be used N times ... makes sense, otherwise you
are required to use all N function calls on color to obtain the color of
the N stones and thus have no more calls left for Switch(i,j) ...

Below is the code ... again crude and not very efficient, but it fits
your requirements. Switch(i,j) and Color(i) are each called exactly N
times. A more efficient algorithm would call Switch(i, j) a _maximum_ of N
times. For example, if all the stones are one color, switch is never
needed.

Sincerely,
TJ Walls
Ph.D. Candidate - Stony Brook University

----------------- <snip> -------------------------
#include <stdio.h>
#include <stdlib.h>

#define N 2000

void Switch(char *list, int pos1, int pos2) {
char c;

c = list[pos1];
list[pos1] = list[pos2];
list[pos2] = c;
}

char Color(char *list, int pos) {
return list[pos];
}

int Sort(char *list) {
int i;
int last_r = 0, last_g = N-1;

Should be initialized to zero:
int calls = 0;
int calls = 1;

This algorithm does not work for some lists ending with a 'r', such as
{'b','r'}. The for loop should be changed to:
for (i = 0; i <= last_g; i++) {
for (i = 0; i < last_g; i++) {
switch (Color(list, i)) {
case 'r':
if (i != last_r++) {
Switch(list, last_r-1, i);
}
break;
This call to Switch() is redundant:
case 'b': Switch(list, i, i); break;
case 'g':
if (i != last_g--) {
Switch(list, last_g+1, i--);
}
break;
default: fprintf(stderr, "Invalid Color\n"); exit(7); break;
}
Counts the number of times Color() is called (=N). Switch() may be called
fewer times.
calls++;
}
return calls;
}

int main(void) {
char *list;
int i, tmp;
int calls;

if ((list = malloc(N*sizeof(char))) == NULL) {
fprintf(stderr, "Out of memory\n");
exit(5);
}

srand(1);

fprintf(stdout, "Original List:\n");
for (i = 0; i < N; i++) {
tmp = 1+(int)(3.0*rand()/(RAND_MAX+1.0));
switch (tmp) {
case 1: list[i] = 'r'; break;
case 2: list[i] = 'b'; break;
case 3: list[i] = 'g'; break;
default: fprintf(stderr, "Invalid Color\n"); exit(6); break;
}
fprintf(stdout, "%c", list[i]);
}

calls = Sort(list);
fprintf(stdout, "\nSorted List:\n");
for (i = 0; i < N; i++) {
fprintf(stdout, "%c", list[i]);
}
fprintf(stdout, "\nCalls: %d\n", calls);

return 0;
}
----------------- <snip> -------------------------

Alternative sort not using Switch() (not really a sort - just counting
stones and overwriting list):

int Sort(char *list)
{
int i;
int count_r = 0, count_b = 0, count_g = 0;
for (i = 0; i < N; i++)
{
switch (Color(list, i))
{
case 'r': count_r++; break;
case 'b': count_b++; break;
case 'g': count_g++; break;
default: fprintf(stderr, "Invalid Color\n"); exit(7); break;
}
}
for (i = 0; count_r > 0; count_r--)
list[i++] = 'r';
for (; count_b > 0; count_b--)
list[i++] = 'b';
for (; count_g > 0; count_g--)
list[i++] = 'g';

return N;
}

Dag

[Pedro Graca]

TJ wrote:

On Thu, 28 Oct 2004 13:53:32 -0400, meital wrote:

There are three kinds of stones: red,green and blue.
Each cell of the array contains one stone.
The array needs to be sorted so that all the red
stones will come first, then the blue ones and
then all the green ones.

[snip] One crude solution:

[snip]

And, unless I changed something I shouldn't have, it needs reviewing :-)
stones$ cat TJ.c
#include <stdio.h>
#include <stdlib.h>
#include "problem.h"

void TJ(int N) {
int i;
int last_r = 0, last_g = N-1;

for (i = 0; i < last_g; i++) {
switch (color(i)) {
case 0:
if (i != last_r++) {
Switch(last_r-1, i);
}
break;
case 1:
Switch(i, i);
break;
case 2:
if (i != last_g--) {
Switch(last_g+1, i--);
}
break;
default:
fprintf(stderr, "Invalid Color\n");
exit(7);
break;
}
}
}

stones$ cat problem.h
#ifndef HEADERGUARD_PROBLEM_H
#define HEADERGUARD_PROBLEM_H

void Switch(int, int);
int color(int);

/* the function you must define */
void pmg1(int);
void pmg2(int);
void TJ(int);

#endif

stones$ gcc -W -Wall -ansi -pedantic problem.c pmg1.c pmg2.c TJ.c -DSHOW_ARRAYS
stones$ ./a.out 16
1 1 1 0 0 2 2 0 0 1 1 0 1 0 0 0

0 0 0 0 0 0 0 0 1 1 1 1 1 1 2 2
pmg1: used 16 color() and 5 Switch() calls.

0 0 0 0 0 0 0 0 1 1 1 1 1 1 2 2
pmg2: used 16 color() and 5 Switch() calls.

0 0 0 0 0 0 0 1 1 1 1 1 1 0 2 2
TJ: **WRONG**

stones$ gcc -W -Wall -ansi -pedantic problem.c pmg1.c pmg2.c TJ.c
stones$ ./a.out 99999
pmg1: used 99999 color() and 38853 Switch() calls.

pmg2: used 99999 color() and 33325 Switch() calls.

TJ: used 99998 color() and 99998 Switch() calls.

--
USENET would be a better place if everybody read: | to mail me: simply |
http://www.catb.org/~esr/faqs/smart-questions.html | "reply" to this post, |
http://www.netmeister.org/news/learn2quote2.html | *NO* MIME, plain text |
http://www.expita.com/nomime.html | and *NO* attachments. |

[TJ]

On Fri, 29 Oct 2004 08:17:03 +0000, Pedro Graca wrote:

TJ wrote:

On Thu, 28 Oct 2004 13:53:32 -0400, meital wrote:

There are three kinds of stones: red,green and blue.
Each cell of the array contains one stone.
The array needs to be sorted so that all the red
stones will come first, then the blue ones and
then all the green ones.

[snip]

One crude solution:

[snip]

And, unless I changed something I shouldn't have, it needs reviewing :-)

Story of my life ... :)
[code snipped]
stones$ gcc -W -Wall -ansi -pedantic problem.c pmg1.c pmg2.c TJ.c -DSHOW_ARRAYS
stones$ ./a.out 16
1 1 1 0 0 2 2 0 0 1 1 0 1 0 0 0

0 0 0 0 0 0 0 0 1 1 1 1 1 1 2 2
pmg1: used 16 color() and 5 Switch() calls.

0 0 0 0 0 0 0 0 1 1 1 1 1 1 2 2
pmg2: used 16 color() and 5 Switch() calls.

0 0 0 0 0 0 0 1 1 1 1 1 1 0 2 2
TJ: **WRONG**

Yup ... see below.

Sincerely,
-TJ Walls

[TJ]

On Fri, 29 Oct 2004 07:50:51 +0000, Dag Viken wrote:

This algorithm does not work for some lists ending with a 'r', such as
{'b','r'}. The for loop should be changed to:
for (i = 0; i <= last_g; i++) {
Damn ... not paying attention. Thanks for the correction.

for (i = 0; i < last_g; i++) {
switch (Color(list, i)) {
case 'r':
if (i != last_r++) {
Switch(list, last_r-1, i);
}
break;

This call to Switch() is redundant:

case 'b': Switch(list, i, i); break;
Did this on purpose ... I wanted to call Switch and Color exactly N
times to illustrate the point of the example. I wrote this before I read
the posts about the Dutch Flag Algorithm. This switch was acting something
akin the pivot point ...
case 'g':
if (i != last_g--) {
Switch(list, last_g+1, i--);
}
break;
default: fprintf(stderr, "Invalid Color\n"); exit(7); break;
}

Counts the number of times Color() is called (=N). Switch() may be called
fewer times.

Originally I actually had:
if (i != last_g+1, i--) {
Switch();
} else {
Switch (i, i);
}

I took it out of the point for some reason ... again, I was trying to
call both functions N times.


int Sort(char *list)
{
int i;
int count_r = 0, count_b = 0, count_g = 0;
for (i = 0; i < N; i++)
{
switch (Color(list, i))
{
case 'r': count_r++; break;
case 'b': count_b++; break;
case 'g': count_g++; break;
default: fprintf(stderr, "Invalid Color\n"); exit(7); break;
}
}
for (i = 0; count_r > 0; count_r--)
list[i++] = 'r';
for (; count_b > 0; count_b--)
list[i++] = 'b';
for (; count_g > 0; count_g--)
list[i++] = 'g';

return N;
}

Dag

Clever ...
Sincerely,
TJ Walls
Ph.D. Candidate - Stony Brook University

[TJ]

On Thu, 28 Oct 2004 21:40:15 -0400, meital wrote:

Thanks. Your assumptions were correct. I am trying to understand your
code.
You have been a big help to me.

My solution was just quick and crude (and partially incorrect) ... since
you said you were asked this in an interview, I tried to do in "interview"
time. I really recommend that you lookup and try to understand QuickSort and
then the Dutch Flag algorithm. They are much more elegant and will be of
more use to you in the future.

Sincerely,
TJ Walls
Ph.D. Candidate - Stony Brook University

[Pedro Graca]

TJ wrote:

On Fri, 29 Oct 2004 08:17:03 +0000, Pedro Graca wrote:

TJ wrote:

One crude solution:

And, unless I changed something I shouldn't have, it needs reviewing :-)

Yup ... see below.

Changed, result now is:

stones$ ./stones 100000
pmg1: used 100000 color() and 38816 Switch() calls in ~0 seconds.

pmg2: used 100000 color() and 33288 Switch() calls in ~4 seconds.

pmg3: used 100000 color() and 33288 Switch() calls in ~7 seconds.

TJ: used 100000 color() and 99997 Switch() calls in ~0 seconds.

Oops
I thought I could make 'pmg2' better; just managed to make it slower :-)

Should I post the complete code?
(I'm learning C, so it probably is bad code)
--
USENET would be a better place if everybody read: | to mail me: simply |
http://www.catb.org/~esr/faqs/smart-questions.html | "reply" to this post, |
http://www.netmeister.org/news/learn2quote2.html | *NO* MIME, plain text |
http://www.expita.com/nomime.html | and *NO* attachments. |